Common Errors in M/M/1 Balance Equations

Why Check Each State?

For an M/M/1 queue, a stationary distribution is not validated just because its terms look geometric or because a few equations seem to fit. At each state, the probability flow into that state must equal the flow out. The state \(0\) is especially important: when the system is empty, a service completion cannot occur. Using the interior service rate at this boundary, reversing an arrival and a departure, or omitting the normalizing constant can each produce an incorrect answer.

Consider a probability space \((\Omega,\mathcal{F},\mathbb{P})\) carrying the continuous-time Markov process \((X_t)_{t\ge0}\), where \(X_t\) is the number of customers in the system at time \(t\), with state space \(S=\{0,1,2,\ldots\}\) and filtration \((\mathcal{F}_t)_{t\ge0}\). Arrivals occur at rate \(\lambda\ge0\), and service times are exponential with rate \(\mu>0\). A customer departs at rate \(\mu\) when \(X_t\ge1\); at state \(0\), there is no departure. The process is nonexplosive: its total transition rate is at most \(\lambda+\mu\).

A stationary distribution is a probability row vector \(\pi=(\pi_0,\pi_1,\ldots)\) such that if \(X_0\) has distribution \(\pi\), then \(X_t\) has distribution \(\pi\) for every \(t\ge0\). For this bounded-rate process, the standard generator criterion says that a probability vector is stationary exactly when \(\pi Q=0\). This criterion is a standard result for continuous-time Markov chains; its general proof is given in the later course material on continuous-time chains. Here the equations \(\pi Q=0\) express the state-by-state flow balances.

The Correct Balance Equations

At state \(0\), the only transition out is an arrival, at rate \(\lambda\); the only transition in is a service completion from state \(1\), at rate \(\mu\). At a state \(n\ge1\), transitions in come from \(n-1\) by an arrival and \(n+1\) by a service completion. Transitions out come from \(n\) by an arrival or a service completion. Consequently, the balance equations are

The first equation is a boundary equation, not the \(n\ge1\) equation with \(n=0\) substituted into it. In particular, there is no service-completion flow out of state \(0\).

Proof. Let \(\pi\) be any stationary probability distribution, so its entries are nonnegative, sum to \(1\), and satisfy the balance equations. 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 \(n\ge1\), rearranging the balance equation gives \(\lambda\pi_{n-1}-\mu\pi_n=\lambda\pi_n-\mu\pi_{n+1}\), or \(J_{n-1}=J_n\). Inductively, every \(J_n=0\), so \(\lambda\pi_n=\mu\pi_{n+1}\) for all \(n\ge0\). If \(\lambda=0\), this forces \(\pi_{n+1}=0\) for every \(n\), and normalization gives \(\pi_0=1\). If \(\lambda>0\), it gives \(\pi_{n+1}=\rho\pi_n\), hence \(\pi_n=\pi_0\rho^n\). When \(\rho<1\), the geometric sum is \(\sum_{n=0}^{\infty}\rho^n=1/(1-\rho)\), so normalization requires \(\pi_0=1-\rho\). When \(\rho=1\), all entries equal \(\pi_0\), and they cannot sum to \(1\) unless \(\pi_0=0\), which would make their sum \(0\). When \(\rho>1\), if \(\pi_0>0\) the terms \(\pi_0\rho^n\) do not even tend to zero, so their sum diverges; if \(\pi_0=0\), the recurrence forces every entry to be zero. Thus no stationary probability distribution exists for \(\rho\ge1\). Conversely, when \(\rho<1\), the proposed entries are nonnegative and sum to \((1-\rho)/(1-\rho)=1\). They satisfy \(\lambda\pi_n=\mu\pi_{n+1}\) because \(\mu(1-\rho)\rho^{n+1}=\lambda(1-\rho)\rho^n\), including the case \(\lambda=0\). These equalities give the state \(0\) balance and, by adding the two neighboring flows, each interior balance. The generator criterion therefore makes this probability vector stationary. The recurrence and normalization also show it is the only one. \(\square\)

Three Checks That Catch Common Errors

A Practical Audit

When checking an M/M/1 balance calculation, start by writing the transitions at the boundary separately from those in the interior. Then check the direction and units of each flow: a rate from \(n\) to \(n+1\) is an upward arrival rate, while a rate from \(n\) to \(n-1\) is a downward service rate. A stationary equation compares rate multiplied by probability with rate multiplied by probability; it is not obtained by swapping the two rates or by using a probability from a different chain.

In particular, the embedded jump chain records the next state conditional on a jump. At \(n\ge1\), its upward and downward probabilities are \(\lambda/(\lambda+\mu)\) and \(\mu/(\lambda+\mu)\), respectively; at \(0\), its next jump is upward with probability \(1\). Those jump probabilities are not the generator rates. Do not insert them into \(\pi Q=0\) as if they were rates, and do not treat state \(0\) as if it had the same possible departures as a positive state.

Finally, test a proposed answer in three distinct ways: check the boundary balance, check at least one interior balance using its incoming and outgoing flows, and check that the entries are nonnegative and sum to one. For the M/M/1 stationary distribution, the recurrence and boundary balance imply \(\pi_n=\pi_0\rho^n\); normalization is possible only when \(\rho<1\). A sequence satisfying the algebra but failing the sum, or a normalized sequence that fails the boundary equation, is not a stationary probability distribution.