Burke's theorem
Burke's theorem states that departures from a stationary M/M/1 queue form a Poisson process with the same rate as its arrivals.
Scope: use a stable single-server queue with Poisson arrival rate lambda, iid exponential service times of rate mu independent of arrivals, unlimited waiting space and lambda < mu. The output law is a stationary result, not a claim about a queue just started empty. [1]
The theorem preserves the distribution of the arrival stream through this queue, not its actual timestamps. Input and output are not independent copies: conservation gives departures = arrivals + initial occupancy - final occupancy over the same interval. Equal mean rates alone do not establish a Poisson output. [1]
In a tandem of independent M/M/1 servers, departures can therefore feed the next stage as Poisson arrivals. Each stage must remain stable. Shared request sizes, backpressure or a non-exponential stage require a separate model; the theorem does not validate a storage pipeline merely because its external arrivals are Poisson. [2]
Counterexample: with one nonpreemptive serial server taking exactly 1 ms per request, consecutive departures are at least 1 ms apart even for Poisson input. A Poisson stream of positive rate has a positive probability of shorter gaps, so this fixed-duration output cannot be Poisson. This is a mathematical support argument, not a measured workload. [4]
Relations
Citations
- Keane and O'Connell: The M/M/1 queue is Bernoulli (2008), section 1; arXiv:0804.3935v1.
- Martin and Prabhakar: Fixed points for multi-class queues (2010), sections 1-2; arXiv:1003.3024v1.
- Hesela: tandem queues and the fixed-duration departure-gap counterexample.
Further reading
Sources & caveats
- The original 1956 publisher record establishes attribution and scope; the open 2008 and 2010 research manuscripts supply the inspected mathematical formulation.
- The fixed-duration counterexample follows directly from serial service. It is not a simulation, hardware measurement or a novel theorem.