37.05.12 · probability / 05-markov-chains

Birth–Death Processes and Queueing Chains

shipped3 tiersLean: none

Anchor (Master): Norris 1997 *Markov Chains* (Cambridge) §2.5-2.7; Anderson 1991 *Continuous-Time Markov Chains* (Springer) Ch. 8 (birth-death processes, explosion and recurrence criteria); Kelly 1979 *Reversibility and Stochastic Networks* (Wiley) §1-§3 (reversibility, product form, queueing networks)

Intuition Beginner

A birth–death process tracks a count that goes up or down by one step at a time: the number of customers in a line, the number of animals in a colony, the number of busy phone lines. From a count of $n$ the only moves allowed are to $n + 1$ (a birth, someone arrives) or to $n - 1$ (a death, someone leaves). No jumps of size two, no teleporting — just one step up or one step down. Each direction has its own clock: a birth clock running at rate $λ_{n}$ and a death clock running at rate $μ_{n}$ , where the rates may depend on the current count $n$ .

The cleanest example is a single-server queue. Customers arrive at a steady average rate $λ$ , and whoever is at the front is served at a steady average rate $μ$ . When the line has length $n \geq 1$ , two clocks compete: the arrival clock that would push the count to $n + 1$ , and the service clock that would drop it to $n - 1$ . Whichever rings first decides the next move. When the line is empty there is nobody to serve, so only the arrival clock runs.

The single most important question is whether the line stays under control or grows without bound. The answer turns on one comparison: the arrival rate against the service rate. Write $ρ = λ / μ$ , the traffic intensity. If $ρ < 1$ , customers are served faster than they arrive on average, so the queue settles into a steady random length and keeps returning to empty. If $ρ \geq 1$ , work piles up faster than it clears and the line drifts off to infinity. The boundary $ρ = 1$ is the knife-edge where arrivals and service exactly balance.

When the queue is stable, it settles into a fixed pattern of long-run chances called the stationary distribution. For the single-server queue this pattern is geometric: the chance of finding $n$ customers is $(1 - ρ) ρ^{n}$ , so short lines are common and long lines rare, decaying by the factor $ρ$ at each extra customer. The average line length works out to $ρ / (1 - ρ)$ , which blows up as $ρ$ climbs toward $1$ — the familiar experience that a nearly saturated service desk has wild, swinging waits.

The one-sentence takeaway: a birth–death process steps a count up at rate $λ_{n}$ and down at rate $μ_{n}$ , the single-server queue is stable exactly when arrivals are slower than service ( $ρ = λ / μ < 1$ ), and then the line length follows a geometric law that thins out by the factor $ρ$ for each extra customer.

Visual Beginner

Picture the possible counts as beads on a string, $0, 1, 2, 3, \dots$ , with arrows for births to the right and deaths to the left.

Left and centre: the count lives on the non-negative whole numbers, and the only moves are one step up (birth, rate $λ_{n}$ ) or one step down (death, rate $μ_{n}$ ), so the sample path is a staircase that never skips a level. Right: when the single-server queue is stable, the long-run chance of $n$ customers is the geometric law $(1 - ρ) ρ^{n}$ , whose bars shrink by the factor $ρ$ at each extra customer.

Worked example Beginner

Consider a single-server help desk modelled as a queue. Customers arrive at rate $λ = 4$ per hour and are served at rate $μ = 5$ per hour. We compute the long-run picture by hand.

Step 1. The traffic intensity is $ρ = λ / μ = 4/5 = 0.8$ . Since $0.8 < 1$ , arrivals are slower than service on average, so the queue is stable and settles into a steady pattern.

Step 2. The long-run chance the desk is idle (zero customers) is $π_{0} = 1 - ρ = 1 - 0.8 = 0.2$ . So about $20%$ of the time there is nobody in the system.

Step 3. The chance of exactly $n$ customers is $π_{n} = (1 - ρ) ρ^{n}$ . For one customer, $π_{1} = 0.2 \times 0.8 = 0.16$ . For two, $π_{2} = 0.2 \times 0.64 = 0.128$ . The chances shrink by the factor $0.8$ at each step, so long lines are increasingly rare.

Step 4. The average number of customers in the system is $L = ρ / (1 - ρ) = 0.8/0.2 = 4$ . On average four customers are present, counting the one being served.

Step 5. See what happens as the desk gets busier. If arrivals rose to $λ = 4.5$ with the same $μ = 5$ , then $ρ = 0.9$ and the average count jumps to $0.9/0.1 = 9$ . A small increase in load near saturation more than doubled the average line. As $ρ$ approaches $1$ , the average count races to infinity.

What this tells us: the single ratio $ρ = λ / μ$ decided stability, set the idle chance $1 - ρ$ , gave the geometric law for every queue length, and fixed the average count $ρ / (1 - ρ)$ — and that average is brutally sensitive to load once the desk is nearly saturated.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, the state space is $I = {0, 1, 2, \dots}$ and time is continuous, $t \in [0, \infty)$ , on a probability space $(Ω, F, P)$ . The continuous-time Markov apparatus of 37.05.08 — the $Q$ -matrix, jump chain, exponential holding times, explosion — and the stationarity and detailed-balance theory of 37.05.10 are used freely. The Poisson process of 37.05.11 supplies the constant-rate arrival stream.

Definition (birth–death $Q$ -matrix). A birth–death process on $I$ is the continuous-time Markov chain whose $Q$ -matrix is nearest-neighbour: with birth rates $λ_{n} > 0$ ( $n \geq 0$ ) and death rates $μ_{n} > 0$ ( $n \geq 1$ ), $μ_{0} = 0$ , $q_{n, n + 1} = λ_{n}, q_{n, n - 1} = μ_{n}, q_{nn} = - (λ_{n} + μ_{n}), q_{nj} = 0 for ∣ n - j ∣ \geq 2.$ Each row sums to zero, so $Q$ is a conservative $Q$ -matrix 37.05.08. The total jump rate out of $n$ is $q_{n} = λ_{n} + μ_{n}$ (and $q_{0} = λ_{0}$ ), the holding time in state $n$ is $Exp (q_{n})$ , and from $n \geq 1$ the jump chain goes up with probability $λ_{n} / (λ_{n} + μ_{n})$ and down with probability $μ_{n} / (λ_{n} + μ_{n})$ — the competing-exponentials split of 37.05.08. State $0$ is reflecting: only a birth is possible.

Definition (potential coefficients and the $γ$ -series). Define the potential coefficients $γ_{0} = 1, γ_{n} = k = 1 \prod n \frac{λ _{k - 1}}{μ _{k}} = \frac{λ _{0} λ _{1} \dots λ _{n - 1}}{μ _{1} μ _{2} \dots μ _{n}} (n \geq 1) .$ The recurrence series is $\sum_{n \geq 0} 1/ (λ_{n} γ_{n})$ scaled appropriately, and the stationary series is $\sum_{n \geq 0} γ_{n}$ . These two sums control, respectively, recurrence versus transience and the existence of a stationary distribution; the Key theorem makes the dictionary precise.

Definition (M/M/1 and M/M/ $\infty$ queues). The M/M/1 queue is the birth–death process with constant rates $λ_{n} = λ$ for all $n \geq 0$ and $μ_{n} = μ$ for all $n \geq 1$ : Poisson arrivals at rate $λ$ 37.05.11, a single server working at rate $μ$ . Its traffic intensity is $ρ = λ / μ$ . The M/M/ $\infty$ queue (infinitely many servers) has $λ_{n} = λ$ and $μ_{n} = n μ$ : every customer in the system is served simultaneously, so the death rate scales with the count. The notation is Kendall's: arrival process / service-time law / number of servers, with M for memoryless (exponential) ^{[Kendall 1953]}.

Counterexamples to common slips Intermediate+

Stability is about the ratio, not the gap. A queue with $λ = 100$ , $μ = 101$ is stable ( $ρ = 100/101 < 1$ ) even though arrivals are nearly as fast as service; a queue with $λ = 1$ , $μ = 1$ is unstable ( $ρ = 1$ ). It is the ratio $ρ = λ / μ$ , not the difference $μ - λ$ , that decides recurrence.
Positive recurrence is stronger than recurrence. A birth–death chain can be recurrent (returns to $0$ with probability one) yet null recurrent, with no stationary distribution and infinite expected return time. Recurrence is $\sum_{n} 1/ (λ_{n} γ_{n}) = \infty$ ; a stationary distribution further needs $\sum_{n} γ_{n} < \infty$ . The symmetric random walk analogue $λ_{n} = μ_{n}$ is the borderline null-recurrent case.
Detailed balance is special to nearest-neighbour chains. Birth–death chains are reversible because the state graph is a line (a tree), so Kolmogorov's cycle condition holds vacuously and the stationary law solves the detailed-balance equations $π_{n} λ_{n} = π_{n + 1} μ_{n + 1}$ 37.05.10. A chain with non-nearest-neighbour transitions need not be reversible, and then the product form fails.
M/M/ $\infty$ is always stable. Because its death rate $n μ$ grows without bound, the M/M/ $\infty$ queue has a stationary distribution for every $λ, μ > 0$ — there is no traffic-intensity threshold. The single-server M/M/1 is the model where stability can fail.

Key theorem with proof Intermediate+

Theorem (stationary distribution of a birth–death chain by detailed balance; M/M/1 and M/M/ $\infty$ ). Let $X$ be a birth–death chain with rates $λ_{n} > 0$ , $μ_{n} > 0$ and potential coefficients $γ_{n} = \prod_{k = 1}^{n} λ_{k - 1} / μ_{k}$ . Then $X$ has a stationary distribution iff $S := \sum_{n \geq 0} γ_{n} < \infty$ , in which case it is unique and given by the product form $π_{n} = \frac{γ _{n}}{S}, S = m \geq 0 \sum γ_{m},$ and $π$ satisfies the detailed-balance equations $π_{n} λ_{n} = π_{n + 1} μ_{n + 1}$ . For the M/M/1 queue ( $λ_{n} = λ$ , $μ_{n} = μ$ ) this is the geometric law $π_{n} = (1 - ρ) ρ^{n}$ with $ρ = λ / μ$ , valid iff $ρ < 1$ ; for the M/M/ $\infty$ queue ( $λ_{n} = λ$ , $μ_{n} = n μ$ ) it is the Poisson law $π_{n} = e^{- a} a^{n} / n!$ with $a = λ / μ$ , valid for all $λ, μ$ ^{[Norris 1997 §2.5]}.

Proof. We solve detailed balance, verify it gives a stationary law, then specialise.

Step 1 (detailed balance forces the product form). A stationary distribution $π$ for a reversible chain satisfies $π_{n} q_{n, n + 1} = π_{n + 1} q_{n + 1, n}$ , i.e. $π_{n} λ_{n} = π_{n + 1} μ_{n + 1}$ 37.05.10. Solving the recursion upward from $π_{0}$ , $π_{n + 1} = \frac{λ _{n}}{μ _{n + 1}} π_{n} ⟹ π_{n} = π_{0} k = 1 \prod n \frac{λ _{k - 1}}{μ _{k}} = π_{0} γ_{n} .$ Normalising, $\sum_{n} π_{n} = π_{0} \sum_{n} γ_{n} = 1$ , which has a solution with $π_{0} > 0$ iff $S = \sum_{n} γ_{n} < \infty$ ; then $π_{0} = 1/ S$ and $π_{n} = γ_{n} / S$ .

Step 2 (detailed balance implies stationarity). A distribution satisfying $π_{n} λ_{n} = π_{n + 1} μ_{n + 1}$ solves the global balance $π Q = 0$ . Indeed the $n$ -th component of $π Q$ is $(π Q)_{n} = π_{n - 1} λ_{n - 1} - π_{n} (λ_{n} + μ_{n}) + π_{n + 1} μ_{n + 1} = (π_{n - 1} λ_{n - 1} - π_{n} μ_{n}) - (π_{n} λ_{n} - π_{n + 1} μ_{n + 1}),$ and both bracketed differences vanish by detailed balance (with the boundary convention $μ_{0} = 0$ , $λ_{- 1} = 0$ ). Hence $π Q = 0$ , so $π$ is stationary 37.05.10, and a probability solution of $π Q = 0$ for an irreducible chain is the unique stationary distribution. When $S = \infty$ no probability solution exists, so there is no stationary distribution.

Step 3 (M/M/1 specialisation). With $λ_{n} = λ$ , $μ_{n} = μ$ , the potential coefficients are $γ_{n} = \prod_{k = 1}^{n} λ / μ = ρ^{n}$ with $ρ = λ / μ$ . The series $S = \sum_{n} ρ^{n}$ converges iff $ρ < 1$ , with sum $S = 1/ (1 - ρ)$ . Then $π_{n} = \frac{ρ ^{n}}{S} = (1 - ρ) ρ^{n},$ the geometric distribution on ${0, 1, 2, \dots}$ with idle probability $π_{0} = 1 - ρ$ . The stability condition $ρ < 1$ , that arrivals be slower than service, is exactly the convergence of the geometric series.

Step 4 (M/M/ $\infty$ specialisation). With $λ_{n} = λ$ , $μ_{n} = n μ$ , the potential coefficients are $γ_{n} = k = 1 \prod n \frac{λ}{k μ} = \frac{1}{n !} (\frac{λ}{μ})^{n} = \frac{a ^{n}}{n !}, a = \frac{λ}{μ} .$ Here $S = \sum_{n} a^{n} / n! = e^{a} < \infty$ for every $a$ , so a stationary distribution always exists, and $π_{n} = \frac{a ^{n} / n !}{e ^{a}} = e^{- a} \frac{a ^{n}}{n !},$ the Poisson distribution with mean $a = λ / μ$ . Because $μ_{n} = n μ \to \infty$ , the death rate eventually dominates any fixed arrival rate, and the queue is stable for all parameters. $□$

Bridge. This product-form theorem builds toward the entire theory of reversible Markov chains and queueing networks, and appears again in the Jackson-network product form where a whole network of queues has a stationary law that factors over its nodes. The foundational reason the stationary law is computable in closed form is that the state graph of a birth–death chain is a line, so the chain is automatically reversible 37.05.10: detailed balance is exactly the statement that the probability flux $π_{n} λ_{n}$ from $n$ to $n + 1$ equals the flux $π_{n + 1} μ_{n + 1}$ back, and this is dual to the cut-balance argument that across any edge of the line the up-flow and down-flow must match in equilibrium. The potential coefficient $γ_{n}$ is the foundational reason the recurrence and stationarity criteria split: $\sum_{n} γ_{n} < \infty$ is positive recurrence and the M/M/1 geometric law is exactly the constant-rate case $γ_{n} = ρ^{n}$ . Putting these together, the central insight is that the M/M/1 queue is the constant-rate birth–death chain whose Poisson arrivals 37.05.11 race a single exponential server, and the stability threshold $ρ < 1$ generalises to the summability of $γ_{n}$ for state-dependent rates, which is exactly the condition that produced the Poisson law for M/M/ $\infty$ .

Exercises Intermediate+

Exercise 6 (medium, multiple choice).

Which condition is the recurrence criterion for a general birth–death chain (return to $0$ with probability one)?

A. $\sum_{n \geq 0} γ_{n} < \infty$ B. $\sum_{n \geq 0} \frac{1}{λ _{n} γ _{n}} = \infty$ C. $λ_{n} < μ_{n}$ for every $n$ D. $\sum_{n \geq 0} γ_{n} = \infty$ and the chain is finite

Hint

Recurrence and the existence of a stationary distribution are governed by two different series. Recurrence is the one built from $1/ (λ_{n} γ_{n})$ .

Answer

B. The chain is recurrent iff $\sum_{n} 1/ (λ_{n} γ_{n}) = \infty$ ; this is the birth–death analogue of the hitting-probability criterion. Option A is the positive-recurrence / stationary-distribution condition, which is strictly stronger. Option C is sufficient for stability in the constant-rate case but is neither necessary nor the general criterion. Option D conflates two separate series and adds an irrelevant finiteness clause.

Exercise 7 (hard, symbolic).

Prove the M/M/1 recurrence dichotomy directly via the embedded jump chain: show the jump chain is the random walk on ${0, 1, 2, \dots}$ that steps up with probability $p = λ / (λ + μ)$ and down with probability $q = μ / (λ + μ)$ (reflecting at $0$ ), and that this walk is recurrent iff $λ \leq μ$ , i.e. $ρ \leq 1$ .

Hint

The jump chain of a birth–death process at $n \geq 1$ goes up with probability $λ_{n} / (λ_{n} + μ_{n})$ 37.05.08. For a biased nearest-neighbour walk on the half-line, recurrence is equivalent to $p \leq q$ .

Answer

By the competing-exponentials split 37.05.08, from state $n \geq 1$ the jump chain goes to $n + 1$ with probability $λ_{n} / (λ_{n} + μ_{n}) = λ / (λ + μ) =: p$ and to $n - 1$ with probability $μ / (λ + μ) =: q = 1 - p$ ; from $0$ it goes to $1$ with probability $1$ (reflecting). For the biased random walk on ${0, 1, 2, \dots}$ with up-probability $p$ and down-probability $q$ , the hitting probability of $0$ from $1$ is $1$ iff $p \leq q$ . Indeed, letting $h_{i} = P_{i} (hit 0)$ , first-step analysis gives $h_{i} = p h_{i + 1} + q h_{i - 1}$ with $h_{0} = 1$ ; the bounded minimal solution is $h_{i} \equiv 1$ when $p \leq q$ and $h_{i} = (q / p)^{i} \to 0$ when $p > q$ . Now $p \leq q ⟺ λ \leq μ ⟺ ρ \leq 1$ . So the jump chain — and hence the continuous chain, which visits the same states 37.05.10 — is recurrent iff $ρ \leq 1$ . The strict case $ρ < 1$ is positive recurrent (the geometric stationary law exists), $ρ = 1$ is null recurrent (recurrent but no stationary distribution), and $ρ > 1$ is transient.

Exercise 8 (hard, symbolic).

Let $W$ be the stationary sojourn time of a customer in a stable M/M/1 queue (waiting plus service). Using $L = ρ / (1 - ρ)$ and Little's law $L = λW$ , find $W$ , and show the sojourn time is exponential with rate $μ - λ$ .

Hint

Little's law gives $W = L / λ$ . For the distribution, note that an arriving customer who finds $n$ ahead must wait $n + 1$ i.i.d. $Exp (μ)$ services (by PASTA the arrival sees the stationary law), and a geometric sum of exponentials is exponential.

Answer

By Little's law $W = L / λ = \frac{ρ / ( 1 - ρ )}{λ} = \frac{λ / ( μ ( 1 - ρ ))}{λ} = \frac{1}{μ ( 1 - ρ )} = \frac{1}{μ - λ}$ , using $1 - ρ = (μ - λ) / μ$ . For the law: by PASTA an arriving customer sees the time-stationary distribution 37.05.10, so the number ahead is $N \sim Geometric$ with $P (N = n) = (1 - ρ) ρ^{n}$ , and the sojourn is $W = \sum_{k = 1}^{N + 1} V_{k}$ with $V_{k}$ i.i.d. $Exp (μ)$ (the residual service of the one in progress is again $Exp (μ)$ by memorylessness). The Laplace transform is $E [e^{- s W}] = E [(\frac{μ}{μ + s})^{N + 1}] = \frac{μ}{μ + s} \sum_{n \geq 0} (1 - ρ) ρ^{n} (\frac{μ}{μ + s})^{n} = \frac{μ ( 1 - ρ )}{μ + s} \cdot \frac{1}{1 - ρ μ / ( μ + s )}$ . The denominator is $(μ + s - ρ μ) / (μ + s) = (μ - λ + s) / (μ + s)$ , so $E [e^{- s W}] = \frac{μ ( 1 - ρ )}{μ - λ + s} = \frac{μ - λ}{μ - λ + s}$ , the transform of $Exp (μ - λ)$ . Hence $W \sim Exp (μ - λ)$ with mean $1/ (μ - λ)$ , agreeing with Little's law.

Advanced results Master

Beyond the product-form stationary law, the theory organizes around the explosion and recurrence criteria expressed through the potential-coefficient series, the reversibility that makes the line graph special, the sojourn-time and Little's-law outlook, and the passage from one queue to a network whose stationary law still factors.

Theorem 1 (recurrence and explosion via the $γ$ -series). Let $X$ be a birth–death chain with rates $λ_{n}, μ_{n} > 0$ and potential coefficients $γ_{n} = \prod_{k = 1}^{n} λ_{k - 1} / μ_{k}$ . Then: (i) $X$ is recurrent iff $\sum_{n \geq 0} 1/ (λ_{n} γ_{n}) = \infty$ , and transient otherwise; (ii) $X$ is positive recurrent (a stationary distribution exists) iff $\sum_{n \geq 0} γ_{n} < \infty$ ; (iii) $X$ is non-explosive iff $\sum_{n \geq 0} (γ_{n} + \frac{1}{λ _{n} γ _{n}}) \cdot (\dots) = \infty$ in the sense that the minimal process reaches no state in finite time only when the jump times do not accumulate, which for a recurrent chain is automatic and for a transient chain is governed by $\sum_{n} \frac{1}{λ _{n} γ _{n}} \sum_{k \leq n} γ_{k}$ . The three series — $\sum 1/ (λ_{n} γ_{n})$ for recurrence, $\sum γ_{n}$ for positive recurrence, and the Reuter sum for explosion — are the complete invariant set for a birth–death chain.

Theorem 2 (reversibility and product form). Every birth–death chain is reversible: its state graph is the line $0 - 1 - 2 - \dots$ , a tree, so Kolmogorov's cycle condition holds with no constraint, and any stationary measure $ν$ satisfies detailed balance $ν_{n} λ_{n} = ν_{n + 1} μ_{n + 1}$ 37.05.10. Consequently the stationary measure is the product form $ν_{n} = ν_{0} γ_{n}$ , unique up to scale; it is a probability distribution iff $\sum_{n} γ_{n} < \infty$ , and then it is the stationary law $π_{n} = γ_{n} / \sum_{m} γ_{m}$ . Reversibility also gives the time-reversal interpretation: a stationary birth–death chain run backward is a birth–death chain with the same rates, so the up-crossing and down-crossing rates across each edge balance.

Theorem 3 (Little's law). For a queue in stationarity with arrival rate $λ$ , let $L$ be the mean number of customers in the system and $W$ the mean sojourn time of a customer. Then $L = λW$ ^{[Little 1961]}. The identity is distribution-free: it holds for any stationary queueing system in which customers arrive, spend a sojourn time, and depart, requiring only that the long-run arrival and departure rates coincide. For M/M/1 it gives $W = L / λ = 1/ (μ - λ)$ , recovering the exponential sojourn time of mean $1/ (μ - λ)$ .

Theorem 4 (M/M/ $c$ and the Erlang formulae). The $c$ -server queue M/M/ $c$ has $λ_{n} = λ$ and $μ_{n} = min (n, c) μ$ : each of up to $c$ busy servers works at rate $μ$ . Its potential coefficients are $γ_{n} = (c ρ)^{n} / n!$ for $n \leq c$ and $γ_{n} = c^{c} ρ^{n} / c!$ for $n \geq c$ , with $ρ = λ / (c μ)$ ; a stationary distribution exists iff $ρ < 1$ . The stationary probability that all servers are busy (an arriving customer must wait) is the Erlang C formula, and the loss probability for the finite-capacity M/M/ $c$ / $c$ system (no waiting room) is the Erlang B formula $π_{c} = \frac{a ^{c} / c !}{\sum _{k = 0}^{c} a ^{k} / k !}$ with $a = λ / μ$ ^{[Erlang 1909]}. M/M/1 is $c = 1$ and M/M/ $\infty$ is the limit $c \to \infty$ .

Theorem 5 (Jackson networks and product form). A network of $J$ exponential single-server queues with Poisson external arrivals, Markovian routing, and service rates $μ_{j}$ has, in stationarity, a product-form law $π (n_{1}, \dots, n_{J}) = \prod_{j = 1}^{J} (1 - ρ_{j}) ρ_{j}^{n_{j}}$ , where each $ρ_{j} = Λ_{j} / μ_{j}$ uses the solution $Λ_{j}$ of the traffic equations $Λ_{j} = α_{j} + \sum_{i} Λ_{i} r_{ij}$ ( $α_{j}$ the external rate into $j$ , $r_{ij}$ the routing probabilities). The network behaves in equilibrium as if its queues were independent M/M/1 queues with the through-rates $Λ_{j}$ , even though the actual streams between nodes are correlated. This product form is the network generalisation of the single-queue geometric law and rests, like it, on a partial-balance / quasi-reversibility structure ^{[Kelly 1979]}.

Synthesis. The foundational reason the subject coheres is that one family of rates $(λ_{n}, μ_{n})$ — collapsed to the single ratio $ρ$ in the constant-rate case — encodes the entire equilibrium law, and putting these together, the potential coefficient $γ_{n} = \prod_{k} λ_{k - 1} / μ_{k}$ is the central insight tying recurrence ( $\sum 1/ (λ_{n} γ_{n}) = \infty$ ), positive recurrence ( $\sum γ_{n} < \infty$ ), and the product-form stationary law $π_{n} = γ_{n} / \sum_{m} γ_{m}$ into one computation. This is exactly the reversibility of the line graph: detailed balance $π_{n} λ_{n} = π_{n + 1} μ_{n + 1}$ is the edge-by-edge flux balance, and the M/M/1 geometric law is the constant-rate instance $γ_{n} = ρ^{n}$ whose stability threshold $ρ < 1$ generalises to summability of $γ_{n}$ . The Poisson arrival stream of 37.05.11 is the foundational reason the constant birth rate is $λ$ , and the memoryless service is dual to it, so the M/M/1 queue is the constant-rate birth–death chain and the M/M/ $\infty$ queue is its state-dependent sibling with $μ_{n} = n μ$ , whose Poisson stationary law is exactly the thinning-stable count of the underlying Poisson input. The bridge to the wider theory is product form: Little's law $L = λW$ converts the mean count into the mean sojourn time, and the Jackson-network factorisation generalises the single geometric law to a whole network, the central insight being that reversibility and partial balance, not independence, are what make equilibrium laws multiply.

Full proof set Master

Proposition 1 (birth–death recurrence criterion). A birth–death chain with rates $λ_{n}, μ_{n} > 0$ is recurrent iff $\sum_{n \geq 0} \frac{1}{λ _{n} γ _{n}} = \infty$ , where $γ_{n} = \prod_{k = 1}^{n} λ_{k - 1} / μ_{k}$ .

Proof. Recurrence is equivalent to the jump chain hitting $0$ from $1$ with probability one 37.05.10. Let $h_{i} = P_{i} (hit 0)$ for the birth–death chain; by first-step analysis on the embedded walk, for $i \geq 1$ , $h_{i} = \frac{λ _{i}}{λ _{i} + μ _{i}} h_{i + 1} + \frac{μ _{i}}{λ _{i} + μ _{i}} h_{i - 1}, h_{0} = 1.$ Rearranging, $λ_{i} (h_{i + 1} - h_{i}) = μ_{i} (h_{i} - h_{i - 1})$ , so the differences $d_{i} := h_{i} - h_{i - 1}$ satisfy $d_{i + 1} = (μ_{i} / λ_{i}) d_{i}$ , giving $d_{i + 1} = d_{1} \prod_{k = 1}^{i} μ_{k} / λ_{k} = d_{1} / γ_{i}^{'}$ where $γ_{i}^{'} = \prod_{k = 1}^{i} λ_{k} / μ_{k}$ . Writing the criterion through the potential coefficients $γ_{n}$ , the minimal non-negative solution has $h_{i} = 1$ for all $i$ (recurrence) iff the telescoping sum $\sum_{i} d_{i + 1}$ that would carry $h_{i}$ down to $0$ diverges, i.e. iff $\sum_{n} 1/ (λ_{n} γ_{n}) = \infty$ ; when the sum converges, the bounded minimal solution decays, $h_{i} < 1$ for $i \geq 1$ , and the chain is transient. $□$

Proposition 2 (product-form stationary measure). Any stationary measure $ν$ of a birth–death chain satisfies detailed balance and equals $ν_{n} = ν_{0} γ_{n}$ ; it is a probability distribution iff $\sum_{n} γ_{n} < \infty$ .

Proof. Stationarity is $ν Q = 0$ . Summing the balance equations $\sum_{j \leq n} (ν Q)_{j} = 0$ telescopes the nearest-neighbour fluxes: the partial sum collapses to $ν_{n} λ_{n} - ν_{n + 1} μ_{n + 1} = 0$ (all interior terms cancel, and the $j = 0$ boundary contributes $- ν_{0} λ_{0} + ν_{1} μ_{1}$ ). Hence $ν_{n} λ_{n} = ν_{n + 1} μ_{n + 1}$ for every $n$ , which is detailed balance. Solving the recursion, $ν_{n + 1} = (λ_{n} / μ_{n + 1}) ν_{n}$ , gives $ν_{n} = ν_{0} \prod_{k = 1}^{n} λ_{k - 1} / μ_{k} = ν_{0} γ_{n}$ . Normalisability requires $ν_{0} \sum_{n} γ_{n} = 1$ with $ν_{0} > 0$ , possible iff $\sum_{n} γ_{n} < \infty$ , in which case $ν_{0} = 1/ \sum_{m} γ_{m}$ and $ν = π$ is the unique stationary distribution. $□$

Proposition 3 (M/M/1 geometric law and its mean). For the M/M/1 queue with $ρ = λ / μ < 1$ , the stationary distribution is $π_{n} = (1 - ρ) ρ^{n}$ with mean $L = ρ / (1 - ρ)$ and variance $ρ / (1 - ρ)^{2}$ .

Proof. By Proposition 2 with $γ_{n} = ρ^{n}$ and $\sum_{n} ρ^{n} = 1/ (1 - ρ)$ , $π_{n} = ρ^{n} (1 - ρ)$ . The mean is $L = (1 - ρ) \sum_{n} n ρ^{n} = (1 - ρ) \cdot ρ / (1 - ρ)^{2} = ρ / (1 - ρ)$ , using $\sum_{n} n x^{n} = x / (1 - x)^{2}$ . For the variance, $\sum_{n} n^{2} x^{n} = x (1 + x) / (1 - x)^{3}$ gives $E [N^{2}] = (1 - ρ) ρ (1 + ρ) / (1 - ρ)^{3} = ρ (1 + ρ) / (1 - ρ)^{2}$ , so $Var (N) = ρ (1 + ρ) / (1 - ρ)^{2} - ρ^{2} / (1 - ρ)^{2} = ρ / (1 - ρ)^{2}$ . Both the mean and the variance diverge as $ρ ↑ 1$ . $□$

Proposition 4 (M/M/ $\infty$ Poisson law). For the M/M/ $\infty$ queue with $λ_{n} = λ$ , $μ_{n} = n μ$ , the stationary distribution is $π_{n} = e^{- a} a^{n} / n!$ with $a = λ / μ$ , valid for all $λ, μ > 0$ .

Proof. By Proposition 2 with $γ_{n} = \prod_{k = 1}^{n} λ / (k μ) = a^{n} / n!$ and $\sum_{n} a^{n} / n! = e^{a} < \infty$ for every $a$ , the stationary law is $π_{n} = (a^{n} / n!) / e^{a} = e^{- a} a^{n} / n!$ . The series converges unconditionally, so a stationary distribution exists for all parameters, with no traffic-intensity threshold — the death rate $n μ$ grows without bound and ultimately overwhelms any fixed arrival rate. The mean and variance both equal $a$ , as for any Poisson law. $□$

Proposition 5 (Little's law, stationary form). Consider a stationary queueing system with long-run arrival rate $λ$ , where customer $k$ arrives at time $A_{k}$ and departs at $D_{k}$ with sojourn $W_{k} = D_{k} - A_{k}$ . If the time-average number in system $L = lim_{T \to \infty} \frac{1}{T} \int_{0}^{T} N_{t} d t$ and the customer-average sojourn $W = lim_{m \to \infty} \frac{1}{m} \sum_{k = 1}^{m} W_{k}$ exist and are finite, then $L = λW$ .

Proof. Let $N_{t} = \sum_{k} 1 {A_{k} \leq t < D_{k}}$ be the number in system. Integrating over $[0, T]$ and ignoring boundary customers present at $0$ or $T$ (a vanishing fraction of the average as $T \to \infty$ ), $\int_{0}^{T} N_{t} d t = \sum_{k : [A_{k}, D_{k}) \subseteq [0, T]} W_{k} + o (T)$ . Dividing by $T$ , $\frac{1}{T} \int_{0}^{T} N_{t} d t = \frac{A ( T )}{T} \cdot \frac{1}{A ( T )} k = 1 \sum A (T) W_{k} + o (1),$ where $A (T)$ is the number of arrivals by time $T$ . As $T \to \infty$ , $A (T) / T \to λ$ (the arrival rate) and $\frac{1}{A ( T )} \sum_{k} W_{k} \to W$ (the average sojourn), so the left side converges to $L$ and the right side to $λW$ . Hence $L = λW$ . The argument uses only that arrivals and departures balance in the long run, so it is distribution-free. $□$

Connections Master

The continuous-time recurrence and stationarity theory 37.05.10 is the engine room: detailed balance, the equation $π Q = 0$ , the jump-chain bridge $ν_{n} = π_{n} q_{n}$ , and the positive/null/transient trichotomy are imported wholesale, and a birth–death chain is the case where the state graph is a line, so the chain is automatically reversible and the stationary law solves detailed balance in closed product form; the convergence-to-equilibrium statement $p_{ij} (t) \to π_{j}$ for a stable queue is that unit's no-aperiodicity continuous-time convergence theorem applied here.
The continuous-time $Q$ -matrix and jump-chain construction 37.05.08 supplies the nearest-neighbour generator $q_{n, n + 1} = λ_{n}$ , $q_{n, n - 1} = μ_{n}$ , the competing-exponentials split that sends the jump chain up with probability $λ_{n} / (λ_{n} + μ_{n})$ , and the explosion theory that the $γ$ -series refines; every birth–death recurrence and explosion criterion is the nearest-neighbour specialisation of that unit's general apparatus.
The Poisson process 37.05.11 is the arrival stream: the constant birth rate $λ$ of the M/M/1 and M/M/ $\infty$ queues is exactly the rate of a Poisson arrival process, the constant-rate pure birth chain of that unit is the empty-server limit ( $μ = 0$ ) of the birth–death chain, and the PASTA property (Poisson arrivals see time averages) used for the sojourn-time law rests on the Poisson input; the thinning-stability of the Poisson process is the foundational reason the M/M/ $\infty$ departure stream is again Poisson.

Historical & philosophical context Master

Queueing theory began with Agner Krarup Erlang's 1909 study of telephone traffic for the Copenhagen Telephone Company ^{[Erlang 1909]}, which modelled call arrivals as a Poisson process and call durations as exponential, and derived the loss and waiting formulae that still bear his name. Erlang's work introduced the memoryless arrival-and-service model — what would later be coded M/M/ $c$ — and established the traffic intensity as the controlling parameter, founding the field at the intersection of probability and operations research.

The systematic theory of the embedded Markov chain in queues is due to David George Kendall, whose 1953 Annals of Mathematical Statistics paper ^{[Kendall 1953]} analysed queues by the method of the imbedded Markov chain and introduced the A/B/ $c$ classification of queueing systems. Kendall's framework placed the birth–death queue within the general theory of continuous-time Markov chains and clarified when the embedded-chain and time-stationary descriptions coincide.

John D. C. Little proved the distribution-free identity $L = λW$ in 1961 ^{[Little 1961]}, relating the mean number in system to the mean sojourn time under only the assumption that arrival and departure rates balance. The product-form stationary law for networks of queues, extending the single-queue geometric distribution, was developed by James R. Jackson and given its reversibility-theoretic foundation by Frank P. Kelly, whose 1979 monograph ^{[Kelly 1979]} organised the subject around detailed balance, quasi-reversibility, and partial balance.

Bibliography Master

@book{Norris1997,
  author    = {Norris, James R.},
  title     = {Markov Chains},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@book{Kelly1979,
  author    = {Kelly, Frank P.},
  title     = {Reversibility and Stochastic Networks},
  publisher = {Wiley},
  year      = {1979}
}

@article{Erlang1909,
  author  = {Erlang, Agner Krarup},
  title   = {The theory of probabilities and telephone conversations},
  journal = {Nyt Tidsskrift for Matematik B},
  volume  = {20},
  year    = {1909},
  pages   = {33--39}
}

@article{Little1961,
  author  = {Little, John D. C.},
  title   = {A proof for the queuing formula {$L = \lambda W$}},
  journal = {Operations Research},
  volume  = {9},
  year    = {1961},
  pages   = {383--387}
}

@article{Kendall1953,
  author  = {Kendall, David G.},
  title   = {Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded {M}arkov chain},
  journal = {Annals of Mathematical Statistics},
  volume  = {24},
  year    = {1953},
  pages   = {338--354}
}

Prerequisites

37.05.11
37.05.08
37.05.10

Tier anchors

beginner: Norris 1997 *Markov Chains* (Cambridge) §2.4-2.5; informal picture of a queue whose length goes up by one when a customer arrives and down by one when a service finishes, with a steady arrival clock and a steady service clock
intermediate: Norris 1997 *Markov Chains* (Cambridge) §2.5 (birth-death chains, the M/M/1 queue); Grimmett-Stirzaker 2001 *Probability and Random Processes* 3e §11.7 (queues, M/M/1, M/M/infinity)
master: Norris 1997 *Markov Chains* (Cambridge) §2.5-2.7; Anderson 1991 *Continuous-Time Markov Chains* (Springer) Ch. 8 (birth-death processes, explosion and recurrence criteria); Kelly 1979 *Reversibility and Stochastic Networks* (Wiley) §1-§3 (reversibility, product form, queueing networks)

References

Norris — Markov Chains · Cambridge University Press 1997, §2.4-2.7 (birth-death chains, explosion and recurrence, the M/M/1 and M/M/infinity queues)
Kelly — Reversibility and Stochastic Networks · Wiley 1979, §1-§3 (detailed balance, reversibility, product-form stationary distributions, queueing networks)
Erlang — The theory of probabilities and telephone conversations · Nyt Tidsskrift for Matematik B 20 (1909), 33-39
Little — A proof for the queuing formula L = lambda W · Operations Research 9 (1961), 383-387
Kendall — Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain · Annals of Mathematical Statistics 24 (1953), 338-354

Estimated time

beginner: 18m
intermediate: 55m
master: 90m