Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 38 · M/M/1 Queues

The M/M/1 Waiting-Time Distribution

Go beyond averages: the M/M/1 time in system is exponential, and the queueing delay has an atom at zero. Compute tail probabilities and percentiles.

Averages hide the experience of unlucky customers. A mean wait of 4 minutes sounds fine, but if one in ten customers waits over 10 minutes, the service feels bad. Service targets are often stated as percentiles: "95% of requests answered within 2 seconds." For the M/M/1 queue with first come first served service, the full waiting-time distribution is known and quite simple.

Time in system

A new arrival finds n customers ahead with probability (1 - ρ) ρ^n (PASTA). The arrival then needs to wait for n residual services and its own service. Because service is memoryless, that is the sum of n + 1 independent exponential(μ) times. Mixing over n with geometric weights gives a clean result:

The time in system T is exponential with rate μ - λ.

P(T > t) = e^(-(μ - λ) t)

Its mean is 1/(μ - λ), matching W. The standard deviation also equals 1/(μ - λ), a hint that waits are quite spread out.

Waiting time in the queue

The delay before service starts, Wq, is a mixture. With probability 1 - ρ the server is idle and the customer waits 0. Otherwise the wait is a positive exponential random variable:

P(Wq > t) = ρ e^(-(μ - λ) t) for t ≥ 0

So there is an atom at zero of size 1 - ρ, and given that you wait at all, the wait is exponential with rate μ - λ. The average is ρ × 1/(μ - λ) = ρ/(μ - λ), which matches Wq.

Percentiles

The p-th percentile of a continuous distribution solves P(T > t) = 1 - p. For time in system:

t_p = ln(1 / (1 - p)) / (μ - λ)

For the queueing delay, if 1 - p < ρ:

t_p = ln(ρ / (1 - p)) / (μ - λ)

and if 1 - p ≥ ρ then t_p = 0, because that fraction of customers does not wait at all. For example the median wait of customers is 0 whenever ρ < 0.5.

Example: λ = 0.8 and μ = 1 per minute. Then μ - λ = 0.2. The 95th percentile of the time in system is ln(20)/0.2, about 15 minutes, although the mean is 5 minutes.

Python Percentile calculator

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.

Checking against a simulation

We estimate P(Wq > t) from a simulated stream of customers and compare it with ρ e^(-(μ-λ)t). The simulation computes each customer's waiting time with the recursion "start = later of arrival and the server becoming free".

Python Simulated versus formula

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 agreement is good. Notice how heavy the tail is: at ρ = 0.8, about 29% of customers wait more than 5 minutes, even though the mean wait is 4 minutes and the server is faster than the arrivals.

These formulas assume FIFO service. Under other disciplines the mean stays the same but the distribution does not, as the earlier LIFO example showed.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In an M/M/1 queue, the time in system (FIFO) follows which distribution?

    The sum of a geometric number of exponential services is exponential with rate mu - lambda.
  2. 2. With rho = 0.7, what is the probability a customer does not wait at all?

    The customer waits 0 when the server is idle, which has probability 1 - rho = 0.3.
  3. 3. lambda = 2 and mu = 3 per minute. What is P(T > 3 minutes) for the time in system?

    The rate is mu - lambda = 1 per minute, so P(T > 3) = e^(-3), about 0.05.
  4. 4. Why is the median queueing delay 0 when rho < 0.5?

    P(Wq = 0) = 1 - rho is above 0.5, so at least half the customers wait nothing.

Summary

  • Time in system is exponential with rate μ - λ: P(T > t) = e^(-(μ-λ)t).
  • Queueing delay: P(Wq > t) = ρ e^(-(μ-λ)t), with an atom 1 - ρ at zero.
  • Percentiles come from solving the tail equation; they are much larger than the mean.
  • Results assume first come first served service.

Next: M/M/1 Design Trade-offs