Stationary Probabilities for the M/M/c/K Queue

Occupancy and Rates in a Finite Queue

In an M/M/c/K queue, $c$ servers share a single waiting line and the system can contain at most $K$ customers in total, including those in service. When the system is full, a new arrival cannot enter. The stationary probabilities therefore describe the long-run occupancy of a finite-state process, with a change in the departure rate at the point where all $c$ servers are busy.

Assume throughout that $c$ and $K$ are integers with $1\le c\le K$, the arrival rate satisfies $\lambda>0$, and each busy server serves at rate $\mu>0$. Arrivals follow a Poisson process, service times are independent exponential random variables with rate $\mu$, and the arrival and service processes are independent. Let $(X_t)_{t\ge0}$ be the continuous-time Markov chain on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with state space $S=\{0,1,\ldots,K\}$, where $X_t$ is the number of customers in the system at time $t$.

From state $n<K$, an arrival increases the occupancy to $n+1$ at rate $\lambda$. From state $K$, the arrival rate into the system is zero. From state $n\ge1$, the total departure rate is $\min(n,c)\mu$: there are $n$ busy servers when $n<c$, and $c$ busy servers when $n\ge c$. Write $Q=(q_{ij})$ for the generator, whose off-diagonal entries are transition rates and whose rows sum to zero.

Definition: A stationary distribution for this finite continuous-time Markov chain is a probability row vector $\pi=(\pi_0,\ldots,\pi_K)$ such that $\pi P(t)=\pi$ for every $t\ge0$, where $P(t)=e^{tQ}$ is the transition matrix at time $t$. For a finite-state chain, this is equivalent to $\pi Q=0$.

To see the equivalence in the definition, if $\pi Q=0$, then $\pi Q^m=0$ for every integer $m\ge1$. Expanding the matrix exponential gives $\pi e^{tQ}=\pi$. Conversely, if $\pi e^{tQ}=\pi$ for every $t\ge0$, differentiating at $t=0$ gives $\pi Q=0$. We use this finite-state characterization to derive the probabilities.

Deriving the Stationary Weights

It is useful to first find unnormalized weights. Put $a=\lambda/\mu$ and $\rho=\lambda/(c\mu)=a/c$. The upward rate from $n$ is $\lambda$ for $n<K$, and the downward rate from $n$ is $\min(n,c)\mu$ for $n\ge1$. The ratio of the weight at $n+1$ to the weight at $n$ is the upward rate from $n$ divided by the downward rate from $n+1$. Below $c$, that downward rate increases with the occupancy; from $c$ onward it remains $c\mu$.

Theorem: Under the assumptions above, the unique stationary distribution of the M/M/c/K occupancy chain is $$ \pi_n=\frac{w_n}{Z},\qquad 0\le n\le K, $$ where $$ w_n= \begin{cases} \dfrac{a^n}{n!}, & 0\le n\le c,\\[6pt] \dfrac{a^c}{c!}\rho^{\,n-c}, & c\le n\le K, \end{cases} \qquad Z=\sum_{n=0}^{c-1}\frac{a^n}{n!} +\frac{a^c}{c!}\sum_{r=0}^{K-c}\rho^r. $$ The two expressions for $w_c$ agree.

Proof. For a finite-state chain, stationarity is equivalent to $\pi Q=0$, as shown above. Write $b_n=\lambda$ for $0\le n<K$, $b_K=0$, and $d_n=\min(n,c)\mu$ for $1\le n\le K$, with $d_0=0$. For any row vector $\pi$, define the net upward flow across the edge from $n$ to $n+1$ by $J_n=\pi_n b_n-\pi_{n+1}d_{n+1}$, for $0\le n<K$. At state $0$, the equation $(\pi Q)_0=0$ says $J_0=0$. At an interior state $n$, where $1\le n<K$, the equation $(\pi Q)_n=0$ says $J_{n-1}-J_n=0$. Consequently, all the $J_n$ equal $J_0=0$. At state $K$, the equation is also satisfied when $J_{K-1}=0$; there is no upward flow out of $K$. Thus stationarity is equivalent to the adjacent-flow equations $\pi_n b_n=\pi_{n+1}d_{n+1}$ on all edges.

All rates $b_n$ for $n<K$ and $d_{n+1}$ for $n<K$ are positive. Therefore any stationary distribution must satisfy $$ \frac{\pi_{n+1}}{\pi_n}=\frac{\lambda}{\min(n+1,c)\mu},\qquad 0\le n<K. $$ Starting with weight $w_0=1$, for $n+1\le c$ this recursion gives $w_{n+1}/w_n=a/(n+1)$, hence $w_n=a^n/n!$ up to $n=c$. For $n\ge c$, it gives $w_{n+1}/w_n=\lambda/(c\mu)=\rho$, hence $w_n=(a^c/c!)\rho^{n-c}$. The weights are positive and have finite sum $Z$, since there are only $K+1$ states. Normalizing them gives a probability vector, and each adjacent-flow equation holds for that vector, so it is stationary. The same recursion shows every stationary vector is proportional to these weights; its entries must sum to one, which fixes the proportionality constant as $1/Z$. This proves both existence and uniqueness. $\square$

The formula has two regimes. For occupancies $0,\ldots,c$, each additional customer encounters another busy server, so the downward rate increases from $n\mu$ to $(n+1)\mu$. This produces the factorial term. Once $c$ customers are present, every server is busy; extra customers wait, and the departure rate stays at $c\mu$. The weights above $c$ therefore form a geometric sequence with ratio $\rho$. The finite sum in $Z$ is valid whether $\rho$ equals one or not; if $\rho=1$, its second sum is simply $K-c+1$.

Worked Distributions

Worked Example: Two Servers and Two Waiting Places

Let $c=2$, $K=4$, $\lambda=2$, and $\mu=1$. The states are $0,1,2,3,4$. The generator, with rows and columns in that order, is $$ Q= \begin{bmatrix} -2&2&0&0&0\\ 1&-3&2&0&0\\ 0&2&-4&2&0\\ 0&0&2&-4&2\\ 0&0&0&2&-2 \end{bmatrix}. $$

Every row sums to zero: the row totals are $-2+2=0$, $1-3+2=0$, $2-4+2=0$, $2-4+2=0$, and $2-2=0$. Thus the displayed rates have the required generator row sums. Here $a=2/1=2$ and $\rho=2/(2\cdot1)=1$. The weights below and at $c$ are $w_0=1$, $w_1=2$, and $w_2=2^2/2!=2$. Above $c$, each weight is multiplied by $\rho=1$, so $w_3=2$ and $w_4=2$.

The normalizer is $Z=1+2+2+2+2=9$. Therefore $$ (\pi_0,\pi_1,\pi_2,\pi_3,\pi_4)=\left(\frac19,\frac29,\frac29,\frac29,\frac29\right). $$

Check: The probabilities sum to $(1+2+2+2+2)/9=1$. The flow from state $0$ to $1$ is $(1/9)2=2/9$, equal to the reverse flow $(2/9)1=2/9$. From $1$ to $2$, the upward flow is $(2/9)2=4/9$, equal to $(2/9)2=4/9$ downward. From $2$ to $3$, both flows are $(2/9)2=4/9$, and from $3$ to $4$, both are also $(2/9)2=4/9$. These adjacent-flow equalities verify $\pi Q=0$.

Worked Example: A Queue with a Declining Weight Above Two Servers

Take $c=2$, $K=3$, $\lambda=1$, and $\mu=2$. The generator is $$ Q= \begin{bmatrix} -1&1&0&0\\ 2&-3&1&0\\ 0&4&-5&1\\ 0&0&4&-4 \end{bmatrix}. $$

Its row totals are $-1+1=0$, $2-3+1=0$, $4-5+1=0$, and $4-4=0$. Here $a=1/2$ and $\rho=1/(2\cdot2)=1/4$. The weights are $w_0=1$, $w_1=1/2$, and $w_2=(1/2)^2/2!=1/8$. The remaining weight is $w_3=(1/8)(1/4)=1/32$. Hence $$ Z=1+\frac12+\frac18+\frac1{32} =\frac{32+16+4+1}{32} =\frac{53}{32}. $$ Dividing each weight by $Z$ gives $$ (\pi_0,\pi_1,\pi_2,\pi_3)=\left(\frac{32}{53},\frac{16}{53},\frac4{53},\frac1{53}\right). $$

Check: The probabilities sum to $(32+16+4+1)/53=1$. Across the first edge, the upward flow is $(32/53)1=32/53$, and the downward flow is $(16/53)2=32/53$. Across the second edge, the flows are $(16/53)1=16/53$ and $(4/53)4=16/53$. Across the last edge, they are $(4/53)1=4/53$ and $(1/53)4=4/53$. All adjacent flows agree.

Worked Example: Capacity Equal to the Number of Servers

Suppose $c=K=3$, $\lambda=3$, and $\mu=1$. There is no state above $c$. The generator on states $0,1,2,3$ is $$ Q= \begin{bmatrix} -3&3&0&0\\ 1&-4&3&0\\ 0&2&-5&3\\ 0&0&3&-3 \end{bmatrix}. $$

The row totals are $-3+3=0$, $1-4+3=0$, $2-5+3=0$, and $3-3=0$. With $a=3/1=3$, the weights are $w_0=1$, $w_1=3$, $w_2=3^2/2!=9/2$, and $w_3=3^3/3!=27/6=9/2$. The normalizer is $Z=1+3+9/2+9/2=13$. Thus $$ (\pi_0,\pi_1,\pi_2,\pi_3)=\left(\frac1{13},\frac3{13},\frac9{26},\frac9{26}\right). $$

Check: In denominator $26$, the probabilities sum to $2/26+6/26+9/26+9/26=26/26=1$. The flows across the three edges match: $(1/13)3=3/13$ and $(3/13)1=3/13$; $(3/13)3=9/13$ and $(9/26)2=9/13$; $(9/26)3=27/26$ and $(9/26)3=27/26$.

What Changes at the Server Threshold

The transition from factorial weights to geometric weights is a direct consequence of the service mechanism, not a change in the arrival process. For $n<c$, adding a customer increases the number of busy servers by one, and the departure rate from the new state is $(n+1)\mu$. For $n\ge c$, all servers are already busy, so the departure rate from the new state is $c\mu$, no matter how many customers are waiting. The stationary weight ratio consequently changes from $a/(n+1)$ to the constant $\rho$.

A common mistake is to continue the factorial formula above $c$, as if the service rate increased with every customer in the system. In the first example, this incorrect rule would assign $w_3=a^3/3!=8/6=4/3$ and $w_4=a^4/4!=16/24=2/3$, instead of the correct weights $2$ and $2$. The incorrect weights sum to $1+2+2+4/3+2/3=7$, but normalization cannot fix the error: across the edge from $2$ to $3$, the unnormalized upward flow would be $2\cdot2=4$, while the downward flow would be $(4/3)\cdot2=8/3$. The correct weights satisfy equal flows because above $c$ the departure rate is capped at $c\mu$, not increased to $n\mu$.

Once the weights are established, normalization is the only remaining step. For example, the geometric part of $Z$ can be written as $\sum_{r=0}^{K-c}\rho^r=(1-\rho^{K-c+1})/(1-\rho)$ when $\rho\ne1$, and as $K-c+1$ when $\rho=1$. Both expressions concern a finite sum; no stability condition for an infinite-capacity queue is needed. If $\lambda=0$, the chain is not irreducible and the stationary distribution is concentrated at state $0$; the theorem above uses $\lambda>0$ so that all states communicate and its uniqueness proof applies.

Check Your Understanding

Use the adjacent-flow recursion and normalize your weights before checking each answer.

For $c=1$, $K=2$, $\lambda=1$, and $\mu=1$, find the three stationary probabilities.
For $c=2$ and $K=4$, which departure rate applies in state $4$, and why does it not equal $4\mu$?
If $c=2$, $K=3$, $\lambda=2$, and $\mu=1$, calculate $a$, $\rho$, and the unnormalized weight $w_3$.
Explain why the second sum in $Z$ contains $K-c+1$ terms, including the state $c$.
For a finite birth-death chain, explain how equal flow across each adjacent pair implies the stationarity equations at the boundary and interior states.

Stationary Probabilities for the M/M/c/K Queue

What You'll Learn