The M/G/1 Queue and the Pollaczek-Khinchine Formula

An operations desk staffs a single specialist to manually review flagged trades, arriving randomly (well-modeled as Poisson), but review time per trade varies enormously — most reviews take a couple of minutes, but a small fraction of genuinely complex cases take an hour. The standard M/M/1 queue formula assumes exponential (memoryless) service times, which badly understates how much this heavy-tailed variability actually hurts waiting customers. The M/G/1 queue generalizes to any service-time distribution ("G" for general), and the Pollaczek-Khinchine formula is the exact result for average waiting time there — revealing something the M/M/1 case hides: variance in service time, not just its average, is a first-order driver of how long people wait.

An analogy: a single supermarket checkout with mixed basket sizes

Picture one checkout lane where most customers have a handful of items (fast to scan) but occasionally someone shows up with a completely full cart (very slow). Even if the average items-per-customer stays exactly the same, a lane serving a mix of mostly-fast and occasionally-very-slow customers backs up far worse than one serving customers who are all moderately, consistently average. The occasional very-slow customer creates a long-lasting backlog that a series of consistently-average customers never would, at the identical average service rate. That's the intuitive core of Pollaczek-Khinchine: it's not just how long service takes on average, it's how unevenly those times are spread out.

The formula, one piece at a time

Let $\lambda$ be the arrival rate, and let service times have mean $\mathbb{E}[S] = 1/\mu$ and variance $\text{Var}(S)$. Define utilization $\rho = \lambda/\mu = \lambda \mathbb{E}[S]$ (must be below 1 for stability). The Pollaczek-Khinchine formula for the average waiting time in queue (not counting service itself) is

$$W_q = \frac{\lambda \big(\mathbb{E}[S]^2 + \text{Var}(S)\big)}{2(1-\rho)} = \frac{\rho^2(1+C_S^2)}{2\lambda(1-\rho)} \cdot \frac{2\lambda}{\rho} \cdot \frac{1}{2},$$

more commonly written using the squared coefficient of variation $C_S^2 = \text{Var}(S)/\mathbb{E}[S]^2$ (a scale-free measure of service-time spread) as

$$W_q = \frac{\rho}{1-\rho} \cdot \frac{\mathbb{E}[S](1+C_S^2)}{2}.$$

In plain English: average wait time grows with utilization exactly the way the simpler M/M/1 formula predicts (the $\rho/(1-\rho)$ term, blowing up as the server saturates), but it's also scaled by $(1+C_S^2)/2$ — a factor purely about the shape of the service-time distribution. For exponential service times, $C_S^2 = 1$ (a defining property of the exponential), giving factor 1 and recovering the ordinary M/M/1 formula exactly. For a perfectly constant (zero-variance) service time, $C_S^2 = 0$, and the factor drops to $1/2$ — a deterministic-service queue has half the average wait of an exponential-service queue with the identical mean service time and arrival rate, purely because there's no variability to create pileups.

Drag the rate above to see the exponential's characteristic mix of many short values and a long tail of rare large ones — that shape is exactly what gives exponential service times $C_S^2=1$, the baseline the deterministic ($C_S^2=0$) and heavy-tailed ($C_S^2>1$) cases below are measured against.

Worked example 1: exponential vs. deterministic review time

Suppose flagged trades arrive at $\lambda = 4$ per hour, and average review time is $\mathbb{E}[S] = 12$ minutes $= 0.2$ hours, so $\rho = 4 \times 0.2 = 0.8$. With exponential review times ($C_S^2=1$): $W_q = \frac{0.8}{0.2} \times \frac{0.2 \times 2}{2} = 4 \times 0.2 = 0.8$ hours, or 48 minutes average wait. With perfectly consistent, deterministic 12-minute review times ($C_S^2=0$): $W_q = \frac{0.8}{0.2} \times \frac{0.2 \times 1}{2} = 4 \times 0.1 = 0.4$ hours, or 24 minutes — exactly half the wait, for the identical arrival rate and average service time, purely because deterministic service eliminates the pileup risk from occasional slow reviews.

Worked example 2: the heavy-tailed real-world case

Now model the real situation: 90% of reviews take 5 minutes, 10% take 60 minutes. Mean service time: $\mathbb{E}[S] = 0.9(5) + 0.1(60) = 4.5+6 = 10.5$ minutes $= 0.175$ hours, giving $\rho = 4 \times 0.175 = 0.7$. Variance: $\mathbb{E}[S^2] = 0.9(25)+0.1(3600) = 22.5+360=382.5$ (minutes²), so $\text{Var}(S) = 382.5 - 10.5^2 = 382.5-110.25=272.25$, and $C_S^2 = 272.25/110.25 \approx 2.47$. Plugging in: $W_q = \frac{0.7}{0.3} \times \frac{0.175(1+2.47)}{2} = 2.33 \times \frac{0.175 \times 3.47}{2} \approx 2.33 \times 0.304 \approx 0.71$ hours, or about 42.5 minutes — despite a lower mean service time (10.5 vs. 12 minutes) and lower utilization (0.7 vs. 0.8) than worked example 1's exponential case, the heavy-tailed mix still produces a comparably long wait, entirely because $C_S^2 \approx 2.47$ is far above 1, showing how much the occasional very-slow review distorts the queue.

What this means in practice

The Pollaczek-Khinchine formula is the reason "reduce the variance of processing time," not just "reduce the average," is a real operational lever: standardizing a review process, splitting a rare-but-slow task category into its own dedicated queue, or batching similar-complexity trades together all reduce $C_S^2$ and cut average wait, without touching mean service time or staffing. It also explains why systems with occasional slow outliers feel disproportionately congested relative to what average processing time alone would suggest.