queueing theory Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because th ...

, a discipline within the mathematical

theory of probability Probability theory or probability calculus is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expre ...

, Burke's theorem (sometimes the Burke's output theorem) is a

theorem In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...

(stated and demonstrated by Paul J. Burke while working at

Bell Telephone Laboratories Nokia Bell Labs, commonly referred to as ''Bell Labs'', is an American industrial research and development company owned by Finnish technology company Nokia. With headquarters located in Murray Hill, New Jersey, Murray Hill, New Jersey, the compa ...

) asserting that, for the

M/M/1 queue In queueing theory, a discipline within the mathematical probability theory, theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service ...

, M/M/c queue or M/M/∞ queue in the steady state with arrivals is a

Poisson process In probability theory, statistics and related fields, a Poisson point process (also known as: Poisson random measure, Poisson random point field and Poisson point field) is a type of mathematical object that consists of Point (geometry), points ...

with rate parameter λ: # The departure process is a Poisson process with rate parameter λ. # At time ''t'' the number of customers in the queue is independent of the departure process prior to time ''t''.

Proof

Burke first published this theorem along with a proof in 1956. The theorem was anticipated but not proved by O’Brien (1954) and Morse (1955). A second proof of the theorem follows from a more general result published by Reich. The proof offered by Burke shows that the time intervals between successive departures are independently and exponentially distributed with parameter equal to the arrival rate parameter, from which the result follows. Demonstration_Burke_theorem

An alternative proof is possible by considering the

reversed process In mathematics and physics, time-reversibility is the property of a process whose governing rules remain unchanged when the direction of its sequence of actions is reversed. A deterministic process is time-reversible if the time-reversed process ...

and noting that the

is a reversible stochastic process. Consider the figure. By

Kolmogorov's criterion In probability theory, Kolmogorov's criterion, named after Andrey Kolmogorov, is a theorem giving a necessary and sufficient condition for a Markov chain or continuous-time Markov chain to be stochastically identical to its time-reversed version. ...

for reversibility, any birth-death process is a reversible Markov chain. Note that the arrival instants in the forward Markov chain are the departure instants of the reversed Markov chain. Thus the departure process is a

of rate λ. Moreover, in the forward process the arrival at time t is independent of the number of customers after t. Thus in the reversed process, the number of customers in the queue is independent of the departure process prior to time ''t''. This proof could be counter-intuitive, in the sense that the departure process of a birth-death process is independent of the service offered.

Related results and extensions

The theorem can be generalised for "only a few cases," but remains valid for M/M/c queues and Geom/Geom/1 queues. It is thought that Burke's theorem does not extend to queues fed by a Markovian arrival processes (MAP) and is conjectured that the output process of an MAP/M/1 queue is an MAP only if the queue is an M/M/1 queue. An analogous theorem for the Brownian queue was proven by J. Michael Harrison.

References

{{Queueing theory Single queueing nodes Theorems in probability theory Queueing theory