Local Balance Equations for Queue Length

Stationary Flow Across Queue-Length Boundaries

In an M/M/1 queue, arrivals increase the number of customers in the system by one, while service completions decrease it by one whenever the system is nonempty. A stationary distribution describes probabilities that remain unchanged over time. Local balance expresses this stationarity through a particularly simple comparison: for each adjacent pair of queue lengths, the stationary flow upward must equal the stationary flow downward. This turns a system of balance equations into a recurrence for the probabilities.

Assume throughout that the arrival rate \(\lambda\) and service rate \(\mu\) are both strictly positive. On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \((X_t)_{t\ge0}\) be the queue-length continuous-time Markov chain on \(S=\{0,1,2,\ldots\}\), with its natural filtration \((\mathcal{F}_t)_{t\ge0}\). From state \(0\), an arrival moves the chain to \(1\) at rate \(\lambda\). From state \(n\ge1\), arrivals move it to \(n+1\) at rate \(\lambda\), and service completions move it to \(n-1\) at rate \(\mu\).

The generator \(Q=(q_{ij})\) records these transition rates. Its nonzero entries are \(q_{01}=\lambda\), \(q_{00}=-\lambda\), and, for \(n\ge1\), \(q_{n,n+1}=\lambda\), \(q_{n,n-1}=\mu\), and \(q_{nn}=-(\lambda+\mu)\). Every other entry is zero. The row at state \(0\) sums to \(-\lambda+\lambda=0\); each row at a positive state sums to \(\mu-(\lambda+\mu)+\lambda=0\). The rates out of any state are at most \(\lambda+\mu\), so this generator has bounded rates.

From Global Balance to Local Balance

For this bounded-rate chain, stationarity is equivalent to the coordinate equations \((\pi Q)_n=0\) for all \(n\). To see why the generator equations apply, the transition semigroup is \(P(t)=e^{tQ}\). Since the rates are bounded, \(Q\) is a bounded operator on summable row vectors, and the exponential series converges. If \(\pi P(t)=\pi\) for all \(t\), differentiating at \(t=0\) gives \(\pi Q=0\). Conversely, if \(\pi Q=0\), then every positive power satisfies \(\pi Q^k=0\) for \(k\ge1\), so the exponential series gives \(\pi e^{tQ}=\pi\). This argument is specific to the bounded-rate setting used here.

Proof. Assume first that \(\pi\) is stationary. By the generator characterization, \(\pi Q=0\). At state \(0\), the coordinate equation is \[ -\lambda\pi_0+\mu\pi_1=0. \] At each state \(n\ge1\), it is \[ \lambda\pi_{n-1}-(\lambda+\mu)\pi_n+\mu\pi_{n+1}=0. \] Define the net upward flow across the boundary between states \(n\) and \(n+1\) by \(J_n=\lambda\pi_n-\mu\pi_{n+1}\). The equation at state \(0\) gives \(J_0=0\). For each \(n\ge1\), direct subtraction gives \[ J_{n-1}-J_n =\lambda\pi_{n-1}+\mu\pi_{n+1}-(\lambda+\mu)\pi_n =0. \] Thus \(J_n=J_{n-1}\) for every \(n\ge1\). Starting from \(J_0=0\), induction gives \(J_n=0\) for all \(n\ge0\), which is exactly local balance. Conversely, suppose local balance holds. It gives the state \(0\) equation immediately. For \(n\ge1\), subtracting the local-balance equation at \(n\) from the one at \(n-1\) yields \[ \lambda\pi_{n-1}-(\lambda+\mu)\pi_n+\mu\pi_{n+1}=0. \] Therefore \(\pi Q=0\), and the bounded-rate semigroup argument shows that \(\pi\) is stationary. \(\square\)

The boundary equation matters: there is no transition from state \(0\) to a negative queue length. The first balance equation is therefore \(\lambda\pi_0=\mu\pi_1\), not an interior equation with an additional probability \(\pi_{-1}\). Once the boundary equation holds, each interior equation says that the net flow across consecutive boundaries is unchanged; the proof shows that this flow must be zero at every boundary.

Solving and Normalizing the Recurrence

Because \(\mu>0\), local balance can be rearranged as \(\pi_{n+1}=(\lambda/\mu)\pi_n\). Set \(\rho=\lambda/\mu\), the traffic intensity. Repeated application gives \(\pi_n=\pi_0\rho^n\) for every \(n\ge0\). This recurrence determines the relative probabilities, but they form a stationary distribution only if they can be normalized to sum to one.

Proof. The recurrence gives \(\pi_n=\pi_0\rho^n\) by induction: it holds at \(n=0\), and if it holds at \(n\), then \(\pi_{n+1}=\rho\pi_n=\pi_0\rho^{n+1}\). If \(\pi_0=0\), the recurrence forces every \(\pi_n=0\), contradicting the requirement that the probabilities sum to one. Thus any probability solution must have \(\pi_0>0\). When \(\rho\ge1\), every term \(\pi_0\rho^n\) is at least \(\pi_0\), so the infinite sum diverges and cannot equal one. When \(0<\rho<1\), the geometric-series identity gives \(\sum_{n=0}^{\infty}\pi_0\rho^n=\pi_0/(1-\rho)\). Setting this sum equal to one requires \(\pi_0=1-\rho\). The resulting probabilities are nonnegative, sum to one, and satisfy \(\pi_n\lambda=\pi_{n+1}\mu\), since \((1-\rho)\rho^n\lambda=(1-\rho)\rho^{n+1}\mu\) when \(\rho=\lambda/\mu\). The theorem then shows that this probability vector is stationary. \(\square\)

This result identifies when the local-balance solution can be a probability distribution. It does not say that a chain started from every initial state converges to that distribution; stationarity and convergence to stationarity are different claims.

Interpreting the Flow Equations

The equation \(\pi_n\lambda=\pi_{n+1}\mu\) compares flows across the cut separating states \(0,\ldots,n\) from states \(n+1,n+2,\ldots\). Under stationarity, the only upward crossing of this cut is an arrival from state \(n\), with probability of being at that state \(\pi_n\) and rate \(\lambda\). The only downward crossing is a service completion from state \(n+1\), with probability \(\pi_{n+1}\) and rate \(\mu\). The equation says these stationary rates match.

A common mistake is to reverse the ratio and write \(\pi_{n+1}=(\mu/\lambda)\pi_n\). For the rates \(\lambda=3,\mu=2\), this mistake gives the proposed values \(\pi_0=1/3\) and \(\pi_1=(1/3)(2/3)=2/9\), using the reversed ratio’s geometric normalization. But the boundary flows would be \(\lambda\pi_0=3(1/3)=1\) and \(\mu\pi_1=2(2/9)=4/9\), which are unequal. The correction is to solve \(\lambda\pi_n=\mu\pi_{n+1}\) for the next probability: \(\pi_{n+1}=(\lambda/\mu)\pi_n\). A second frequent error is to normalize a geometric sequence with ratio at least one; checking the infinite sum prevents treating a formal recurrence solution as a stationary probability distribution.