Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 36 · Applications and Simulation

Simulating the M/M/1 Queue

Analyze the M/M/1 queue with Poisson arrivals and exponential service, derive L, W and Little's law, and verify them with a short Lindley recursion simulation.

Queues are where the processes of this chapter meet real life: checkout lines, web servers, call centers, hospital emergency rooms. The simplest model has Poisson arrivals, exponential service times and one server. Its name in Kendall notation is M/M/1: the M's stand for "Markovian" (memoryless) arrival and service processes, and the 1 is the number of servers.

The model as a birth-death process

Customers arrive as a Poisson process with rate λ. The server handles one customer at a time, each taking Exponential(μ) time (mean 1/μ). Let N(t) be the number in the system (waiting plus in service). It is a birth-death process with λₙ = λ and μₙ = μ, so with traffic intensity ρ = λ/μ < 1 the stationary distribution is

Text
π_n = (1 - ρ) ρ^n,        n = 0, 1, 2, ...

The server is busy a fraction ρ of the time. From this distribution:

Text
L  = E[N]  = ρ / (1 - ρ)                 mean number in system
Lq = ρ² / (1 - ρ)                        mean number waiting
W  = 1 / (μ - λ)                         mean time in system
Wq = ρ / (μ - λ)                         mean time waiting

Little's law connects them without any assumptions about the distribution: L = λ W and Lq = λ Wq. Check: λ W = λ / (μ - λ) = ρ/(1 - ρ) = L. ✓

Notice how fast things deteriorate when ρ → 1: at ρ = 0.5, L = 1; at ρ = 0.9, L = 9; at ρ = 0.99, L = 99. A system run at high utilization is fragile.

Example: λ = 4 customers per hour, μ = 5 per hour, so ρ = 0.8. Then L = 4, W = 1/(5 - 4) = 1 hour, Wq = 0.8 hours (48 minutes). Time in the system is not 12 minutes (the service time): it is 5 times longer, because of waiting.

Lindley's recursion

Instead of tracking the queue in continuous time, track each customer. Let Dₙ be the waiting time (before service) of customer n, Sₙ its service time, and Aₙ₊₁ the gap between customers n and n+1. Customer n+1 arrives Aₙ₊₁ after customer n. In the meantime, customer n has waited Dₙ and is served for Sₙ, so the remaining work in front of n+1 is Dₙ + Sₙ - Aₙ₊₁, or zero if the system has emptied:

Text
D_{n+1} = max(0, D_n + S_n - A_{n+1})

This tiny loop simulates an M/M/1 queue exactly and handles other service distributions too (just change how S is drawn).

Python Lindley recursion versus the formulas

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulated waiting times land close to the theory. Statistical error is a few percent at most.

How utilization drives waiting

Now sweep the traffic intensity and compare the simulated mean time in system with 1/(μ - λ). We keep μ = 1 so that time is measured in service times.

Python Waiting time as utilization grows

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The points hug the curve, which blows up as ρ approaches 1. Near 1 the simulation needs far more customers to stay accurate, because the queue takes a long time to forget its starting state.

Good practice for queue simulation

  • Discard a warm-up period (the queue starts empty, which biases early waits).
  • Use many more customers when ρ is large: estimates become much noisier and slower to settle as ρ approaches 1, so be skeptical of results near saturation.
  • Repeat with different seeds and report a spread, not a single number.
  • If ρ ≥ 1 the waiting times grow without limit: the simulation will not settle.
flowchart LR
  A["Arrivals: Poisson λ"] --> Q["Waiting line"]
  Q --> S["One server: Exp(μ)"]
  S --> D["Departures"]

The M/M/1 system.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. An M/M/1 queue has λ = 3 and μ = 4 per minute. What is the traffic intensity ρ?

    ρ = λ/μ = 3/4 = 0.75.
  2. 2. For the same queue, what is the mean time in the system W?

    W = 1/(μ - λ) = 1/(4 - 3) = 1 minute.
  3. 3. Little's law states that...

    The mean number in the system equals the arrival rate times the mean time in the system.
  4. 4. What happens to the mean wait when ρ gets very close to 1?

    W = 1/(μ(1 - ρ)) tends to infinity as ρ tends to 1.

Summary

  • M/M/1 is a birth-death chain; with ρ = λ/μ < 1 the number in the system is geometric: πₙ = (1 − ρ)ρⁿ.
  • L = ρ/(1 − ρ), W = 1/(μ − λ), Wq = ρ/(μ − λ); Little's law links them.
  • Lindley's recursion D_{n+1} = max(0, Dₙ + Sₙ − A_{n+1}) simulates the queue in a few lines.
  • Waiting explodes as utilization nears 100%.

Next: Branching Processes