Applying Burke's Theorem to Tandem M/M/1 Queues

Poisson Flow Through a Tandem

In a tandem queue, customers pass through stations in a fixed order: each departure from one station becomes an arrival to the next. This structure makes Burke’s theorem especially useful. In steady state, a stable M/M/1 station with Poisson input has a Poisson departure process at the same rate as its input. Thus, under the right assumptions, the output of one station supplies the Poisson input needed to analyze the next. The key qualification is that every station must itself be stable.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Consider \(r\) single-server stations in series. Station \(k\) has an independent exponential service mechanism of rate \(\mu_k\), and external arrivals form a Poisson process of rate \(\lambda\), independent of all service mechanisms. Each customer visits each station once, in order, and leaves after station \(r\). Let \(X^{(k)}_t\in\{0,1,2,\ldots\}\) be the number of customers at station \(k\) at time \(t\), including any customer in service. The tandem is considered in steady state.

Proof. The external input to station 1 is Poisson of rate \(\lambda\). Since \(\lambda<\mu_1\), station 1 is a stable M/M/1 queue in steady state, so Burke’s theorem gives a Poisson departure process of rate \(\lambda\). That departure process is the arrival process to station 2. The service mechanism at station 2 is independent of its input, and \(\lambda<\mu_2\), so Burke’s theorem applies there and gives a Poisson departure process of rate \(\lambda\). Repeating this argument, if the output of station \(k\) is Poisson of rate \(\lambda\), it is the input to station \(k+1\); independence of that station’s service mechanism and \(\lambda<\mu_{k+1}\) allow Burke’s theorem to give output rate \(\lambda\). Induction proves the claim for all stations. Each customer leaves the system only after the last station, whose departure rate is therefore \(\lambda\). \(\square\)

This argument uses Burke’s theorem at each node; it does not establish that the queue lengths at different nodes are independent. A Poisson output statement concerns the departure process of a stationary M/M/1 node. It does not, by itself, imply independence between that process and the node’s queue length at a given time, or between queue lengths at separate stations.

Node-Level Performance

For a stable M/M/1 station with arrival rate \(\lambda\) and service rate \(\mu>\lambda\), write \(\rho=\lambda/\mu\) for its utilization. Its queue-length process has state space \(\{0,1,2,\ldots\}\): from state \(n\), arrivals increase the state at rate \(\lambda\), and when \(n\ge1\), service completions decrease it at rate \(\mu\).

Proof. Let \((\pi_n)_{n\ge0}\) be a stationary distribution. Sum the stationary balance equations over states \(0,\ldots,n\). Transitions between two states in this set cancel in the sum. The only flow out is an arrival from state \(n\), with rate \(\pi_n\lambda\); the only flow in is a service completion from state \(n+1\), with rate \(\pi_{n+1}\mu\). Therefore \(\pi_n\lambda=\pi_{n+1}\mu\), so \(\pi_{n+1}=\rho\pi_n\) and \(\pi_n=\pi_0\rho^n\). Since \(\rho<1\), normalization gives \(1=\sum_{n\ge0}\pi_0\rho^n=\pi_0/(1-\rho)\), hence \(\pi_0=1-\rho\). These probabilities satisfy the balance equations: the equation at 0 is \(\pi_0\lambda=\pi_1\mu\); for \(n\ge1\), substitution gives \(\pi_{n-1}\lambda+\pi_{n+1}\mu=\pi_n\mu+\pi_n\lambda\). Thus they are stationary, and the recurrence and normalization show they are the only stationary probability distribution. Using \(\sum_{n\ge0}n\rho^n=\rho/(1-\rho)^2\), obtained by differentiating the geometric series for \(0\le\rho<1\), gives \(L=\sum n\pi_n=\rho/(1-\rho)\). The probability the server is busy is \(1-\pi_0=\rho\), so \(L_q=L-\rho=\rho/(1-\rho)-\rho=\rho^2/(1-\rho)\). \(\square\)

Little’s law states that, in a stable stationary system, the mean number in a system equals its arrival rate times the mean time a customer spends there. Consequently, the mean total time \(W\) at one M/M/1 station and the mean queueing time \(W_q\), excluding service, are

The service-time mean \(1/\mu\) is subtracted because a customer’s total time at the node consists of its waiting time plus its service time. These formulas apply separately at each tandem station once Burke’s theorem has supplied its Poisson arrival rate.

Worked Tandem Calculations

Common Pitfalls and Scope

Common mistake: ignoring the downstream stability condition. A mistaken calculation might set \(\rho_2=\lambda/\mu_2=2/2=1\), then write \(\pi_n=(1-\rho_2)\rho_2^n=0\) and claim this is the stationary distribution. Although each displayed term is zero, their sum is zero, not one. The geometric stationary distribution requires \(\rho<1\); it cannot be extended to \(\rho=1\). The correction is to test \(\lambda<\mu_k\) at every node before using stationary M/M/1 formulas.

Another tempting overreach is to infer that the queue lengths \(X^{(1)}_t,\ldots,X^{(r)}_t\) are independent because each station has a Poisson input and a geometric stationary occupancy. Burke’s theorem establishes a Poisson departure process under its stationary M/M/1 assumptions. It does not by itself establish independence among the node occupancies. A separate network result is needed for joint stationary probabilities.

For a stable tandem, the practical sequence is: check every strict stability inequality \(\lambda<\mu_k\); pass the common Poisson rate from one node to the next using Burke’s theorem; compute each node’s performance with its own service rate; and add node-level expected times for the end-to-end mean. The addition uses linearity of expectation, not independence of delays.