Burke's Theorem for M/M/1 Departure Processes

Why the Departure Process Is Not Obvious

In an M/M/1 queue, arrivals form a Poisson process, but departures are governed by both service times and the queue’s changing occupancy. When the system is empty, a potential service completion produces no departure; when it is busy, service completions do. It is therefore not immediate that departures have independent Poisson increments. Burke’s theorem resolves this question for a queue in stationarity: despite the dependence between occupancy and service activity, the departure process has the same rate as the arrival process.

Let \(A(t)\) count arrivals during \((0,t]\), and let \(D(t)\) count departures during \((0,t]\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), suppose arrivals are generated by a Poisson process of rate \(\lambda>0\), and potential service completions by an independent Poisson process of rate \(\mu>0\). A potential service completion reduces the queue by one only when the queue is nonempty. Let \(X_t\in S=\{0,1,2,\ldots\}\) be the number of customers in the system at time \(t\). Its natural filtration is \(\mathcal{F}_t=\sigma(X_s:0\le s\le t)\). For describing the construction from the independent primitive processes, we may also use the enlarged filtration \(\mathcal{G}_t=\sigma(A(s),C(s):0\le s\le t)\), where \(C\) is the potential service-completion process; this is not the natural filtration of \(X\).

The queue-length process is a continuous-time Markov chain. Its generator \(Q=(q_{ij})\) has \(q_{0,1}=\lambda\), \(q_{0,0}=-\lambda\), and, for \(n\ge1\), \(q_{n,n+1}=\lambda\), \(q_{n,n-1}=\mu\), and \(q_{n,n}=-(\lambda+\mu)\); all other entries are zero. The row at state \(0\) sums to \(-\lambda+\lambda=0\). Each row at \(n\ge1\) sums to \(\lambda+\mu-(\lambda+\mu)=0\). These rates apply even though the service clock is ineffective when the queue is empty: there is no transition from \(0\) to \(-1\).

The Stationary Distribution and Reversibility

Write \(\pi_n=\mathbb{P}(X_t=n)\) in stationarity. The stability condition makes the geometric probabilities below summable. We first verify stationarity and detailed balance directly, so that the reversal argument has its required starting point.

Proof. Since \(0<\rho<1\), the geometric series gives \(\sum_{n=0}^{\infty}(1-\rho)\rho^n=(1-\rho)/(1-\rho)=1\), so these probabilities form a distribution. For each \(n\ge0\), \(\pi_n\lambda=(1-\rho)\rho^n\lambda=(1-\rho)\rho^{n+1}\mu=\pi_{n+1}\mu\), using \(\rho\mu=\lambda\). Thus detailed balance holds on every adjacent pair. At state \(0\), the incoming stationary flow is \(\pi_1\mu=\pi_0\lambda\), equal to the outgoing flow. At state \(n\ge1\), incoming flow is \(\pi_{n-1}\lambda+\pi_{n+1}\mu\), while outgoing flow is \(\pi_n(\lambda+\mu)\). Detailed balance gives \(\pi_{n-1}\lambda=\pi_n\mu\) and \(\pi_{n+1}\mu=\pi_n\lambda\), so the incoming flow is \(\pi_n(\lambda+\mu)\) as well. Hence \(\pi Q=0\), and \(\pi\) is invariant. The rates are bounded by \(\lambda+\mu\), so the chain is nonexplosive; an invariant initial distribution therefore gives a stationary chain. \(\square\)

For a stationary continuous-time Markov chain, the reversed transition rate from \(i\) to \(j\), for \(i\ne j\), is \(q^*_{ij}=\pi_jq_{ji}/\pi_i\). In this queue, detailed balance gives \(q^*_{n,n+1}=\lambda\) and \(q^*_{n+1,n}=\mu\). Thus reversal leaves the queue-length transition rates unchanged. The next result justifies using that reversed chain, rather than treating the rate formula as a mere analogy.

Proof. Fix a finite horizon \(T\) and a possible path with successive states \(i_0,\ldots,i_m\) and jump times \(0<t_1<\cdots<t_m<T\). Its density with respect to the jump-time coordinates is its initial probability \(\pi_{i_0}\), multiplied by the jump rates \(q_{i_{r-1},i_r}\), and by the holding-time factors \(\exp(-q_{i_r}(t_{r+1}-t_r))\), where \(q_i=-q_{ii}\), \(t_0=0\), and \(t_{m+1}=T\). The reversed path visits \(i_m,\ldots,i_0\) in reverse order. Its initial probability is \(\pi_{i_m}\). The holding-time factors are unchanged because the same state occupies the same time interval in either description. Detailed balance, applied successively to the edges of the path, gives \(\pi_{i_0}\prod_{r=1}^m q_{i_{r-1},i_r}=\pi_{i_m}\prod_{r=1}^m q_{i_r,i_{r-1}}\). Therefore the forward and reversed path densities agree. This establishes that the reversed path has the same Markov transition rates, as claimed. \(\square\)

Burke’s Theorem

Proof. Fix \(T>0\) and reverse the stationary queue-length path on \([0,T]\), so the reversed path at reversed time \(s\) is \(X_{T-s}\). By the time-reversal proposition and detailed balance, this reversed path has the law of an M/M/1 queue with arrival rate \(\lambda\) and service rate \(\mu\), started with distribution \(\pi\). In the reversed path, an upward jump from \(n\) to \(n+1\) has rate \(\lambda\), independent of the current state \(n\). Such upward jumps are its external arrivals: they can be constructed from a rate-\(\lambda\) Poisson process independent of the initial state and of the potential service process. Every forward departure is a downward jump of the forward queue and hence an upward jump of the reversed queue. Reversing the order of points in \((0,T]\) therefore identifies the forward departure points with the reversed arrival points. A homogeneous Poisson process restricted to \((0,T]\) remains a homogeneous Poisson process of the same rate when its points are reflected about \(T/2\); its counts on disjoint intervals remain independent, since the reflected intervals are disjoint and have the same lengths. This proves the asserted Poisson law on \((0,T]\). Since the argument holds for every \(T\), it proves the departure-process assertion. Finally, \(X_T\) is the initial state of the reversed chain. The reversed arrivals in \((0,T]\) are independent of that initial state, so the forward departures in \((0,T]\) are independent of \(X_T\). \(\square\)

The independence statement concerns departures up to time \(T\), not departures after time \(T\). For example, if \(X_T=0\), the queue cannot depart immediately without first receiving a customer. Thus the theorem does not say that future departures are independent of the queue length at the present time.

Where the Result Can Fail

Stationarity is essential. If the queue starts empty, it does not have the stationary departure process from time zero. For instance, set \(\lambda=\mu=1\) and \(X_0=0\). The first departure by time \(t\) requires an arrival at some time \(s\le t\), followed by a service completion before \(t\). The first arrival has density \(e^{-s}\) at time \(s\); after it, the service time is exponential with rate \(1\). Thus the probability of at least one departure by time \(t\) is

As \(t\) decreases to zero, this probability is of order \(t^2\), whereas a rate-\(1\) Poisson process would have probability \(1-e^{-t}\) of at least one point, which is of order \(t\). The mismatch occurs because an initially empty queue must first receive a customer before any departure is possible. The stationary theorem cannot be applied to this initial condition.

Common mistake. It is incorrect to identify the departure rate with the service rate \(\mu\), as if the server were always busy. With \(\lambda=1,\mu=2\), that mistake predicts rate \(2\). In fact, the stationary busy probability is \(\rho=1/2\), so the departure rate is \(\mu\mathbb{P}(X_t\ge1)=2(1/2)=1=\lambda\). More importantly, matching this average rate alone does not establish a Poisson process: independent increments require the time-reversal argument.

Burke’s theorem is useful because it allows a queue’s stationary output to be analyzed with the same interval-count tools as an external Poisson input. Its scope must be kept precise: the arrival rate must be strictly below the service rate, the queue must be stationary, and the conclusion is about the departure point process. It does not say that arrivals and departures are the same events, that the queue length is independent of future departures, or that the output from an arbitrary initial state is immediately Poisson.