---
title: Variability, M/G/1 and Kingman’s approximation
url: https://doc.liz6.com/en/theory/03-queueing-theory/05-variability-and-mg1
locale: en
area: theory
tags:
- Queueing theory
- Theory
date: 2026-09-10
modified: 2026-09-10
description: At the same mean service time and utilization, an occasional very long job can delay many followers. M/G/1 exposes the role of the service second moment. Kingman's approximation adds interarrival variability to a mean-wait estimate.
---
# Variability, M/G/1 and Kingman’s approximation
At the same mean service time and utilization, an occasional very long job can delay many followers. M/G/1 exposes the role of the service second moment. Kingman's approximation adds interarrival variability to a mean-wait estimate.
## Why long jobs are encountered more often
Sampling a busy server at a random time favors a service interval of length $s$ in proportion to $s$: it occupies more time. Its residual-work area is $s^2/2$. For IID service, the mean residual service conditional on a busy observation is:
$$E[R\mid\text{busy}]=\frac{E[S^2]}{2E[S]}.$$
This is $E[S]/2$ for deterministic service and $E[S]$ for exponential service. It is an average under time sampling, not a claim that an individual job is always halfway through.
## The Pollaczek–Khinchine formula
Assume Poisson arrivals, IID service independent of arrivals, one FCFS server, unlimited space and $\rho=\lambda E[S]<1$. With finite $E[S^2]$, waiting consists of residual work in service plus the complete work of jobs ahead. PASTA and $L_q=\lambda E[W_q]$ give:
$$E[W_q]=\rho\frac{E[S^2]}{2E[S]}+L_qE[S]
=\frac{\lambda E[S^2]}2+\rho E[W_q].$$
Rearrange to obtain the exact PK mean within M/G/1:
$$E[W_q]=\frac{\lambda E[S^2]}{2(1-\rho)}
=\frac{\rho}{1-\rho}\frac{1+C_s^2}{2}E[S].$$
At mean service 10 ms and $\rho=0.8$, values $C_s^2=0,1,9$ give mean waits of 20, 40 and 200 ms. Mean service work has not increased; the chance of encountering a long service and the resulting accumulated wait have.
## A stationary distribution need not have a finite waiting mean
Under the usual IID M/G/1 conditions, finite $E[S]$ and $\rho<1$ can yield a stationary system. If $E[S^2]=\infty$, FCFS mean waiting can nevertheless be infinite. A suitably scaled Pareto service distribution with shape strictly between 1 and 2 has this property.
Every finite dataset can produce a finite sample variance. That does not establish a finite population second moment. Inspect large jobs, timeout censoring, request categories and sensitivity to observation length; a few extremes alone do not identify a tail family.
## General arrivals and Kingman's approximation
For FCFS GI/GI/1 with mutually independent IID gap and service sequences and finite second moments, a commonly used approximation is:
$$E[W_q]\approx\frac{\rho}{1-\rho}\frac{C_a^2+C_s^2}{2}E[S].$$
This mean approximation is motivated by heavy-traffic analysis. It is neither a general upper bound nor a p99 formula. Low load, strong dependence or batch arrivals can create substantial error. When arrivals really are Poisson, $C_a^2=1$ recovers exact PK numerically; measuring that moment alone does not establish exactness.
**Variability, M/G/1 and Kingman’s approximation · Experiment**
Mean service is fixed at 10 ms. The solid line always assumes Poisson arrivals; the dashed line uses current Cₐ² in a GI/GI/1 approximation. They are not two exact solutions of the same arrival process and do not predict p99.
First hold $C_a^2=1$ and vary service variability, then move $C_a^2$ away from 1. The solid curve remains a Poisson reference; only the dashed curve uses the chosen arrival variability. They are not two exact answers for the same system.
## Check your understanding
1. Replace deterministic service with exponential service of the same mean. How does M/G/1 mean waiting change?
Reasoning
$C_s^2$ increases from 0 to 1, doubling the factor $(1+C_s^2)/2$ and therefore mean waiting. Total system time also includes unchanged mean service, so it generally does not double.
Reasoning
Measure service sizes and waits by request class to locate FCFS blocking. Then evaluate splitting large tasks, isolating batch work, scheduling or bounding task cost. Each changes fairness or throughput, so assess more than the overall mean.