Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 36 · Continuous-Time Markov Chains

Birth-Death Processes

Study birth-death chains where the state moves up or down by one. Derive the product-form stationary distribution and test it on queues and a pure-birth process.

The simplest interesting continuous-time chains move only one step at a time: up by one (a birth) or down by one (a death). Queue lengths, populations, the number of busy lines in a telephone exchange, and the number of molecules of a chemical species all behave this way. They are called birth-death processes, and their stationary distribution has a neat closed form.

Rates

The state n = 0, 1, 2, … is the current population. In state n:

  • A birth moves n → n+1 at rate λₙ (the birth rate).
  • A death moves n → n-1 at rate μₙ (the death rate), with μ₀ = 0.

All other entries of the generator matrix are 0, so Q is tridiagonal:

Text
q_{n,n+1} = λ_n,   q_{n,n-1} = μ_n,   q_{n,n} = -(λ_n + μ_n)

Examples:

  • M/M/1 queue: λₙ = λ (arrivals) and μₙ = μ for n ≥ 1 (one server).
  • Immigration-death: λₙ = a (steady immigration), μₙ = nμ (each individual dies at rate μ).
  • Pure birth (Yule process): λₙ = nλ, no deaths: each individual splits at rate λ.
flowchart LR
  S0["0"] -->|"λ0"| S1["1"]
  S1 -->|"μ1"| S0
  S1 -->|"λ1"| S2["2"]
  S2 -->|"μ2"| S1
  S2 -->|"λ2"| S3["3"]
  S3 -->|"μ3"| S2

A birth-death chain: rates λ move up, rates μ move down.

Detailed balance and the product form

Look at the cut between states n-1 and n. In a stationary chain, the rate of crossing upward must equal the rate of crossing downward:

Text
π_{n-1} λ_{n-1} = π_n μ_n

(this is called detailed balance). Solving step by step gives

Text
π_n = π_0 · (λ_0 λ_1 ... λ_{n-1}) / (μ_1 μ_2 ... μ_n)

and π₀ is fixed by Σ πₙ = 1. A stationary distribution exists only if the sum of these products is finite.

Example, M/M/1: πₙ = π₀ ρⁿ with ρ = λ/μ. If ρ < 1 the sum is 1/(1-ρ), so πₙ = (1-ρ)ρⁿ, a geometric distribution. If ρ ≥ 1 the queue grows without bound and no stationary distribution exists.

Example, immigration-death: πₙ = π₀ (a/μ)ⁿ / n!, a Poisson distribution with mean a/μ.

A solver for finite birth-death chains

For a finite chain 0, …, K the product formula always works. The next program implements it and checks the answer against the general πQ = 0 solve from the previous lesson.

Python Product-form stationary distribution

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two methods give identical vectors. For M/M/1/5 the vector is geometric with ratio 2/3, cut off at 5. The telephone example is the classical Erlang loss model: the last number is the chance that all lines are busy when a call arrives.

A pure birth process: the Yule process

When λₙ = nλ and μₙ = 0, each individual produces a new one at rate λ, independently. Starting from one individual, the population grows exponentially in expectation: E[X(t)] = e^(λt), because d/dt E[X] = λ E[X]. In fact X(t) is geometric with success probability e^(-λt), so Var[X(t)] = e^(2λt) - e^(λt). Pure birth chains have no stationary distribution; they escape to infinity.

Python Simulate the Yule process

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sample mean and variance track the formulas, confirming the geometric law.

Do not assume a stationary distribution exists. For M/M/1 you need ρ < 1, and for pure birth chains there is never one. Always check that the sum of the product weights is finite.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the detailed balance equation across the cut between n-1 and n?

    Upward crossing rate (π_{n-1} λ_{n-1}) equals downward crossing rate (π_n μ_n).
  2. 2. For an M/M/1 queue with λ = 1 and μ = 4, what is P(empty system) in the stationary distribution?

    π₀ = 1 - ρ = 1 - 1/4 = 0.75.
  3. 3. In an immigration-death process with immigration rate a and per-individual death rate μ, what is the stationary distribution?

    π_n ∝ (a/μ)^n / n!, which is Poisson with mean a/μ.
  4. 4. For a Yule process started from one individual with rate λ per individual, what is E[X(t)]?

    d/dt E[X] = λ E[X], so E[X(t)] = e^(λt).

Summary

  • A birth-death process moves one step at a time: up at rate λₙ, down at rate μₙ; its generator is tridiagonal.
  • Detailed balance π_{n-1} λ_{n-1} = πₙ μₙ gives πₙ = π₀ · (λ₀…λ_{n-1}) / (μ₁…μₙ).
  • M/M/1 has geometric stationary law when ρ = λ/μ < 1; immigration-death has a Poisson law; the Erlang loss model gives blocking probabilities.
  • Pure birth chains such as the Yule process grow without a stationary distribution.

Next: Kolmogorov Equations and Transient Behavior