Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 38 · Basics and Little's Law

Birth-Death Processes

Learn birth-death processes, the balance equations and the product-form solution that give the steady state of M/M/1 and M/M/c queues.

The queues in the next chapters share one structure: the number of customers goes up by one when someone arrives and down by one when someone leaves. A process that changes only by +1 or -1 steps, with rates that depend on the current count, is called a birth-death process. Once you master it, you can derive M/M/1, M/M/c and many other results from a single formula.

The model

Let N(t) be the number of customers at time t. When N = n:

  • a birth (arrival) happens at rate λn, moving to n + 1;
  • a death (departure) happens at rate μn, moving to n - 1 (with μ0 = 0, since nobody can leave an empty system).
flowchart LR
  S0["0"] -- "λ0" --> S1["1"]
  S1 -- "μ1" --> S0
  S1 -- "λ1" --> S2["2"]
  S2 -- "μ2" --> S1
  S2 -- "λ2" --> S3["3"]
  S3 -- "μ3" --> S2

States are customer counts. Arrows carry the rates of moving up and down.

For M/M/1 all λn = λ and μn = μ. For M/M/c the death rate is μn = min(n, c) μ, since at most c servers are busy.

Steady state and balance

If the process settles down, let Pn be the long-run fraction of time spent in state n. In steady state, the flow of probability across any cut between state n - 1 and state n must balance: the rate going up equals the rate going down.

λ(n-1) P(n-1) = μn Pn

This is called a detailed balance or cut equation. Rearranging:

Pn = P(n-1) × λ(n-1) / μn

Applying it repeatedly from P0 gives the product form:

Pn = P0 × (λ0 λ1 ... λ(n-1)) / (μ1 μ2 ... μn)

Finally P0 is found from the requirement that all probabilities sum to 1. The steady state exists only if that sum is finite.

A general solver

The function below builds the product-form probabilities for any rates, truncating the state space at a large N (probabilities beyond it are negligible when the queue is stable). We test it on M/M/1, where we expect L = ρ/(1-ρ) (derived in the next chapter). With ρ = 0.8 that is 4.

Python Product-form solver

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.

A queue where customers get discouraged

Birth-death processes can describe behaviors beyond the textbook. Suppose arrivals are discouraged by a long line: the arrival rate in state n is λn = λ / (n + 1), and a single server works at the constant rate μ. The product form gives

Pn = P0 × (λ/μ)^n / n!

which is a Poisson distribution with mean a = λ/μ. So P0 = e^(-a). Let us check it numerically with a = 2.

Python Discouraged arrivals

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.

Here the system is stable for any λ and μ, because arrivals fade out when the line is long. This shows that the stability condition ρ < 1 is specific to constant arrival rates.

What is next

Almost every queue in this chapter and the next is a birth-death process with particular rates:

Model λn μn
M/M/1 λ μ
M/M/c λ min(n, c) μ
M/M/∞ λ n μ
M/M/1/K λ for n < K, 0 at K μ

In the following lessons you will use the formula to derive closed forms for each.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In a birth-death process, from state n the process can move to which states?

    Births add one customer and deaths remove one, so only neighbors are reachable in one step.
  2. 2. The balance (cut) equation between states n-1 and n is...

    Flow upward across the cut, lambda(n-1) P(n-1), equals flow downward, mu(n) P(n).
  3. 3. For M/M/c, what is the death rate in state n?

    At most c servers can be busy, so the total service rate is min(n, c) times mu.
  4. 4. After computing the unnormalized weights, how do we get the probabilities?

    Probabilities must sum to 1, so we normalize by the total weight.

Summary

  • A birth-death process moves up with rate λn and down with rate μn.
  • Balance across each cut gives λ(n-1) P(n-1) = μn Pn and the product form for Pn.
  • Normalizing fixes P0; the steady state exists only if the sum converges.
  • M/M/1, M/M/c and M/M/∞ are special cases with different rates.

Next: The M/M/1 Steady State