14.2 Birth–death queues
In a birth–death process the state \(n = 0, 1, 2, \ldots \) jumps to \(n + 1\) at rate \(\lambda _n\) and to \(n - 1\) at rate \(\mu _n\).
Theorem 14.2.1. If \(S = \sum _{n \geq 0}\prod _{k = 1}^n\frac {\lambda _{k - 1}}{\mu _k}\) is finite, the process has the stationary distribution \[ p_n = p_0\prod _{k = 1}^n\frac {\lambda _{k - 1}}{\mu _k}, \qquad p_0 = \frac 1S . \]
Proof. In steady state the rate at which the process crosses from \(n\) to \(n + 1\) equals the rate at which it crosses back, since between two upward crossings of the cut between \(n\) and \(n + 1\) there is exactly one downward crossing. The first rate is \(p_n\lambda _n\) and the second \(p_{n + 1}\mu _{n + 1}\), so \(p_{n + 1} = p_n\lambda _n/\mu _{n + 1}\), and induction gives the product; the probabilities sum to \(1\) when \(p_0 = 1/S\). □
M/M/1. Here \(\lambda _n = \lambda \) and \(\mu _n = \mu \), so \(p_n = (1 - \rho )\rho ^n\), a geometric distribution, for \(\rho < 1\). Then \[ L = \frac \rho {1 - \rho }, \qquad W = \frac L\lambda = \frac 1{\mu - \lambda }, \qquad W_q = W - \frac 1\mu = \frac \rho {\mu - \lambda }, \qquad L_q = \lambda W_q = \frac {\rho ^2}{1 - \rho } . \] The probability that an arrival must wait is \(1 - p_0 = \rho \), and the time in the system is exponential with rate \(\mu - \lambda \). With \(\lambda = 4\) and \(\mu = 5\) an hour: \(\rho = 0.8\), \(L = 4\), \(W = 1\) hour, \(W_q = 48\) minutes, \(L_q = 3.2\) (Software 14.5.1). Since \(L = \rho /(1 - \rho )\), raising the load from \(0.8\) to \(0.9\) doubles the mean number present, and from \(0.9\) to \(0.95\) doubles it again (Figure 14).
M/M/\(c\). With \(c\) servers, \(\mu _n = \min (n, c)\mu \). Writing \(a = \lambda /\mu \) (the offered load, in erlangs) and \(\rho = a/c\), the probability that an arrival must wait is the Erlang C formula \[ C(c, a) = \frac {\dfrac {a^c}{c!(1 - \rho )}}{\displaystyle \sum _{k = 0}^{c - 1}\frac {a^k}{k!} + \frac {a^c}{c!(1 - \rho )}}, \qquad W_q = \frac {C(c, a)}{c\mu - \lambda } . \] Loss systems. If arrivals that find all \(c\) servers busy are lost (M/M/\(c\)/\(c\), as for telephone lines), the fraction lost is the Erlang B formula \(B(c, a) = \dfrac {a^c/c!}{\sum _{k = 0}^ca^k/k!}\), which, remarkably, holds for any service distribution with mean \(1/\mu \).
Example 14.2.2. A bank branch has \(24\) customers an hour, and a teller serves \(10\) an hour on average. With \(3\) tellers (\(\rho = 0.8\)) the probability of waiting is \(0.647\) and the mean wait \(6.5\) minutes; with \(4\), \(0.287\) and \(1.1\) minutes; with \(5\), \(0.11\) and \(0.26\) minutes. If instead each of the \(3\) tellers had a separate queue taking a third of the customers, each would be an M/M/1 queue with \(\lambda = 8\), \(\mu = 10\), and the mean wait would be \(24\) minutes, almost four times as long: pooling servers into one queue keeps none of them idle while customers wait at another (Software 14.5.2).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.