Stationary Distribution of the M/M/c Queue

From Queue Rates to Stationary Probabilities

In an M/M/c queue, arrivals occur at rate $\lambda$, and each of the $c$ servers provides service at rate $\mu$. When fewer than $c$ customers are present, an additional customer can begin service immediately; when at least $c$ are present, all servers are busy and any additional customer waits. This change in the total service rate at $c$ makes the stationary distribution a two-part formula.

Assume throughout that $c$ is a positive integer and $\lambda,\mu>0$. Let $(\Omega,\mathcal{F},\mathbb{P})$ be the probability space supporting the queue, and let $X_t$ be the number of customers in the system at time $t\ge0$. Its state space is $S=\{0,1,2,\ldots\}$, and we use the natural filtration $(\mathcal{F}_t)_{t\ge0}$. Under the M/M/c assumptions, $X_t$ is a continuous-time Markov chain: arrivals increase the count by one, and service completions decrease it by one.

Definition: The birth rate from each state $n$ is $\lambda$. The death rate from state $n\ge1$ is $\delta_n=\min(n,c)\mu$, and $\delta_0=0$. Thus the generator $Q=(q_{ij})$ has $q_{n,n+1}=\lambda$, $q_{n,n-1}=\delta_n$ for $n\ge1$, $q_{nn}=-(\lambda+\delta_n)$, and all other entries zero. Each row sums to zero. A stationary distribution is a probability row vector $\pi=(\pi_0,\pi_1,\ldots)$ satisfying $\pi P(t)=\pi$ for every $t\ge0$, where $P(t)=e^{tQ}$.

Below $c$, the death rate in state $n$ is $n\mu$, because $n$ servers are busy. At and above $c$, the death rate is $c\mu$. The stability condition is $\lambda<c\mu$: it says the arrival rate is less than the total service rate when all servers are occupied. The derivation below will show directly why this condition is required for a stationary probability distribution on the unbounded state space.

The Balance Equations and Their Solution

For adjacent states $n$ and $n+1$, stationary flow upward across the boundary must equal stationary flow downward across it. This gives $\pi_n\lambda=\pi_{n+1}\delta_{n+1}$. The equations can also be obtained by writing $\pi Q=0$ and considering the net flow across the set $\{0,\ldots,n\}$: only a birth from $n$ or a death from $n+1$ crosses that boundary.

Theorem: For an M/M/c queue with $\lambda,\mu>0$ and integer $c\ge1$, a stationary probability distribution exists if and only if $\rho=\lambda/(c\mu)<1$. When it exists, it is unique. Set $a=\lambda/\mu$. Its probabilities are $$ \pi_n= \begin{cases} \displaystyle \pi_0\frac{a^n}{n!}, & 0\le n<c,\\[6pt] \displaystyle \pi_0\frac{a^c}{c!}\rho^{\,n-c}, & n\ge c, \end{cases} \qquad \pi_0= \left[ \sum_{n=0}^{c-1}\frac{a^n}{n!} +\frac{a^c}{c!}\frac{1}{1-\rho} \right]^{-1}. $$

Proof. Write $\delta_n=\min(n,c)\mu$. The transition rates are bounded above: each total rate out of a state is at most $\lambda+c\mu$. Consequently the chain is nonexplosive, and its transition semigroup can be represented by uniformization. To see the relevant facts explicitly, choose $r=\lambda+c\mu$ and define $R=I+Q/r$. The entries of $R$ are nonnegative and its rows sum to one, since each row of $Q$ sums to zero and its total rate out is at most $r$. The semigroup is $$ P(t)=e^{tQ}=e^{-rt}\sum_{k=0}^{\infty}\frac{(rt)^k}{k!}R^k. $$ If a probability vector $\pi$ satisfies $\pi Q=0$, then $\pi R=\pi$, so $\pi R^k=\pi$ for every $k\ge0$. Substitution in the displayed series gives $\pi P(t)=\pi$. Conversely, if $\pi P(t)=\pi$ for all $t$, differentiating at $t=0$ gives $\pi Q=0$; bounded rates justify this derivative through the same series.

For any stationary probability vector, apply $\pi Q=0$ to the indicator of $\{0,\ldots,n\}$. The only transitions crossing its boundary are the birth $n\to n+1$, at rate $\lambda$, and the death $n+1\to n$, at rate $\delta_{n+1}$. Therefore $$ \pi_n\lambda=\pi_{n+1}\delta_{n+1},\qquad n\ge0. $$ Since $\lambda>0$, these equations determine every $\pi_n$ from $\pi_0$. For $0\le n<c$, repeated substitution gives $$ \pi_n=\pi_0\prod_{k=1}^{n}\frac{\lambda}{k\mu} =\pi_0\frac{a^n}{n!}. $$ At $n=c$ this gives $\pi_c=\pi_0a^c/c!$. For each $n\ge c$, the next death rate is $c\mu$, so $\pi_{n+1}/\pi_n=\lambda/(c\mu)=\rho$. Hence $\pi_n=\pi_0(a^c/c!)\rho^{n-c}$ for every $n\ge c$.

It remains to determine when these nonnegative weights can sum to one. Their sum is $$ \pi_0\left[ \sum_{n=0}^{c-1}\frac{a^n}{n!} +\frac{a^c}{c!}\sum_{k=0}^{\infty}\rho^k \right]. $$ The finite sum is positive, and $a^c/c!>0$. The geometric series is finite exactly when $\rho<1$; if $\rho=1$ its terms are all one, and if $\rho>1$ they do not tend to zero. Thus no choice of positive $\pi_0$ can normalize the weights when $\rho\ge1$. When $\rho<1$, summing the geometric series gives the stated value of $\pi_0$. The resulting vector sums to one and satisfies every adjacent balance equation. These equations imply $\pi Q=0$: at state $0$, the inflow from $1$ equals the outflow; at each state $n\ge1$, the two adjacent balance equations give $\pi_{n-1}\lambda+\pi_{n+1}\delta_{n+1}=\pi_n(\lambda+\delta_n)$. By uniformization, $\pi Q=0$ implies $\pi P(t)=\pi$, so the normalized vector is stationary. Finally, the balance equations determine all probabilities from $\pi_0$, and normalization determines $\pi_0$, proving uniqueness. $\square$

The formula separates the two regimes for a reason: before all servers are busy, successive downward rates are $\mu,2\mu,\ldots,c\mu$, producing the factorial. Once the system is at or above $c$, the downward rate stays fixed at $c\mu$, so the probabilities have a geometric tail.

Worked Distributions

Worked Example: Two Servers with Arrival Rate Equal to Per-Server Service Rate

Take $c=2$, $\lambda=1$, and $\mu=1$. The arrival rate equals the per-server service rate, but not the total service capacity: $c\mu=2$. Thus $a=1$ and $\rho=1/2<1$, so a stationary distribution exists.

Before using the generator, check its rows. At state $0$, the off-diagonal rate is $q_{01}=1$ and $q_{00}=-1$, whose sum is $0$. At state $1$, the rates are $q_{10}=1$, $q_{12}=1$, and $q_{11}=-2$, whose sum is $0$. For every state $n\ge2$, the rates are $q_{n,n-1}=2$, $q_{n,n+1}=1$, and $q_{nn}=-3$, whose sum is $0$.

The normalizing constant is $$ Z=1+\frac{1^1}{1!}+\frac{1^2}{2!}\frac{1}{1-1/2} =1+1+\frac12\cdot2=3, $$ so $\pi_0=1/3$. The probabilities below $c$ are $\pi_1=(1/3)(1)=1/3$. At $c$, $\pi_2=(1/3)(1/2)=1/6$, and the tail ratio is $1/2$, giving $\pi_n=(1/6)(1/2)^{n-2}$ for $n\ge2$. The mass below $c$ is $1/3+1/3=2/3$; the tail mass from $2$ onward is $(1/6)/(1-1/2)=1/3$. The total is $2/3+1/3=1$.

Check: The balance equation at $0$ is $\pi_0\lambda=(1/3)(1)=1/3=\pi_1\mu$. At $1$, $\pi_1\lambda=(1/3)(1)=1/3=\pi_2(2\mu)=(1/6)(2)$. Above $2$, the ratio $\pi_{n+1}/\pi_n=1/2=\lambda/(2\mu)$, so each remaining adjacent balance equation holds.

Worked Example: Three Servers with a Fractional Utilization

Take $c=3$, $\lambda=2$, and $\mu=1$. Then $a=2$ and $\rho=2/3<1$. Check the generator rows: state $0$ has rates $q_{01}=2,q_{00}=-2$, summing to $0$; state $1$ has $q_{10}=1,q_{12}=2,q_{11}=-3$, summing to $0$; state $2$ has $q_{21}=2,q_{23}=2,q_{22}=-4$, summing to $0$. Every state $n\ge3$ has rates $q_{n,n-1}=3,q_{n,n+1}=2,q_{nn}=-5$, also summing to $0$.

The normalizer is $$ Z=1+2+\frac{2^2}{2!}+\frac{2^3}{3!}\frac{1}{1-2/3} =1+2+2+\frac{4}{3}\cdot3=9. $$ Thus $\pi_0=1/9$, $\pi_1=(1/9)2=2/9$, and $\pi_2=(1/9)2=2/9$. At $n=3$, $\pi_3=(1/9)(8/6)=4/27$, and for $n\ge3$, $\pi_n=(4/27)(2/3)^{n-3}$.

Check: The mass below $3$ is $1/9+2/9+2/9=5/9$. The tail mass is $(4/27)/(1-2/3)=4/9$, so the total is $1$. At the boundary, $\pi_2\lambda=(2/9)(2)=4/9$ and $\pi_3(3\mu)=(4/27)(3)=4/9$. One step into the tail, $\pi_4=(4/27)(2/3)=8/81$; then $\pi_3\lambda=(4/27)(2)=8/27$ and $\pi_4(3\mu)=(8/81)(3)=8/27$, as required.

Worked Example: A Two-Server Queue Near Its Stability Boundary

Take $c=2$, $\lambda=3$, and $\mu=2$. Here $a=3/2$, the total service capacity is $c\mu=4$, and $\rho=3/4<1$. For the generator, state $0$ has rates $q_{01}=3,q_{00}=-3$, summing to $0$; state $1$ has $q_{10}=2,q_{12}=3,q_{11}=-5$, summing to $0$; and each state $n\ge2$ has $q_{n,n-1}=4,q_{n,n+1}=3,q_{nn}=-7$, summing to $0$.

The normalizer is $$ Z=1+\frac32+\frac{(3/2)^2}{2!}\frac{1}{1-3/4} =1+\frac32+\frac98\cdot4=7, $$ so $\pi_0=1/7$. Then $\pi_1=(1/7)(3/2)=3/14$, and $\pi_2=(1/7)(9/8)=9/56$. For $n\ge2$, $\pi_n=(9/56)(3/4)^{n-2}$.

Check: The mass below $2$ is $1/7+3/14=2/14+3/14=5/14$. The tail mass is $(9/56)/(1-3/4)=(9/56)4=9/14$, giving total $1$. The balance at state $0$ is $\pi_0\lambda=3/7=\pi_1\mu=(3/14)2$. At state $1$, $\pi_1\lambda=9/14=\pi_2(2\mu)=(9/56)4$. These checks also confirm that the tail ratio is $3/4$, not $\lambda/\mu=3/2$.

What the Formula Does—and Does Not—Say

The probabilities describe the number of customers in the system in an invariant regime. They do not by themselves give a waiting-time distribution, a delay probability, or a performance target; those require additional calculations. Nor does the definition of stationarity alone assert that a distribution started from every initial state has already reached equilibrium at a particular time. Here the theorem identifies the invariant probability law and the condition for its existence.

Common mistake: using the per-server rate in the tail. In the two-server example with $\lambda=1,\mu=1$, an incorrect calculation might set the tail ratio to $\lambda/\mu=1$. That would make the proposed tail $\pi_2,\pi_2,\pi_2,\ldots$, which cannot have finite total mass. The correct downward rate in states $n\ge c$ is $c\mu$, not $\mu$; therefore the tail ratio is $\lambda/(c\mu)=1/2$. In general, use $a=\lambda/\mu$ in the factorial portion and $\rho=\lambda/(c\mu)$ in the geometric portion.

A practical calculation should therefore proceed in order: verify the model’s birth and death rates, check $\rho<1$, calculate the finite sum below $c$, add the geometric tail starting at $c$, and normalize. Finally, check both the boundary balance and that all probabilities sum to one. These checks catch the most common errors: omitting the probability at $n=c$ from the tail, using the wrong rate above $c$, or confusing $\lambda/\mu$ with $\lambda/(c\mu)$.

Check Your Understanding

For each calculation, distinguish the finite part below $c$ from the geometric tail beginning at $c$.

For $c=2,\lambda=1,\mu=2$, calculate $a$, $\rho$, and the normalizing constant $Z$.
For $c=3,\lambda=1,\mu=1$, write $\pi_0,\pi_1,\pi_2,\pi_3$ in terms of $\pi_0$, and state the ratio $\pi_{n+1}/\pi_n$ for $n\ge3$.
Why can the adjacent balance equations not be normalized when $\rho=1$?
For $c=2,\lambda=3,\mu=2$, verify the balance equation between states $2$ and $3$ using the worked probabilities.
Explain why the service rate in a state $n\ge c$ is $c\mu$, rather than $\mu$.

Stationary Distribution of the M/M/c Queue

What You'll Learn