Kingman's Formula for G/G/1 Queues

An exchange's matching engine, or a risk desk's overnight batch job, is a single server processing one request at a time, fed by requests that don't arrive on a neat schedule and don't take identical time to handle. You want to know the average wait before service starts. If arrivals were a Poisson process and service times were exponential, there's a clean closed-form answer. But real order flow and real processing times are lumpier and more variable than that — bursts of orders, occasional slow computations — and for that general case there is no exact formula. Kingman's formula is the standard approximation, and its real message isn't the algebra: it's that variability, not just how busy the server is, is what makes queues blow up.

An analogy: the checkout line that never seems fair

Picture two supermarket checkouts running at the same average speed and the same average customer arrival rate — say both are 80% busy. One has customers arriving at almost perfectly even intervals with almost identical basket sizes. The other has customers who arrive in unpredictable clumps and whose basket sizes range from one item to a full cart. Even though both checkouts do the same average amount of work, the second one will have dramatically longer average waits. The extra wait isn't from being "more busy" — it's from being less predictable. Kingman's formula turns that intuition into a number.

The formula, one symbol at a time

Let $\rho$ (rho) be the utilization — the fraction of time the server is busy, a number between 0 and 1. Let $C_a^2$ be the squared coefficient of variation of interarrival times (variance of the gaps between arrivals, divided by their mean squared) — it measures how erratic arrivals are; $C_a^2 = 1$ for a Poisson process, and it is larger when arrivals cluster. Let $C_s^2$ be the same measure for service times. Let $\mathbb{E}[S]$ be the mean service time. Kingman's approximation for the mean waiting time in queue, $\mathbb{E}[W_q]$, is:

$$\mathbb{E}[W_q] \approx \left( \frac{\rho}{1 - \rho} \right) \left( \frac{C_a^2 + C_s^2}{2} \right) \mathbb{E}[S] .$$

In plain English: the average wait is the product of two separate effects multiplied together. The first factor, $\rho/(1-\rho)$, is the pure congestion effect — it explodes as utilization approaches 100%, exactly as in the simple Poisson queue. The second factor, $(C_a^2 + C_s^2)/2$, is the pure variability effect — the average of how erratic arrivals are and how erratic service is. Two queues at identical utilization can have very different waits purely because this second factor differs; a perfectly regular queue ($C_a^2 = C_s^2 = 0$) has no wait at all even at high utilization, while a bursty one can have waits many multiples longer.

Worked example 1: comparing two order-routing setups

A router forwards orders to a single downstream venue at $\rho = 0.8$ utilization, mean processing time $\mathbb{E}[S] = 2$ milliseconds. Setup A has fairly regular arrivals and service ($C_a^2 = 1$, $C_s^2 = 1$, the Poisson case):

$$\mathbb{E}[W_q] \approx \frac{0.8}{0.2} \times \frac{1+1}{2} \times 2 = 4 \times 1 \times 2 = 8 \text{ ms}.$$

Setup B has the same utilization and mean service time, but bursty order flow from a single large client and occasional slow retries ($C_a^2 = 4$, $C_s^2 = 2$):

$$\mathbb{E}[W_q] \approx 4 \times \frac{4+2}{2} \times 2 = 4 \times 3 \times 2 = 24 \text{ ms}.$$

Same average load, three times the wait — entirely from variability.

Worked example 2: what capacity buys you

Suppose Setup B's ops team can't reduce variability but can add capacity to cut utilization to $\rho = 0.5$:

$$\mathbb{E}[W_q] \approx \frac{0.5}{0.5} \times 3 \times 2 = 1 \times 3 \times 2 = 6 \text{ ms}.$$

Cutting utilization from 0.8 to 0.5 cuts the wait from 24ms to 6ms — a four-fold improvement from a much smaller drop in load, because the $\rho/(1-\rho)$ term is so steep near 1. This is the standard argument for never running latency-sensitive infrastructure near full utilization: the congestion term punishes you nonlinearly.

What this means in practice

Kingman's formula is the quick sanity check a quant reaches for when sizing infrastructure, market-making quote engines, or any single-stage pipeline without simulating the full arrival and service distributions: measure $\rho$, $C_a^2$, $C_s^2$ from historical logs, plug in. It also gives a lever beyond "add servers" — if arrivals or service times can be made more regular (smoothing order submission, capping retry variance), wait drops just as much as adding capacity would, often more cheaply.