The M/M/1 Queue and Waiting-Time Distributions

Picture a single checkout line at a small grocery store. Customers arrive at random, unpredictable moments. The cashier serves each one in a random amount of time — some transactions are quick, some take forever because someone can't find their card. If you asked "how long will the average customer wait," you might guess the answer depends smoothly and gently on how busy the store is. It doesn't. A store running at 50% of its checkout capacity has short lines. A store running at 95% of capacity — seemingly "almost fine" — has customers waiting an order of magnitude longer, not because anything catastrophic happened, but because randomness compounds violently as a system approaches full utilization. The M/M/1 queue is the simplest mathematical model that makes this blowup precise, and it shows up everywhere a resource serves random requests one at a time: an exchange's matching engine, a market maker's quote-update pipeline, a single execution algorithm working one order at a time.

The setup, one symbol at a time

"M/M/1" names three things about the queue. The first M means arrivals happen according to a Poisson process with rate $\lambda$ ("lambda") — customers (or orders, or requests) arrive one at a time, at random moments, with $\lambda$ events happening per unit time on average, and the gaps between arrivals are memoryless (exponentially distributed). The second M means service times are also exponentially distributed, with rate $\mu$ ("mu") — the server finishes an average of $\mu$ customers per unit time it's working, and like the arrivals, how long the current customer has already been served tells you nothing about how much longer they'll take. The 1 means there is exactly one server.

The single most important derived quantity is the utilization, or traffic intensity:

$$\rho = \frac{\lambda}{\mu}$$

In words: utilization is the ratio of how fast work arrives to how fast the server can do it. If $\rho < 1$, the server can keep up on average and the queue reaches a stable, steady-state length. If $\rho \geq 1$, work arrives faster than it can be cleared and the queue grows without bound. Assuming $\rho < 1$, the steady-state formulas for an M/M/1 queue are:

$$L = \frac{\rho}{1-\rho}, \qquad W = \frac{1}{\mu - \lambda}$$

$L$ is the expected number of customers in the system (waiting plus being served) once things have settled into steady state. $W$ is the expected total time a customer spends in the system, waiting plus being served. These two are tied together by Little's Law, $L = \lambda W$ — in words, the average number of items in a system equals the arrival rate times the average time each item spends there, a relationship that holds for essentially any stable queue, not just M/M/1.

Adjust the rate parameter in the explorer above and watch the shape of the Poisson distribution change — this is the distribution governing arrivals in an M/M/1 queue; the wait-time blowup in the figure above comes from the interaction between this arrival randomness and the server's own randomness, not from either one alone.

Worked example 1: a market maker's quote-update queue

Suppose a market maker's system receives quote-update requests at $\lambda = 8$ per second (Poisson) and its single processing thread handles requests at $\mu = 10$ per second (exponential service time, average $1/\mu = 0.1$ seconds each). Utilization is $\rho = \lambda/\mu = 8/10 = 0.8$. Expected number of requests in the system: $L = \rho/(1-\rho) = 0.8/0.2 = 4$ requests, on average, either waiting or being processed. Expected total time a request spends in the system: $W = 1/(\mu-\lambda) = 1/(10-8) = 1/2 = 0.5$ seconds. Check with Little's Law: $L = \lambda W = 8 \times 0.5 = 4$ — matches exactly.

Worked example 2: what happens as utilization creeps up

Keep $\mu = 10$ fixed and raise $\lambda$ from 5 to 9.5, watching $W = 1/(\mu-\lambda)$:

• $\lambda = 5$: $\rho = 0.5$, $W = 1/(10-5) = 0.20$ seconds.
• $\lambda = 8$: $\rho = 0.8$, $W = 1/(10-8) = 0.50$ seconds — 2.5x the wait at $\rho=0.5$, even though $\rho$ only rose by 60% relative.
• $\lambda = 9$: $\rho = 0.9$, $W = 1/(10-9) = 1.00$ second — double again.
• $\lambda = 9.5$: $\rho = 0.95$, $W = 1/(10-9.5) = 2.00$ seconds — double again, from a 5-percentage-point rise in $\rho$.

Utilization went from 0.5 to 0.95 — less than double — while wait time went from 0.20 to 2.00 seconds, a tenfold increase. That is the $\rho/(1-\rho)$ shape: nothing catastrophic happens to $\rho$ itself, but $1-\rho$, the thing in the denominator, is shrinking toward zero, and dividing by a number approaching zero is what produces the blowup.

What this means in practice

• Capacity planning near "busy but fine" is dangerous. A system running comfortably at $\rho=0.6$ that grows its load to $\rho=0.85$ hasn't gotten "somewhat slower" — its wait time has likely tripled or more. Sizing infrastructure with headroom well below $\rho=1$ isn't conservatism, it's the only way to keep tail latency bounded.
• The waiting-time distribution, not just its average, is exponential with rate $\mu - \lambda$ — meaning wait times are themselves highly variable, and occasional very long waits are expected even when the average wait looks tame, which matters for latency-sensitive execution and matching-engine design.
• Single-server bottlenecks (the "1" in M/M/1) are the worst case. Splitting one busy queue into several parallel servers (an M/M/c queue) tends to reduce wait dramatically for the same total capacity, which is why systems add parallel processing threads rather than speeding up one thread.
• The Poisson/exponential assumptions are a deliberate simplification. Real arrival and service processes are rarely perfectly memoryless; when they're not, the more general M/G/1 (Pollaczek-Khinchine) or G/G/1 (Kingman) formulas are needed, but the qualitative blowup-near-$\rho=1$ behavior persists across all of them.