Existence and Uniqueness of the Stationary Distribution

From Local Balance to a Probability Distribution

Local balance identifies the relative weights of the states in an M/M/1 queue. Relative weights are not yet a probability distribution: their sum must be finite, and they must be normalized. Even after finding a stationary distribution, a separate question remains: could there be another one? Here we answer both questions for the queue-length process.

Let \((N_t)_{t\ge0}\) be the M/M/1 queue-length process on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with its natural filtration \((\mathcal{F}_t)_{t\ge0}\), and state space \(S=\{0,1,2,\ldots\}\). Arrivals form a Poisson process of rate \(\lambda>0\); service times are exponential with rate \(\mu>0\), and the server works whenever the queue is nonempty. The 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. Each generator row sums to zero: the row at 0 has sum \(-\lambda+\lambda=0\), while each row \(n\ge1\) has sum \(\lambda+\mu-(\lambda+\mu)=0\).

The chain is irreducible: for any states \(i,j\in S\), a finite sequence of upward jumps connects \(i\) to \(j\) when \(j\ge i\), and a finite sequence of downward jumps connects \(i\) to \(j\) when \(j<i\). Every required jump has positive rate because \(\lambda,\mu>0\). In particular, every state communicates with every other state. Irreducibility does not by itself give a stationary probability distribution; the weights still have to be summable.

For a stationary distribution, local balance across the boundary between states \(n\) and \(n+1\) gives \(\lambda\pi_n=\mu\pi_{n+1}\). Thus the weights are proportional to successive powers of \(\rho\). The normalization question is whether those powers have a finite sum.

Existence and Uniqueness

Proof. First suppose \(\lambda<\mu\), so \(0<\rho<1\). Define \(\pi_n=(1-\rho)\rho^n\). The geometric-series formula gives \(\sum_{n=0}^{\infty}\pi_n=(1-\rho)\sum_{n=0}^{\infty}\rho^n=(1-\rho)/(1-\rho)=1\), and every \(\pi_n\ge0\). Also \(\lambda\pi_n=\mu\pi_{n+1}\) for every \(n\ge0\), since \(\mu(1-\rho)\rho^{n+1}=\mu\rho(1-\rho)\rho^n=\lambda\pi_n\). At state 0, the coordinate of \(\pi Q\) is \(\mu\pi_1-\lambda\pi_0=0\). At every state \(n\ge1\), that coordinate is \(\lambda\pi_{n-1}+\mu\pi_{n+1}-(\lambda+\mu)\pi_n\). The local-balance identities give \(\lambda\pi_{n-1}=\mu\pi_n\) and \(\mu\pi_{n+1}=\lambda\pi_n\), so this coordinate is also zero.

To see that \(\pi Q=0\) implies stationarity here, set \(\nu=\lambda+\mu\) and \(R=I+Q/\nu\). The rows of \(R\) are probability distributions: at state 0 the entries are \(R_{0,0}=\mu/\nu\), \(R_{0,1}=\lambda/\nu\); at \(n\ge1\) they are \(R_{n,n-1}=\mu/\nu\), \(R_{n,n+1}=\lambda/\nu\). Each displayed row sums to 1. The queue can be constructed using potential events from a Poisson process of rate \(\nu\), applying one transition of \(R\) at each event; a transition from 0 to 0 is a potential event with no change in queue length. Consequently, \(P(t)=e^{-\nu t}\sum_{k=0}^{\infty}(\nu t)^kR^k/k!\). Since \(\pi Q=0\), \(\pi R=\pi\), so \(\pi R^k=\pi\) for every \(k\ge0\), and the series yields \(\pi P(t)=\pi\). This proves existence.

Now let \(\alpha\) be any stationary probability distribution. The same series gives \(P(t)=I+\nu t(R-I)+O(t^2)\) as \(t\) decreases to zero. The remainder is bounded in the row-sum norm because \(R\) is stochastic; hence stationarity, \(\alpha P(t)=\alpha\), implies \(\alpha Q=0\) by subtracting \(\alpha\), dividing by \(t\), and taking the limit. The state-0 coordinate of this equation is \(\mu\alpha_1-\lambda\alpha_0=0\). For \(n\ge1\), its state-\(n\) coordinate is \(\lambda\alpha_{n-1}+\mu\alpha_{n+1}-(\lambda+\mu)\alpha_n=0\). Define \(J_n=\lambda\alpha_n-\mu\alpha_{n+1}\). The equation at 0 says \(J_0=0\). For \(n\ge1\), rearranging the state-\(n\) equation gives \(J_n=J_{n-1}\), so induction gives \(J_n=0\) for every \(n\ge0\). Therefore \(\alpha_{n+1}=\rho\alpha_n\) and \(\alpha_n=\rho^n\alpha_0\).

If \(\rho<1\), normalization forces \(\alpha_0=1-\rho\), so \(\alpha=\pi\); this proves uniqueness. If \(\rho\ge1\), then either \(\alpha_0=0\), which by the recurrence makes every \(\alpha_n=0\), or \(\alpha_0>0\). In the latter case, \(\sum_n\alpha_n=\alpha_0\sum_n\rho^n\) diverges: for \(\rho=1\) every term is \(\alpha_0\), and for \(\rho>1\) the terms do not tend to zero. Neither case can give a probability distribution. Thus no stationary probability distribution exists when \(\lambda\ge\mu\), completing both directions. \(\square\)

Worked Normalizations

What Uniqueness Does—and Does Not—Say

The uniqueness proof uses more than the recurrence alone. It first shows that any stationary probability distribution must satisfy the generator balance equations, then uses the boundary equation at state 0 to set the constant flow \(J_0\) to zero. The equations at the other states force that flow to remain zero across every boundary. This pins down all relative weights, and normalization pins down their common multiplier.

Common mistake. For \(\rho=2/3\), one might incorrectly write \(\sum_{n=0}^{\infty}\rho^n=1/\rho=3/2\), then use \(\pi_0=2/3\). The geometric-series formula instead gives \(\sum_{n=0}^{\infty}\rho^n=1/(1-\rho)=3\). With the incorrect multiplier, the total mass would be \((2/3)\cdot3=2\), not 1. The correct multiplier is the reciprocal of 3, namely \(\pi_0=1/3\).

Finally, a stationary distribution is an invariant probability law: if the queue starts with that distribution, its distribution remains unchanged at every time. The existence and uniqueness result does not by itself assert that the law from every fixed initial state converges to the stationary distribution. In particular, it is important not to confuse an invariant distribution with a limiting-distribution claim. The next calculations about idle-server probability can use the normalized distribution, but that quantity is distinct from the existence-and-uniqueness argument established here.