Why M/M/Infinity Has a Poisson Stationary Occupancy

Occupancy as a Birth-Death Process

In an M/M/infinity queue, every arriving customer begins service immediately, and each service time is exponential with rate \(\mu\). If there are \(n\) customers present, each has an independent service-completion rate \(\mu\), so the total departure rate is \(n\mu\). Arrivals occur at rate \(\lambda\), regardless of the current occupancy. These two rates explain why the stationary occupancy is not obtained by treating the system as a single server: the departure rate grows with the number of customers.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be the probability space, and let \((X_t)_{t\ge0}\) be the continuous-time Markov chain giving the number of customers in the system at time \(t\). Its state space is \(S=\{0,1,2,\ldots\}\), and we use the natural filtration \(\mathcal{F}_t=\sigma(X_s:0\le s\le t)\). Assume throughout the main result that \(\lambda>0\) and \(\mu>0\). The exponential arrival and service assumptions give the transition rates \(q_{n,n+1}=\lambda\) and \(q_{n,n-1}=n\mu\) for \(n\ge1\); the diagonal rate is \(q_{n,n}=-(\lambda+n\mu)\). At state \(0\), \(q_{0,1}=\lambda\) and \(q_{0,0}=-\lambda\). All other rates are zero. Each generator row sums to zero: at \(n\ge1\), \(\lambda+n\mu-(\lambda+n\mu)=0\), and at \(0\), \(\lambda-\lambda=0\).

A stationary distribution is a probability vector \(\pi=(\pi_0,\pi_1,\ldots)\) such that, when \(X_0\) has distribution \(\pi\), \(X_t\) also has distribution \(\pi\) for every \(t\ge0\). The birth-death balance relation equates the stationary flow from \(n\) to \(n+1\) with the flow in the reverse direction. It suggests \(\pi_n\lambda=\pi_{n+1}(n+1)\mu\). The next result derives this candidate and justifies that it really is stationary.

Proof. Write \(\rho=\lambda/\mu\). The balance relation requires \(\pi_{n+1}=\pi_n\rho/(n+1)\). Repeated substitution gives \(\pi_n=\pi_0\rho^n/n!\) for every \(n\ge0\): the case \(n=0\) is the definition of \(\pi_0\), and each successive case follows by multiplying by \(\rho/(n+1)\). To make these nonnegative values sum to one, the exponential series gives \(\sum_{n\ge0}\pi_0\rho^n/n!=\pi_0 e^\rho=1\), so \(\pi_0=e^{-\rho}\). The proposed probabilities are therefore normalized.

It remains to justify stationarity for the countably infinite state space. For each positive integer \(M\), consider the finite chain on \(\{0,\ldots,M\}\) with the same departure rates and arrival rate \(\lambda\) below \(M\), but with arrivals blocked in state \(M\). Set \(Z_M=\sum_{k=0}^M\rho^k/k!\) and \(\pi_n^{(M)}=(\rho^n/n!)/Z_M\) for \(0\le n\le M\). These probabilities sum to one by the definition of \(Z_M\). For \(0\le n<M\), \(\pi_n^{(M)}\lambda=\pi_{n+1}^{(M)}(n+1)\mu\), since \[ \frac{\pi_{n+1}^{(M)}(n+1)\mu}{\pi_n^{(M)}\lambda} =\frac{\rho}{n+1}\frac{(n+1)\mu}{\lambda}=1. \] These equalities show that, for each neighboring pair, the two stationary flows agree. At each state the total incoming flow therefore equals the total outgoing flow, so \(\pi^{(M)}Q^{(M)}=0\), where \(Q^{(M)}\) is the finite generator. The finite-state transition matrix is \(e^{tQ^{(M)}}\); its power series gives \(\pi^{(M)}e^{tQ^{(M)}}=\pi^{(M)}\), because \(\pi^{(M)}Q^{(M)}=0\). Hence \(\pi^{(M)}\) is stationary for the finite chain.

As \(M\) increases, \(Z_M\) tends to \(e^\rho\), and for each fixed \(n\), \(\pi_n^{(M)}\) tends to \(e^{-\rho}\rho^n/n!=\pi_n\). In fact, \(\pi^{(M)}\) is the distribution \(\pi\) conditioned on \(X_0\le M\), so it approaches \(\pi\) in total variation. To transfer stationarity to the infinite chain, couple a chain started with law \(\pi^{(M)}\) and the finite chain using the same arrivals and the same exponential service lifetimes for customers present initially or arriving later. They agree until the infinite chain reaches \(M\) and an arrival is blocked by the finite chain. For any fixed \(K<M\), a disagreement by time \(t\) is impossible if the initial occupancy is at most \(K\) and the number of arrivals by \(t\) is less than \(M-K\). The probability of disagreement is consequently at most \(\pi^{(M)}(\{K+1,\ldots,M\})+\mathbb{P}(A(t)\ge M-K)\), where \(A(t)\) is Poisson with mean \(\lambda t\). For fixed \(K\), the second term tends to zero as \(M\) increases; then the first can be made arbitrarily small by increasing \(K\), since \(\pi\) is a probability distribution and \(\pi^{(M)}\) converges to it. Thus the two coupled chains disagree by time \(t\) with probability tending to zero.

For any bounded function \(f\) on \(S\), the expectation of \(f(X_t)\) under initial law \(\pi^{(M)}\) differs from its expectation for the finite chain by a quantity tending to zero: if \(\lVert f\rVert_\infty=\sup_n|f(n)|\), the absolute difference is at most \(2\lVert f\rVert_\infty\) times the probability of disagreement. Also, changing the initial distribution from \(\pi^{(M)}\) to \(\pi\) changes this expectation by a quantity tending to zero, by total-variation convergence. The finite chain has stationary law \(\pi^{(M)}\), so its expectation of \(f\) at time \(t\) is \(\sum_n\pi_n^{(M)}f(n)\), which tends to \(\sum_n\pi_nf(n)\). It follows that the infinite chain started with law \(\pi\) has expectation \(\sum_n\pi_nf(n)\) at time \(t\) for every bounded \(f\). This proves stationarity. The process is nonexplosive: on a finite time interval it has finitely many Poisson arrivals almost surely, and the number of departures cannot exceed the initial population plus the number of arrivals. \(\square\)

Reading the Balance Relation

The balance equation has a simple interpretation. If the system has stationary probability \(\pi_n\) of containing \(n\) customers, then the flow from \(n\) to \(n+1\) per unit time is \(\pi_n\lambda\). The flow back from \(n+1\) to \(n\) is \(\pi_{n+1}(n+1)\mu\). Equating them gives \[ \frac{\pi_{n+1}}{\pi_n}=\frac{\lambda}{(n+1)\mu}. \] The factor \(n+1\) is essential: it reflects the \(n+1\) customers who could complete service in state \(n+1\). Repeated use of this ratio produces the factorial in the Poisson probabilities. Normalization then supplies the exponential factor.

Assumptions and a Common Mistake

The main result assumes \(\lambda>0\) and \(\mu>0\). If \(\lambda=0\) and \(\mu>0\), the stationary distribution is concentrated at zero: \(\pi_0=1\) and \(\pi_n=0\) for \(n\ge1\). If \(\mu=0\) and \(\lambda>0\), there is no stationary probability distribution. Indeed, the only possible moves are births; stationary balance at state zero would require \(\lambda\pi_0=0\), hence \(\pi_0=0\), and balance successively at states \(1,2,\ldots\) would force every \(\pi_n=0\), contradicting that probabilities sum to one.

Common mistake: Using the single-server departure rate \(\mu\) in every nonzero state gives the incorrect equation \(\pi_n\lambda=\pi_{n+1}\mu\), and hence the incorrect ratio \(\pi_{n+1}/\pi_n=\lambda/\mu\). For \(\lambda=4\) and \(\mu=2\), that ratio would be \(2\) at every state, so the proposed weights \(1,2,4,8,\ldots\) cannot be normalized. The correction is to use the total departure rate \((n+1)\mu\) from state \(n+1\), giving \(\pi_{n+1}/\pi_n=4/(2(n+1))=2/(n+1)\). The resulting weights are proportional to \(2^n/n!\), whose sum is \(e^2\), and normalization gives the Poisson law with mean \(2\).

The balance calculation identifies the candidate probabilities, while the finite-state argument explains why this normalized candidate is genuinely stationary for the infinite-state queue. Its essential feature is the state-dependent departure rate: more customers mean more independent service completions per unit time.