Birth-Death Rates and Stability in M/M/c

From Queue Assumptions to an Occupancy Process

In an M/M/c queue, customers arrive according to a Poisson process with rate \(\lambda\), and each of the \(c\) servers has independent exponential service times with rate \(\mu\). The quantity that determines whether the queue can settle into a steady regime is not the rate of one server alone: when all servers are busy, their combined service-completion rate is \(c\mu\). To make that comparison precise, first describe the queue length as a continuous-time Markov chain.

Assume throughout that \(c\) is a positive integer, \(\mu>0\), and initially \(\lambda>0\). Let \((X_t)_{t\ge0}\) be the number of customers in the system at time \(t\), on a probability space \((\Omega,\mathcal F,\mathbb P)\), with state space \(S=\{0,1,2,\ldots\}\). Use the natural filtration \(\mathcal F_t=\sigma(X_s:0\le s\le t)\). The number in the system includes customers in service and customers waiting. The exponential and independence assumptions imply that, given the current occupancy, the future transition rates do not depend on the earlier history.

When \(n<c\), exactly \(n\) servers are busy. The next completion is the minimum of \(n\) independent exponential service times of rate \(\mu\), so its rate is \(n\mu\). When \(n\ge c\), all \(c\) servers are busy; any extra customers wait, and the total completion rate is \(c\mu\). At \(n=0\), no completion is possible. The total rate out of state \(n\) is \(\lambda+\delta_n\), bounded above by \(\lambda+c\mu\). Thus the process is non-explosive: its transitions can be generated by thinning potential event times from a Poisson process of rate \(\lambda+c\mu\), so it cannot make infinitely many jumps in a finite time interval.

For every row \(n\) of \(Q\), the diagonal entry is the negative of the sum of the off-diagonal entries. In particular, the row sum is \(\lambda+\delta_n-(\lambda+\delta_n)=0\), including \(n=0\), where it is \(\lambda-\lambda=0\). This zero row sum is the generator counterpart of a transition matrix having rows that sum to one.

Balance Weights and the Stability Criterion

For a birth-death chain, the balance between neighboring states determines candidate stationary probabilities. The following argument derives the relevant weights and checks when they can be normalized; it does not require computing queueing performance measures.

Proof. Write \(\delta_n=\min(n,c)\mu\) for \(n\ge1\), and suppose first that \(\pi=(\pi_0,\pi_1,\ldots)\) is a stationary probability distribution. The stationary equations at each state say that total probability flow into that state equals total flow out. At state \(0\), this gives \(\pi_0\lambda=\pi_1\delta_1\). For \(n\ge1\), it gives

Define the net flow from \(n\) to \(n+1\) by \(J_n=\pi_n\lambda-\pi_{n+1}\delta_{n+1}\). The equation at \(0\) gives \(J_0=0\). For \(n\ge1\), rearranging the displayed stationary equation gives \(J_n=J_{n-1}\). Induction therefore gives \(J_n=0\) for every \(n\ge0\), so \(\pi_{n+1}=\pi_n\lambda/\delta_{n+1}\). In particular, \(\pi_0\) cannot be zero: if it were, this recurrence would force every \(\pi_n=0\), contradicting \(\sum_n\pi_n=1\).

Define \(w_0=1\) and \(w_n=\prod_{k=1}^n\lambda/\delta_k\) for \(n\ge1\). The recurrence shows that any stationary probability distribution must have \(\pi_n=\pi_0w_n\). Conversely, if \(Z=\sum_{n=0}^{\infty}w_n\) is finite, set \(\pi_n=w_n/Z\). Then \(\sum_n\pi_n=1\) and \(\pi_n\lambda=\pi_{n+1}\delta_{n+1}\) at every neighboring pair. These equalities imply the stationary equation at state \(0\), and at each \(n\ge1\) they give \(\pi_{n-1}\lambda+\pi_{n+1}\delta_{n+1}=\pi_n\delta_n+\pi_n\lambda\). Thus \(\pi Q=0\). To see that this is an invariant distribution, choose \(\nu=\lambda+c\mu\) and let \(R=I+Q/\nu\). The bounded rates ensure that \(R\) is a stochastic matrix, and \(\pi Q=0\) implies \(\pi R=\pi\). The transition semigroup is \(e^{tQ}=e^{-\nu t}\sum_{k=0}^{\infty}(\nu t)^kR^k/k!\); therefore \(\pi e^{tQ}=\pi\) for every \(t\ge0\). We have proved that an invariant probability exists exactly when \(Z\) is finite.

It remains to test convergence. For \(1\le n\le c\), multiplying the first \(n\) factors gives \(w_n=(\lambda/\mu)^n/n!\). For \(n\ge c\), each additional factor is \(\lambda/(c\mu)\), so

The finitely many terms with \(n<c\) cannot affect convergence. The remaining tail is a geometric series with positive first term and ratio \(r=\lambda/(c\mu)\). It is finite exactly when \(r<1\): if \(r=1\), its terms are a fixed positive constant; if \(r>1\), its terms do not tend to zero. Hence \(Z<\infty\) exactly when \(\lambda<c\mu\). This proves the invariant-distribution criterion, and the stated irreducible-chain classification gives the stability conclusion. \(\square\)

The ratio \(r=\lambda/(c\mu)\) compares the arrival rate with the maximum combined service rate. Stability requires a strict inequality. At equality, the fact that the average rates match does not create a stationary probability distribution: the balance weights have a non-summable tail.

What the Stability Condition Does—and Does Not—Say

The condition \(\lambda<c\mu\) concerns the existence of a stationary regime for the unlimited-capacity M/M/c queue. It is not a formula for a waiting time, a delay probability, or a queue-length tail; those require additional calculations. The balance weights above explain why the strict inequality matters, while leaving their normalized stationary probabilities and performance measures for their own derivations.

Two boundary cases are worth separating. If \(\lambda=0\) and \(\mu>0\), the irreducibility assumption in the theorem does not hold: state \(0\) is absorbing, and the distribution concentrated at \(0\) is stationary. Thus the queue is stable in the sense of having a stationary distribution, even though it is not an irreducible positive-recurrent chain on all of \(S\). If \(\mu=0\), there is no service capacity; for \(\lambda>0\), the occupancy only increases, so the positive-rate stability criterion does not apply and no stationary distribution exists.

Common mistake. A frequent error is to assign departure rate \(n\mu\) in every state. For \(c=2\), \(\lambda=3\), and \(\mu=1\), that mistake assigns departure rate \(5\mu=5\) in state \(5\), and might suggest that the queue can clear faster as occupancy grows. The correct rate is \(\min(5,2)\mu=2\), because only two servers can work at once. The corresponding tail ratio is \(3/(2\cdot1)=3/2\), not \(3/5\); the balance weights grow, confirming instability. The correction is to count busy servers, not customers, when computing the total completion rate.