= Pollaczek-Khinchine mean formula
{c}
For a stationary <first come first served> <M G 1 queue>, take independent service times $S$ independent of the <Poisson process> of arrivals. Let $m=\mathbb ES$, $\rho=\lambda m<1$ and $\mathbb ES^2<\infty$. Then the mean <queueing delay> $w$ and mean <queue population> $L$ are
$$
w=\frac{\lambda\mathbb ES^2}{2(1-\rho)},\qquad
L=\rho+\frac{\lambda^2\mathbb ES^2}{2(1-\rho)}.
$$
To see why the second moment appears, a completed service of length $S$ contributes triangular area $S^2/2$ under the <residual service time> curve. The <renewal-reward theorem> gives mean residual duration $r=\lambda\mathbb ES^2/2$, counting zero while idle. <Poisson arrivals see time averages> and <Little's law> then give $w=r+m\lambda w$. Solving this identity proves the formula.<Discrete Stochastic Processes (draft of 2nd edition, 31 January 2011) by Robert Gallager>[Section 4.5.5, equations 4.46–4.50, printed pp. 186–187]{ref}
For the same mean $m$, deterministic service has $\mathbb ES^2=m^2$, while exponential service has $2m^2$, doubling the mean wait at fixed arrival rate. With $m=1$ minute and $\lambda=1/2$ per minute, these waits are respectively $1/2$ and one minute. Stability alone does not guarantee finite mean delay: for positive $\lambda$ and infinite second moment, the mean FCFS wait is infinite even when $\rho<1$.
Back to article page