Birth-Death Processes and the M/M/1M/M/1 Queue

From General CTMCs to Birth-Death Processes

A general CTMC can jump between any pair of states. In many applications — population dynamics, queueing systems, inventory models — transitions only occur between adjacent states: the population grows by one (birth) or shrinks by one (death). This restriction simplifies the generator to a tridiagonal matrix and yields closed-form solutions for the stationary distribution. The M/M/1 queue, perhaps the most important model in queueing theory, is a birth-death process with constant birth and death rates.

Definition:

Birth-Death Process

A birth-death process is a CTMC on state space S={0,1,2,…}\mathcal{S} = \{0, 1, 2, \ldots\} whose generator matrix G\mathbf{G} is tridiagonal:

  • From state nn, transitions go only to n+1n+1 (birth) at rate λn\lambda_n or to n−1n-1 (death) at rate μn\mu_n, with μ0=0\mu_0 = 0.
  • The generator has entries: gn,n+1=λn,gn,n−1=μn,gnn=−(λn+μn),gn,j=0 for ∣j−n∣≥2.g_{n,n+1} = \lambda_n, \quad g_{n,n-1} = \mu_n, \quad g_{nn} = -(\lambda_n + \mu_n), \quad g_{n,j} = 0 \text{ for } |j-n| \geq 2.

The transition rate diagram is a chain: 0⇌μ1λ01⇌μ2λ12⇌μ3λ23⋯0 \xrightleftharpoons[\mu_1]{\lambda_0} 1 \xrightleftharpoons[\mu_2]{\lambda_1} 2 \xrightleftharpoons[\mu_3]{\lambda_2} 3 \cdots

,

Theorem: Stationary Distribution of a Birth-Death Process

A birth-death process with rates {λn}n≥0\{\lambda_n\}_{n \geq 0} and {μn}n≥1\{\mu_n\}_{n \geq 1} has a stationary distribution if and only if ∑n=1∞∏k=0n−1λkμk+1<∞.\sum_{n=1}^{\infty} \prod_{k=0}^{n-1} \frac{\lambda_k}{\mu_{k+1}} < \infty. When this holds, the stationary distribution is: πn=π0∏k=0n−1λkμk+1,π0=(1+∑n=1∞∏k=0n−1λkμk+1)−1.\pi_n = \pi_0 \prod_{k=0}^{n-1} \frac{\lambda_k}{\mu_{k+1}}, \qquad \pi_0 = \left(1 + \sum_{n=1}^{\infty} \prod_{k=0}^{n-1} \frac{\lambda_k}{\mu_{k+1}}\right)^{-1}.

The formula comes from detailed balance: the flow out of state nn to n+1n+1 must equal the flow in: πnλn=πn+1μn+1\pi_n \lambda_n = \pi_{n+1} \mu_{n+1}. Solving recursively: πn+1=(λn/μn+1)πn\pi_{n+1} = (\lambda_n/\mu_{n+1})\pi_n, which telescopes to the product formula.

Proof
Establish detailed balance

For a birth-death process, the global balance equation πG=0\boldsymbol{\pi}\mathbf{G} = \mathbf{0} at state nn reads: πn(λn+μn)=πn−1λn−1+πn+1μn+1.\pi_n(\lambda_n + \mu_n) = \pi_{n-1}\lambda_{n-1} + \pi_{n+1}\mu_{n+1}. The detailed balance equations πnλn=πn+1μn+1\pi_n\lambda_n = \pi_{n+1}\mu_{n+1} are sufficient (they imply global balance by telescoping).

Solve the recursion

From πnλn=πn+1μn+1\pi_n\lambda_n = \pi_{n+1}\mu_{n+1}: πn+1=λnμn+1πn\pi_{n+1} = \frac{\lambda_n}{\mu_{n+1}}\pi_n. Iterating: πn=π0∏k=0n−1λkμk+1\pi_n = \pi_0\prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}.

Normalize

∑n=0∞πn=1\sum_{n=0}^{\infty}\pi_n = 1 gives π0(1+∑n=1∞∏k=0n−1λkμk+1)=1\pi_0(1 + \sum_{n=1}^{\infty}\prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}) = 1. The stationary distribution exists iff the sum is finite. ■\blacksquare

,

Example: The M/M/1M/M/1 Queue

Customers arrive at a single-server queue according to a Poisson process with rate λ\lambda. Service times are i.i.d. Exp(μ)(\mu). Find the stationary distribution and the mean number of customers in the system.

Solution
Identify the birth-death rates

This is a birth-death process with λn=λ\lambda_n = \lambda and μn=μ\mu_n = \mu for all nn. The traffic intensity is ρ=λ/μ\rho = \lambda/\mu.

Stationary distribution

∏k=0n−1λkμk+1=(λμ)n=ρn\prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}} = \left(\frac{\lambda}{\mu}\right)^n = \rho^n. The sum ∑n=1∞ρn\sum_{n=1}^{\infty}\rho^n converges iff ρ<1\rho < 1, and in that case: π0=1−ρ,πn=(1−ρ)ρn,n=0,1,2,…\pi_0 = 1 - \rho, \qquad \pi_n = (1-\rho)\rho^n, \quad n = 0, 1, 2, \ldots This is a geometric distribution on {0,1,2,…}\{0,1,2,\ldots\} with parameter ρ\rho.

Mean number in system

L=E[N]=∑n=0∞nπn=(1−ρ)∑n=0∞nρn=ρ1−ρ.L = \mathbb{E}[N] = \sum_{n=0}^{\infty} n\pi_n = (1-\rho)\sum_{n=0}^{\infty}n\rho^n = \frac{\rho}{1-\rho}.ForFor\rho = 0.8::L = 4$ customers on average.

,

Theorem: Little's Law

For any stable queueing system in steady state: L=λW,L = \lambda W, where LL is the mean number of customers in the system, λ\lambda is the arrival rate, and WW is the mean sojourn time (waiting + service).

This holds regardless of the arrival distribution, service distribution, number of servers, or queueing discipline.

Think of a store with λ\lambda customers entering per hour. Each stays for WW hours on average. At any instant, you find L=λWL = \lambda W customers inside. The remarkable feature is that no assumptions are needed about the service mechanism — only steady-state stability (λ<\lambda < service capacity).

Proof
Proof sketch via sample-path argument

Let α(t)\alpha(t) be the cumulative number of arrivals by time tt and δ(t)\delta(t) the number of departures. The number in system is N(t)=α(t)−δ(t)N(t) = \alpha(t) - \delta(t).

The time-average of N(t)N(t): Lˉ=1T∫0TN(t) dt\bar{L} = \frac{1}{T}\int_0^T N(t)\,dt. The integral ∫0TN(t) dt\int_0^T N(t)\,dt equals the total sojourn time of all customers present during [0,T][0,T]. If there are α(T)\alpha(T) arrivals, each with sojourn time WkW_k: ∫0TN(t) dt≈∑k=1α(T)Wk\int_0^T N(t)\,dt \approx \sum_{k=1}^{\alpha(T)} W_k. Dividing: Lˉ≈α(T)T⋅1α(T)∑Wk=λˉ⋅Wˉ\bar{L} \approx \frac{\alpha(T)}{T}\cdot\frac{1}{\alpha(T)}\sum W_k = \bar{\lambda}\cdot\bar{W}. In the limit T→∞T \to \infty: L=λWL = \lambda W. ■\blacksquare

,

Example: M/M/1 Delay Analysis

Packets arrive at a router buffer according to a Poisson process with rate λ=800\lambda = 800 packets/s. The server processes packets at rate μ=1000\mu = 1000 packets/s. Find: (a) the traffic intensity, (b) the mean number of packets in the system, (c) the mean sojourn time (queueing + transmission delay), (d) the mean waiting time in the queue (excluding service).

Solution
(a) Traffic intensity

ρ=λ/μ=800/1000=0.8\rho = \lambda/\mu = 800/1000 = 0.8.

(b) Mean number in system

L=ρ/(1−ρ)=0.8/0.2=4L = \rho/(1-\rho) = 0.8/0.2 = 4 packets.

(c) Mean sojourn time (Little's law)

W=L/λ=4/800=5W = L/\lambda = 4/800 = 5 ms.

(d) Mean waiting time

The mean service time is 1/μ=11/\mu = 1 ms. Wq=W−1/μ=5−1=4W_q = W - 1/\mu = 5 - 1 = 4 ms.

Alternatively, the mean number waiting (in queue, not in service) is Lq=L−ρ=4−0.8=3.2L_q = L - \rho = 4 - 0.8 = 3.2, and by Little's law applied to the queue alone: Wq=Lq/λ=3.2/800=4W_q = L_q/\lambda = 3.2/800 = 4 ms. ✓\checkmark

Example: Sizing a Link for a Delay Constraint

A network link must guarantee a mean packet delay of at most W∗=2W^* = 2 ms. Packets arrive at rate λ=500\lambda = 500 packets/s. What is the minimum required service rate μ\mu?

Solution
Express the constraint

For M/M/1: W=1μ−λW = \frac{1}{\mu - \lambda}. The constraint W≤W∗W \leq W^* gives μ−λ≥1/W∗\mu - \lambda \geq 1/W^*, so μ≥λ+1/W∗\mu \geq \lambda + 1/W^*.

Compute

μ≥500+1/0.002=500+500=1000\mu \geq 500 + 1/0.002 = 500 + 500 = 1000 packets/s. The utilization at the minimum is ρ=500/1000=0.5\rho = 500/1000 = 0.5. Any μ<1000\mu < 1000 would violate the delay constraint.

M/M/1M/M/1 Queue: State Evolution and Stationary Distribution

Simulate an M/M/1 queue: watch the queue length evolve over time (top), compare the empirical distribution with the geometric stationary distribution (bottom). Adjust arrival and service rates.

Parameters
3
5
100
42

Birth-Death Process: Stationary Distribution

Visualize the stationary distribution of a birth-death process with configurable birth and death rate patterns: constant (M/M/1), linear (λn=λ\lambda_n = \lambda, μn=nμ\mu_n = n\mu for M/M/∞\infty), or state-dependent.

Parameters
3
5
20

The M/M/1M/M/1 Queue in Action

An animated visualization of the M/M/1 queue: customers arriving (Poisson), being served (exponential service time), and departing. The queue length process and convergence to the geometric stationary distribution are shown in real time.
M/M/1 queue with ρ=λ/μ<1\rho = \lambda/\mu < 1: arrivals (left), server (center), queue length N(t)N(t) (top right), and histogram converging to (1−ρ)ρn(1-\rho)\rho^n (bottom right).
⚠️Engineering Note

Buffer Sizing in Practice

The M/M/1 model predicts that the mean delay diverges as ρ→1\rho \to 1. In practice, router buffers have finite capacity KK, making the actual model M/M/1/K. The finite buffer caps delay but introduces packet loss when the buffer is full. Network engineers typically size buffers to keep loss probability below 10−610^{-6} at the target utilization. The rule of thumb K≈RTT×C/NK \approx \text{RTT} \times C / \sqrt{N} (where CC is link capacity and NN is the number of flows) has been validated in data center networks and long-haul links.

Practical Constraints
  • •

    Buffer memory is finite and expensive at high speeds (100 Gbps+).

  • •

    Deep buffers increase worst-case delay (bufferbloat).

  • •

    The M/M/1 model underestimates burstiness of real traffic (long-range dependence).

🔧Engineering Note

Little's Law as a Design Tool

Little's law L=λWL = \lambda W is distribution-free: it holds for any stable queue regardless of arrival process, service distribution, or number of servers. This makes it a powerful first-cut design tool:

  • Capacity planning: Given a delay target W∗W^* and known arrival rate λ\lambda, the mean backlog is L=λW∗L = \lambda W^*, which sizes the buffer.
  • Performance measurement: Measure any two of {L,λ,W}\{L, \lambda, W\} and compute the third.
  • Sanity check: If measured LL, λ\lambda, WW violate Little's law, the system is not in steady state (e.g., during overload or warmup).

Common Mistake: Stability Requires ρ<1\rho < 1, Not ρ≤1\rho \leq 1

Mistake:

Assuming the M/M/1 queue has a stationary distribution when ρ=1\rho = 1 (arrival rate equals service rate). Some students plug ρ=1\rho = 1 into L=ρ/(1−ρ)L = \rho/(1-\rho) and get L=∞L = \infty, concluding "the queue works but is very full."

Correction:

When ρ≥1\rho \geq 1, the M/M/1 queue is transient: the queue length drifts to infinity with probability 1 and no stationary distribution exists. The formulas πn=(1−ρ)ρn\pi_n = (1-\rho)\rho^n and L=ρ/(1−ρ)L = \rho/(1-\rho) are only valid for ρ<1\rho < 1. At ρ=1\rho = 1, the queue is a null-recurrent random walk.

Birth-death process

A CTMC on {0,1,2,…}\{0,1,2,\ldots\} where transitions from state nn go only to n+1n+1 (birth, rate λn\lambda_n) or n−1n-1 (death, rate μn\mu_n). The generator is tridiagonal.

Related: Continuous-time Markov chain (CTMC)

Traffic intensity

The ratio ρ=λ/μ\rho = \lambda/\mu for a single-server queue (or ρ=λ/(cμ)\rho = \lambda/(c\mu) for cc servers). The queue is stable iff ρ<1\rho < 1.

Related: Birth-death process

Little's law

The relation L=λWL = \lambda W between mean number in system (LL), arrival rate (λ\lambda), and mean sojourn time (WW). Holds for any stable queue in steady state, regardless of distributions or scheduling.

Related: Traffic intensity

Key Takeaway

The M/M/1 queue is the simplest queueing model and the foundation for all others. Its stationary distribution is geometric: πn=(1−ρ)ρn\pi_n = (1-\rho)\rho^n with ρ=λ/μ<1\rho = \lambda/\mu < 1. The mean number in system is L=ρ/(1−ρ)L = \rho/(1-\rho) and the mean delay is W=1/(μ−λ)W = 1/(\mu-\lambda). Little's law L=λWL = \lambda W connects these quantities and holds for all stable queues.

Continuous-Time Markov ChainsM/M/cM/M/c, M/M/1/KM/M/1/K, and Erlang Models