Queue-Length Tails in the M/M/c Queue

From Waiting Customers to System Size

In an M/M/c queue, the number of customers in the system includes both those receiving service and those waiting. A question about waiting customers must therefore be translated into a threshold for the total number in the system. In stationarity, the probabilities above the point where all servers are occupied decrease geometrically. This makes tail probabilities straightforward to calculate once the probability of delay and the server utilization are known.

Consider an M/M/c queue on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with arrival rate \(\lambda>0\), \(c\ge1\) servers, and independent exponential service times of rate \(\mu>0\) at each server. Let \(L_t\in\{0,1,2,\ldots\}\) be the number of customers in the system at time \(t\). When \(L_t=n\), the total service-completion rate is \(\min(n,c)\mu\). Define the offered load \(a=\lambda/\mu\) and the utilization \(\rho=\lambda/(c\mu)=a/c\). A stationary distribution exists when \(\rho<1\), or equivalently \(\lambda<c\mu\). Write \(p_n=\mathbb{P}(L_t=n)\) when the process is in stationarity.

The number waiting, not counting customers in service, is \(Q_t=(L_t-c)^+=\max(L_t-c,0)\). Thus, for an integer \(r\ge1\), at least \(r\) customers are waiting exactly when \(L_t\ge c+r\). This threshold is the key to using the stationary tail correctly.

This is the stationary distribution for the birth-death process with birth rate \(\lambda\) and death rate \(\min(n,c)\mu\) in state \(n\). It can be checked from the adjacent balance equations: for \(n<c\), \(p_n\lambda=p_{n+1}(n+1)\mu\); for \(n\ge c\), \(p_n\lambda=p_{n+1}c\mu\). The displayed normalization makes the probabilities sum to one. The stationary distribution and the Erlang C delay probability are the relevant earlier results; here the focus is how their geometric tail answers waiting-customer questions.

The Tail Formula

Let \(C\) denote the Erlang C delay probability, namely the stationary probability that an arriving customer must wait. For Poisson arrivals, arrivals see the stationary time probabilities, so \(C=\mathbb{P}(L_t\ge c)\) at a stationary time. From the stationary distribution, this is also the probability that all \(c\) servers are busy. Summing the geometric tail gives \(C=p_c/(1-\rho)\).

Proof. Assume the queue is in stationarity and \(\rho<1\). By definition, \(Q_t=(L_t-c)^+\), so for \(r\ge1\), the event \(\{Q_t\ge r\}\) equals \(\{L_t\ge c+r\}\). The stationary distribution gives \(p_{c+j}=p_c\rho^j\) for each integer \(j\ge0\). Therefore, using the convergent geometric series,

The same sum starting at \(j=0\) gives \(\mathbb{P}(L_t\ge c)=p_c/(1-\rho)=C\). Substituting this identity into the preceding expression yields \(C\rho^r\). If \(r=0\), every possible queue length is nonnegative, so the probability is one, not \(C\). \(\square\)

A related interpretation follows by conditioning on all servers being busy. For every integer \(r\ge0\),

Indeed, for \(r=0\) the conditional probability is one. For \(r\ge1\), its numerator is \(C\rho^r\) by the theorem, and its denominator is \(C>0\). Hence the conditional number waiting has probabilities \(\mathbb{P}(Q_t=j\mid L_t\ge c)=(1-\rho)\rho^j\) for integers \(j\ge0\): subtract the tail at \(j+1\) from the tail at \(j\). This describes the queue size conditional on congestion; it does not say that the unconditional queue length is geometric, because the queue also has positive probability of having fewer than \(c\) customers.

Reading and Using the Result

The formula separates the tail into two factors. Erlang C, \(C\), is the probability that the queue is in the all-servers-busy region; \(\rho^r\) is the additional geometric reduction for requiring at least \(r\) customers to be waiting. For example, conditional on all servers being busy, requiring one more waiting customer multiplies the tail probability by \(\rho\). Requiring each additional waiting customer contributes another factor of \(\rho\).

This relationship is useful when answering a specific capacity or service-level question about queue length. Once \(C\) and \(\rho\) are available, the positive-threshold tail can be computed without summing a long list of state probabilities. It also shows why high utilization matters: as \(\rho\) approaches one from below, successive tail probabilities decay more slowly. The stability condition remains essential. If \(\rho\ge1\), the geometric weights from \(n=c\) onward do not have a finite sum, so there is no normalized stationary distribution of this form and no stationary tail probability to calculate.

Common mistake: shifting the exponent by one. In the first example, at least two waiting customers means at least \(c+2=4\) customers in the system. The correct probability is \(C\rho^2=(1/3)(1/2)^2=1/12\). A common incorrect calculation is \(C\rho^{2-1}=(1/3)(1/2)=1/6\), which is actually the probability of at least one waiting customer. The correction is to translate the waiting threshold first: \(Q_t\ge r\) means \(L_t\ge c+r\), so the exponent is \(r\), not \(r-1\).

Another error is to use \(\lambda/\mu\) as the utilization. That ratio is the offered load \(a\); utilization per server is \(\rho=\lambda/(c\mu)\). They are not interchangeable. In the three-server example, \(a=2\) while \(\rho=2/3\); using \(a\) as the geometric ratio would incorrectly produce a growing tail instead of a summable one.