Lesson 23: Birth–Death Processes and Steady-State Balance Equations¶
23.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Define a birth–death process and draw its rate-transition diagram.
- Write the balance equations from a diagram, using both the node method and the cut method.
- Derive the general steady-state solution \(P_n = P_0\prod_{k=0}^{n-1}\dfrac{\lambda_k}{\mu_{k+1}}\).
- State and apply the ergodicity condition that guarantees a steady state exists.
- Specialise the general result to \(M/M/1\), \(M/M/\infty\), discouraged arrivals and the machine-repair model.
23.2 Why One Framework Covers Every Queue¶
Lesson 21 described queues qualitatively and Lesson 22 established that Poisson arrivals and exponential service make the system Markovian. This hour builds the single mathematical engine that produces every formula in Lessons 24–29. Rather than deriving \(M/M/1\), then \(M/M/1/N\), then \(M/M/c\) from scratch, we derive one result and then substitute different rate functions.
That is the real payoff of the Markov assumption: a queue whose arrival and service rates may depend on the current number in the system is still completely described by a one-dimensional chain.
The definition¶
Definition (Birth–death process). A continuous-time Markov chain on the states \(\{0,1,2,\dots\}\) is a birth–death process if from state \(n\) the only permitted transitions are to \(n+1\) (a birth, at rate \(\lambda_n\)) and to \(n-1\) (a death, at rate \(\mu_n\), defined for \(n\ge 1\) with \(\mu_0 = 0\)).
The state \(n\) is the number of customers in the system — those waiting plus those in service. The defining restriction is that the state changes by one unit at a time. This is precisely the orderliness axiom of Lesson 22: two events cannot occur simultaneously.
The rate-transition diagram¶
lam_0 lam_1 lam_2 lam_3
(0) ------> (1) ------> (2) ------> (3) ------> ...
<------ <------ <------ <------
mu_1 mu_2 mu_3 mu_4
Each circle is a state; each arrow carries a rate, not a probability. Rates have units of "events per unit time" and may exceed 1.
Reading the diagram is the whole skill. Almost every queuing model in this course is obtained by choosing \(\lambda_n\) and \(\mu_n\) and turning the crank.
| Model | \(\lambda_n\) | \(\mu_n\) |
|---|---|---|
| \(M/M/1\) | \(\lambda\) for all \(n\) | \(\mu\) for all \(n\ge1\) |
| \(M/M/1/N\) | \(\lambda\) for \(n<N\), else \(0\) | \(\mu\) for all \(n\ge1\) |
| \(M/M/c\) | \(\lambda\) for all \(n\) | \(n\mu\) for \(n<c\), else \(c\mu\) |
| \(M/M/\infty\) | \(\lambda\) for all \(n\) | \(n\mu\) |
| Discouraged arrivals | \(\lambda/(n+1)\) | \(\mu\) |
| Machine repair (\(M\) machines) | \((M-n)\lambda\) for \(n<M\) | \(\mu\) |
23.3 The Balance Equations¶
The steady state¶
Let \(P_n(t)\) be the probability of being in state \(n\) at time \(t\). In steady state (also called statistical equilibrium) these probabilities settle to constants \(P_n\) with \(\dfrac{dP_n}{dt}=0\).
Warning. Steady state does not mean the queue length stops changing. The queue keeps fluctuating; what stops changing is the probability distribution of its length. A steady-state analysis tells you nothing about the transient rush in the first few minutes after opening.
The node (global balance) equations¶
Principle of balance. In steady state, the rate of flow into any state equals the rate of flow out of it.
Consider state \(n\ge1\). Flow enters from \(n-1\) (rate \(\lambda_{n-1}P_{n-1}\)) and from \(n+1\) (rate \(\mu_{n+1}P_{n+1}\)). Flow leaves at rate \((\lambda_n+\mu_n)P_n\). Hence
and, for the boundary state \(0\) (which has no death transition),
The cut (detailed balance) equations — the shortcut¶
Equation (2.1) is a three-term recurrence and is awkward. There is a far better route.
Imagine cutting the diagram with a vertical line between state \(n\) and state \(n+1\). Because the process moves one step at a time, every crossing from left to right must eventually be matched by a crossing from right to left. In steady state the two flow rates must be equal:
This is a two-term recurrence and solves immediately. Equation (2.3) is called the detailed balance or cut equation.
Why the cut method is legitimate. Adding (2.2) to (2.1) for \(n=1\) gives \(\lambda_1 P_1 = \mu_2 P_2\); induction then yields (2.3) for every \(n\). The three-term equations are implied by the two-term ones, so nothing is lost. Always use cuts.
23.4 The General Solution¶
Apply (2.3) repeatedly starting from \(P_0\):
Theorem (General birth–death solution). $\(P_n = P_0\prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}, \qquad n\ge 1 \tag{3.1}\)$ with \(P_0\) fixed by the normalisation \(\displaystyle\sum_{n=0}^{\infty}P_n = 1\), giving $\(P_0 = \left[1+\sum_{n=1}^{\infty}\ \prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}\right]^{-1}. \tag{3.2}\)$
Write \(C_n = \prod_{k=0}^{n-1}\lambda_k/\mu_{k+1}\) (with \(C_0=1\)); then \(P_n = C_nP_0\) and \(P_0 = 1/\sum_n C_n\). Every queuing formula in this unit is (3.1) and (3.2) with a particular \(C_n\).
Ergodicity — when does a steady state exist?¶
Ergodicity condition. A steady-state distribution exists iff the series \(\sum_{n=0}^{\infty}C_n\) converges.
If the series diverges, (3.2) forces \(P_0=0\), which means the queue length drifts to infinity: the system is unstable. For \(M/M/1\), \(C_n=\rho^n\) and the geometric series converges iff \(\rho = \lambda/\mu < 1\) — the familiar stability condition, now seen as a special case.
Three consequences worth remembering:
- A finite-capacity queue is always ergodic: the sum has finitely many terms, so it always converges. \(M/M/1/N\) is stable even when \(\lambda>\mu\) — arrivals are simply turned away.
- \(M/M/\infty\) is always ergodic: \(C_n=(\lambda/\mu)^n/n!\) sums to \(e^{\lambda/\mu}\) for any load.
- \(\rho = 1\) exactly is unstable for \(M/M/1\): the queue grows without bound, just more slowly than when \(\rho>1\). There is no such thing as running a single-server queue "at exactly 100 %".
The performance measures¶
Once \(\{P_n\}\) is known, everything else follows:
and Little's law converts stock to time:
Use \(\lambda_{\text{eff}}\), not \(\lambda\). When arrivals can be blocked or discouraged, the rate that actually enters the system is \(\lambda_{\text{eff}}\), and that is the rate Little's law requires. Using the nominal \(\lambda\) here is the single most common error in this topic.
23.5 Solved Problems¶
Problem 1 — Balance equations for a finite chain¶
A system has states \(0,1,2,3\) with birth rates \(\lambda_0=3\), \(\lambda_1=2\), \(\lambda_2=1\) per hour and death rates \(\mu_1=\mu_2=\mu_3=4\) per hour. Find \(P_n\), \(L_s\), \(L_q\), \(\lambda_{\text{eff}}\), \(W_s\) and \(W_q\).
Solution.
Step 1 — cut equations.
Step 2 — normalise.
Step 3 — measures.
Step 4 — Little's law.
Check. Throughput must also equal \(\mu(1-P_0)=4\left(1-\tfrac{32}{71}\right)=4\cdot\tfrac{39}{71}=\tfrac{156}{71}\) ✓. The server is busy a fraction \(1-P_0=0.5493\) of the time.
Note \(\lambda_{\text{eff}}=2.197 < \lambda_0=3\): because arrivals slow as the system fills, more than a quarter of the nominal demand never materialises.
Problem 2 — Recovering M/M/1¶
Show that constant rates \(\lambda_n=\lambda\), \(\mu_n=\mu\) reproduce the geometric distribution, and state the stability condition.
Solution. Here \(C_n=\prod_{k=0}^{n-1}\lambda/\mu=(\lambda/\mu)^n=\rho^n\). So
Therefore \(P_0=1-\rho\) and
a geometric distribution with parameter \(\rho\). The mean is
The series diverges for \(\rho\ge1\), giving the stability condition \(\rho<1\), i.e. \(\lambda<\mu\). Lesson 24 develops this model fully.
Problem 3 — M/M/∞: unlimited servers¶
Every arriving customer is served immediately, so with \(n\) customers present there are \(n\) busy servers: \(\lambda_n=\lambda\), \(\mu_n=n\mu\). Find the distribution and \(L_s\) when \(\lambda=6\)/h and \(\mu=3\)/h.
Solution.
The number in the system is Poisson with mean \(a=\lambda/\mu\). Hence
Numerically \(P_0=e^{-2}=0.1353\), \(P_1=2e^{-2}=0.2707\), \(P_2=2e^{-2}=0.2707\).
Observation. The series \(\sum a^n/n!\) converges for every \(a\), so \(M/M/\infty\) is stable at any load — there is no \(\rho<1\) condition. This is the natural model for self-service systems (a supermarket's aisles, a website's connections) where "service" needs no scarce server.
Problem 4 — Discouraged arrivals¶
Customers who see a long queue balk, so \(\lambda_n = \dfrac{\lambda}{n+1}\) while \(\mu_n=\mu\). With \(\lambda=8\)/h and \(\mu=4\)/h, find \(P_0\), \(L_s\) and \(\lambda_{\text{eff}}\).
Solution.
Remarkably this is the same \(C_n\) as \(M/M/\infty\), so again the state distribution is Poisson with mean 2:
But the two systems differ where it matters. Here there is only one server, so
using the fact that in steady state throughput in = throughput out = \(\mu\Pr[\text{busy}]\).
Interpretation. Note \(\lambda=8 > \mu=4\): a plain \(M/M/1\) queue would be unstable. Discouragement stabilises it, because arrivals throttle themselves as congestion builds. Only \(3.46\) of the \(8\) customers per hour are actually served — the other \(4.54\) balk. Balking is a hidden loss that never appears in a queue-length statistic.
Problem 5 — The machine-repair (finite-source) model¶
A workshop has \(M=4\) machines and one repairman. Each running machine breaks down at rate \(\lambda=0.1\) per hour; a repair takes an exponential time with mean \(2\) hours (\(\mu=0.5\)/h). Find the distribution of broken machines, the expected number running, the repairman's utilisation and the average downtime per machine.
Solution.
Step 1 — rates. With \(n\) machines broken, \(M-n\) are running and each can fail, so \(\lambda_n=(M-n)\lambda\) for \(n<M\) and \(\lambda_M=0\). There is one repairman, so \(\mu_n=\mu\).
Step 2 — coefficients. With \(\lambda/\mu = 0.1/0.5 = 1/5\):
| \(n\) | \(C_n\) | value |
|---|---|---|
| 0 | \(1\) | \(1\) |
| 1 | \(4\cdot\frac15\) | \(0.8\) |
| 2 | \(4\cdot3\cdot\frac1{25}\) | \(0.48\) |
| 3 | \(4\cdot3\cdot2\cdot\frac1{125}\) | \(0.192\) |
| 4 | \(4!\cdot\frac1{625}\) | \(0.0384\) |
Step 3 — measures.
Interpretation. Of the \(3.30\) hours a broken machine is down, only \(2\) hours are actual repair; the other \(1.30\) hours are spent waiting for the repairman. Downtime is \(65\,\%\) longer than repair time even though the repairman is idle \(40\,\%\) of the time — the standard, and deeply counter-intuitive, lesson of queuing theory.
Why the finite-source model is different. Here \(\lambda_n\) falls as the queue grows, because broken machines cannot break again. The population is its own regulator, so the system can never be unstable. Applying the ordinary \(M/M/1\) formula with \(\lambda=4(0.1)=0.4\) would give \(L_s=\rho/(1-\rho)=4\) broken machines — four times the truth. Never use an infinite-source formula on a small finite population.
23.6 Practice Problems¶
- A birth–death process has \(\lambda_0=2,\lambda_1=1\) and \(\mu_1=\mu_2=3\) (states \(0,1,2\)). Find \(P_0,P_1,P_2\) and \(L_s\). (Answer: \(P_0=\tfrac{9}{17}, P_1=\tfrac{6}{17}, P_2=\tfrac{2}{17}\); \(L_s=\tfrac{10}{17}=0.5882\))
- For \(M/M/1\) with \(\lambda=5\)/h, \(\mu=8\)/h, use (3.1) to find \(\Pr[n\ge2]\). (Answer: \(\rho^2=0.3906\))
- In a two-server system with \(\lambda_n=\lambda=4\) and \(\mu_n=\min(n,2)\mu\) with \(\mu=3\), compute \(C_0,C_1,C_2,C_3\) and \(P_0\). (Answer: \(1,\ \tfrac43,\ \tfrac89,\ \tfrac{16}{27}\); \(P_0=0.2\))
- Repeat Problem 5 with two repairmen (\(\mu_n=\min(n,2)\mu\)). Does the average downtime fall by half? (Answer: \(L_s=0.6896\), \(W_s=2.083\) h — a \(36.8\,\%\) cut, not \(50\,\%\))
- Show that for discouraged arrivals with \(\lambda_n=\lambda/(n+1)\), the system is stable for every \(\lambda\), and explain why in one sentence.
23.7 Summary¶
- A birth–death process changes state by one unit at a time; that single restriction is what makes queues solvable.
- Read a queue from its rate diagram. Choosing \(\lambda_n\) and \(\mu_n\) selects the model.
- Use the cut equations \(\lambda_nP_n=\mu_{n+1}P_{n+1}\), never the three-term node equations.
- General solution: \(P_n=P_0\prod_{k=0}^{n-1}\dfrac{\lambda_k}{\mu_{k+1}}\), with \(P_0\) from normalisation. Everything in Lessons 24–29 is a special case.
- Ergodicity = convergence of \(\sum C_n\). Finite capacity and \(M/M/\infty\) are always stable; \(M/M/1\) needs \(\rho<1\) strictly.
- Compute \(L_s\) and \(L_q\) by summation, then convert to times with Little's law using \(\lambda_{\text{eff}}\), not the nominal \(\lambda\).
- Finite-source systems (machine repair) have decreasing \(\lambda_n\) and must never be analysed with infinite-source formulas — the error is large and always optimistic in the wrong direction.
Next lesson: L24 — Model I, \((M/M/1):(\infty/\text{FCFS})\), derived in full.
Practise now: unit3-queue-inventory-lab.html → Birth–Death Builder: enter any
\(\lambda_n\) and \(\mu_n\), see the rate diagram, the balance equations and the resulting distribution.