Deriving the Erlang C Delay Formula

From the Stationary Queue to the Probability of Waiting

In an M/M/c queue, \(c\) identical servers work in parallel. When all servers are occupied, an arriving customer joins the queue; when at least one server is idle, service can begin immediately. The probability that an arrival must wait is therefore connected to the probability that the system contains at least \(c\) customers. The key steps are to obtain that probability from the stationary distribution and to justify why the state seen by a Poisson arrival has the same distribution as the state at an arbitrary time.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_t)_{t\ge0}\) be the continuous-time Markov chain whose state \(X_t=n\) is the number of customers in the system at time \(t\), with state space \(S=\{0,1,2,\ldots\}\). Arrivals form a Poisson process of rate \(\lambda>0\), and each server has independent exponential service times of rate \(\mu>0\). Customers are served in order of arrival. Assume \(c\ge1\) is an integer and \(\lambda<c\mu\), the stability condition for a stationary distribution. Define the offered load \(a=\lambda/\mu\) and utilization \(\rho=\lambda/(c\mu)=a/c\). Thus \(0<a<c\) and \(0<\rho<1\).

From state \(n\), the birth rate is \(\lambda\), and the death rate is \(\min(n,c)\mu\). In generator notation, \(q_{n,n+1}=\lambda\), \(q_{n,n-1}=\min(n,c)\mu\) for \(n\ge1\), and \(q_{n,n}=-\lambda-\min(n,c)\mu\); all other off-diagonal entries are zero. For \(n=0\), the death rate is zero and \(q_{0,0}=-\lambda\). Each generator row sums to zero: its off-diagonal rates sum to \(\lambda+\min(n,c)\mu\), which cancels its diagonal entry. The question is to find the probability that an arrival sees \(X_t\ge c\).

The Stationary Probabilities

Write \(\pi_n=\mathbb{P}(X_t=n)\) when the queue is in stationarity. The stationary birth-death balance across the boundary between states \(n\) and \(n+1\) is \(\pi_n\lambda=\pi_{n+1}\min(n+1,c)\mu\). For \(n<c\), repeated use of this relation gives \(\pi_n=\pi_0a^n/n!\). For \(n\ge c\), the ratio of successive probabilities is \(\lambda/(c\mu)=\rho\), so \(\pi_n=\pi_0(a^c/c!)\rho^{n-c}\). The distinction between the two ranges matters: once all servers are busy, the total service rate stays at \(c\mu\).

Proof. Across the cut separating \(\{0,\ldots,n\}\) from \(\{n+1,n+2,\ldots\}\), the only transitions crossing out are \(n\to n+1\), with stationary rate \(\pi_n\lambda\), and the only transitions crossing in are \(n+1\to n\), with stationary rate \(\pi_{n+1}\min(n+1,c)\mu\). Stationarity makes these rates equal. Starting with \(\pi_0\), this recurrence gives \(\pi_n=\pi_0a^n/n!\) for \(n<c\), because the successive death rates are \(\mu,2\mu,\ldots,c\mu\). For \(n\ge c\), each additional state has probability \(\rho\) times the preceding state's probability, giving the stated geometric form. To normalize, sum the probabilities below \(c\) and then the probabilities from \(c\) onward: \[ 1=\sum_{n=0}^{c-1}\pi_n+\sum_{n=c}^{\infty}\pi_n =\pi_0\sum_{n=0}^{c-1}\frac{a^n}{n!} +\pi_0\frac{a^c}{c!}\sum_{k=0}^{\infty}\rho^k. \] Because \(0<\rho<1\), the geometric series equals \(1/(1-\rho)\), giving the displayed \(\pi_0\). In particular, these probabilities are nonnegative and sum to one. Their sum over \(n\ge c\) is \(\pi_0a^c/[c!(1-\rho)]\). It remains to identify this time-stationary probability with the probability seen by an arrival; that step is justified below. \(\square\)

Why Arrivals See the Stationary Probabilities

It is not true for every arrival process that arrivals see the same state distribution as a randomly selected time. Here it holds because the arrival process is Poisson and its future increments are independent of the queue's history. This property is called PASTA: Poisson Arrivals See Time Averages.

Proof. Let \((\mathcal{F}_t)_{t\ge0}\) contain the queue and service history up to time \(t\). For an interval \((s,u]\), let \(Z\) be a bounded \(\mathcal{F}_s\)-measurable random variable. Independence of Poisson increments from the history up to \(s\) gives \(\mathbb{E}[Z\,A((s,u])]=\mathbb{E}[Z]\lambda(u-s)\), where \(A((s,u])\) is the number of arrivals in that interval. By adding such identities, the same relation holds for processes that are constant on time intervals with values determined by the history at the left endpoint. Approximating a bounded process determined by the history just before each time by these interval processes gives the Poisson sampling identity \[ \mathbb{E}\!\left[\sum_{t:\,\text{arrival},\,0<t\le T}H(t)\right] =\lambda\,\mathbb{E}\!\left[\int_0^T H(t)\,dt\right] \] for bounded predictable \(H(t)\). Take \(H(t)=\mathbf{1}_{\{X_{t-}=n\}}\), which depends only on the state immediately before time \(t\). In stationarity, \(\mathbb{P}(X_{t-}=n)=\pi_n\) for almost every \(t\), so the expected number of arrivals in \((0,T]\) that see state \(n\) is \(\lambda T\pi_n\). The expected total number of arrivals is \(\lambda T\); hence the distribution of the state observed by a Poisson arrival is \(\pi_n\). Summing over \(n\ge c\) proves that the delay probability is \(\sum_{n=c}^{\infty}\pi_n\), which is the formula in the theorem. \(\square\)

The condition “stationary” is important: PASTA identifies the arrival-seen distribution with the time distribution at the same times. If the queue starts empty and has not reached stationarity, the arrival-seen state distribution over an initial time interval need not equal the stationary distribution.

Worked Calculations

Common Errors and the Role of Stability

A frequent error is to use \(a\) as the ratio of successive stationary probabilities throughout the tail. The ratio beyond state \(c\) is \(\lambda/(c\mu)=\rho\), not \(\lambda/\mu=a\): when all servers are busy, the total service rate is \(c\mu\). For example, with \(c=2\) and \(a=1\), incorrectly using \(a=1\) in the tail would give a geometric series \(\sum_{k=0}^{\infty}1^k\), which diverges. The correction is to use \(\rho=1/2\), for which the tail series is \(\sum_{k=0}^{\infty}(1/2)^k=2\).

Another error is to count only the state \(n=c\) as requiring a wait. For \(c=2\), \(a=1\), the stationary probability of exactly two customers is \(\pi_2=1/6\), but states \(3,4,\ldots\) also have all servers occupied. Their total probability is \(1/6\), so the probability of waiting is \(1/6+1/6=1/3\), not \(1/6\).

The stability condition also cannot be dropped. If \(\lambda\ge c\mu\), then \(\rho\ge1\), so the proposed stationary tail sum \(\sum_{k=0}^{\infty}\rho^k\) does not converge. The normalization step fails, and the Erlang C stationary formula does not define a probability distribution. The formula is therefore for a stable queue, not a rule to use at or above capacity.