📐 Concept diagram

Phase 11: Probability Theory II

Subject 11-08: Markov Chains (Continuous Time)

Prerequisites: 11-07 (Discrete-Time Markov Chains), 10-05 (Poisson Process), linear algebra (matrix exponentials)

Learning Objectives

1. Define a continuous-time Markov chain (CTMC) with state space S and generator matrix Q
2. Explain the relationship between exponential holding times and the Q-matrix (Q_{ii} = −λ_i, Q_{ij} = λ_i P_{ij})
3. Derive the Kolmogorov forward and backward equations: P'(t) = P(t)Q and P'(t) = QP(t)
4. Solve for transition probabilities using the matrix exponential: P(t) = e^{tQ}
5. Define and compute stationary distributions for CTMCs: πQ = 0

Core Content

1. Definition and Generator Matrix

A continuous-time Markov chain {X(t) : t ≥ 0} with countable state space S evolves as follows:

1. When the chain enters state i, it stays there for an exponentially distributed holding time with rate λ_i (mean 1/λ_i)
2. After the holding time expires, it jumps to state j ≠ i with probability P_{ij} (where Σ_{j≠i} P_{ij} = 1, P_{ii} = 0)

The Generator Matrix Q: The behavior of a CTMC is fully specified by its infinitesimal generator (or Q-matrix):

• Off-diagonal: Q_{ij} = λ_i P_{ij} — the rate of transitioning from i to j (for i ≠ j)
• Diagonal: Q_{ii} = −λ_i = −Σ_{j≠i} Q_{ij} — negative total rate of leaving state i

Properties of Q: 1. Q_{ij} ≥ 0 for i ≠ j (non-negative off-diagonal) 2. Q_{ii} ≤ 0 (non-positive diagonal) 3. Σ_j Q_{ij} = 0 (rows sum to zero — conservative Q-matrix)

⚠️ CRITICAL: Unlike discrete-time where P has rows summing to 1, the Q-matrix has rows summing to 0. Q represents RATES, not probabilities.

Connection to the Poisson process: A Poisson process with rate λ is a CTMC on state space {0, 1, 2, ...} where Q_{i,i+1} = λ, Q_{ii} = −λ, and all other entries are 0.

2. Kolmogorov Equations

Let P_{ij}(t) = P(X(t) = j | X(0) = i) be the transition probability function. Then:

Kolmogorov Backward Equation (KBE):

$P'(t) = Q P(t)    i.e.    P'_{ij}(t) = Σ_k Q_{ik} P_{kj}(t) = −λ_i P_{ij}(t) + Σ_{k≠i} Q_{ik} P_{kj}(t)
$

Kolmogorov Forward Equation (KFE):

P'(t) = P(t) Q    i.e.    P'_{ij}(t) = Σ_k P_{ik}(t) Q_{kj} = −λ_j P_{ij}(t) + Σ_{k≠j} P_{ik}(t) Q_{kj}

Initial condition: P(0) = I (identity matrix — you are where you start).

Intuition: - Backward equation: conditions on the first jump (what happens in the initial infinitesimal interval dt) - Forward equation: conditions on the last jump (what happens just before reaching state j)

Both lead to the same solution:

$P(t) = e^{tQ} = Σ_{n=0}^{∞} (tQ)ⁿ / n!
$

The matrix exponential generalizes the scalar exponential to matrices — it's the unique solution to P'(t) = QP(t) with P(0) = I.

⚠️ Common Pitfall: The forward and backward equations are different! For infinite state spaces, they may not both be valid. The backward equation is more fundamental because it conditions on the initial state, which is always valid. The forward equation requires additional regularity conditions.

3. Birth-Death Processes

A birth-death process is a CTMC on state space {0, 1, 2, ...} (or {0, 1, ..., N}) where transitions can only go to adjacent states:

• Q_{i,i+1} = λ_i (birth rate when population is i)
• Q_{i,i−1} = μ_i (death rate when population is i), with μ₀ = 0
• Q_{ii} = −(λ_i + μ_i)

Examples: - M/M/1 queue: λ_i = λ (constant arrival rate), μ_i = μ (constant service rate). State = number in system. - Pure birth (Yule process): λ_i = iλ (each individual gives birth independently), μ_i = 0. - Population with logistic growth: λ_i = αi, μ_i = βi² (death rate increases with crowding).

Stationary distribution for birth-death: For a general birth-death process, the detailed balance equations give:

π_i λ_i = π_{i+1} μ_{i+1}    (flux from i to i+1 equals flux from i+1 to i)

Solving recursively:

$π_i = π₀ · (λ₀λ₁...λ_{i−1}) / (μ₁μ₂...μ_i)
$

with π₀ chosen so Σ π_i = 1.

For M/M/1 queue: λ_i = λ, μ_i = μ. Then π_i = π₀ (λ/μ)^i. The sum converges iff λ < μ (traffic intensity ρ = λ/μ < 1). Then π₀ = 1 − ρ, π_i = (1−ρ)ρⁱ — a geometric distribution!

If λ ≥ μ, the queue grows without bound — no stationary distribution exists.

4. Stationary Distribution for CTMCs

A probability distribution π is stationary for a CTMC if:

π Q = 0    i.e.    Σ_i π_i Q_{ij} = 0  for all j

Equivalently: for all j, the total rate of leaving j (π_j Σ_{k≠j} Q_{jk}) equals the total rate of entering j (Σ_{i≠j} π_i Q_{ij}):

$π_j Σ_{k≠j} Q_{jk} = Σ_{i≠j} π_i Q_{ij}    (global balance)
$

Detailed balance (sufficient): π_i Q_{ij} = π_j Q_{ji} for all i ≠ j.

Ergodic theorem: For an irreducible, positive recurrent CTMC with stationary distribution π:

$lim_{t→∞} P_{ij}(t) = π_j    (independent of i)
$

and (1/t) ∫₀ᵗ f(X(s)) ds → Σ_i π_i f(i) almost surely.

5. Explosions

A CTMC can "explode" — take infinitely many jumps in finite time. This happens when Σ 1/λ_i < ∞ (the expected time for infinite jumps is finite).

Example: Pure birth process with λ_i = i². Expected time for infinitely many births: E[Σ 1/i²] = π²/6 < ∞, so the chain explodes in finite time!

For most applied models (finite state spaces or bounded rates), explosions don't occur.

Key Terms

• Detailed balance

Worked Examples

Example 1: Two-State CTMC

A machine alternates between working (state 0) and broken (state 1). Working time ~ Exp(λ), repair time ~ Exp(μ). Find: (a) Q-matrix, (b) P(t), (c) stationary distribution.

Solution:

(a) Q = [[−λ, λ], [μ, −μ]].

(b) Solve P'(t) = P(t)Q. The solution is:

$P(t) = 1/(λ+μ) [[μ+λe^{−(λ+μ)t}, λ−λe^{−(λ+μ)t}],
                  [μ−μe^{−(λ+μ)t}, λ+μe^{−(λ+μ)t}]]
$

As t → ∞: P_{ij}(t) → π_j where π₀ = μ/(λ+μ), π₁ = λ/(λ+μ).

(c) Solve πQ = 0: −λπ₀ + μπ₁ = 0, λπ₀ − μπ₁ = 0, π₀+π₁=1 → π₀=μ/(λ+μ), π₁=λ/(λ+μ). Long-run: proportion of time working = μ/(λ+μ). If repair is fast (large μ), availability is high.

Example 2: M/M/1 Queue — Stationary Analysis

Customers arrive at rate λ = 3/hour, served at rate μ = 5/hour (single server, infinite waiting room).

(a) Find the stationary distribution of the number in the system. (b) Expected number in the system. (c) Probability of finding more than 5 customers.

Solution:

(a) ρ = λ/μ = 3/5 = 0.6 < 1 — stationary distribution exists. π_i = (1−ρ)ρⁱ = 0.4(0.6)ⁱ for i = 0, 1, 2, ...

(b) E[N] = ρ/(1−ρ) = 0.6/0.4 = 1.5.

(c) P(N > 5) = 1 − Σ_{i=0}^{5} 0.4(0.6)ⁱ = 1 − 0.4(1−0.6⁶)/(1−0.6) = 1 − (1−0.6⁶) = 0.6⁶ ≈ 0.0467. About 4.7%.

Example 3: Birth-Death — Bacteria Population

Bacteria in a dish: each divides at rate 2 per hour, dies at rate 1 per hour. Start with 1 bacterium. What is the probability of extinction?

Solution:

This is a birth-death with λ_i = 2i, μ_i = 1·i (per capita rates). Per individual: birth rate 2, death rate 1. This is a branching process in disguise. Probability of extinction starting from 1: solve p = μ/(λ+μ) + λ/(λ+μ) p² = 1/3 + (2/3)p². Roots: p = 1/2 or p = 1. The minimal non-negative root is p = 1/2.

With birth rate > death rate, extinction is not certain: P(extinction) = μ/λ = 1/2.

Quiz

Q1: A continuous-time Markov chain (CTMC) is characterized by:

A) A transition probability matrix P B) A generator matrix (rate matrix) Q C) A single transition rate D) Discrete time steps

Correct: B)

• If you chose B: Correct! The generator matrix Q has q_{ij} ≥ 0 for i ≠ j (transition rates) and q_{ii} = −Σ_{j≠i} q_{ij}. P(X(t+h)=j | X(t)=i) ≈ q_{ij}h for small h.
• If you chose A: P is for discrete-time chains; CTMCs use the generator Q.
• If you chose C: Different state pairs can have different transition rates.
• If you chose D: CTMCs evolve in continuous time, not discrete steps.

Q3: In a birth-death process, transitions are only allowed between:

A) Any pair of states B) Neighboring states (i → i+1 or i → i−1) C) States with the same parity D) Absorbing states only

Correct: B)

• If you chose B: Correct! Birth-death processes only allow transitions to adjacent states: λ_i (birth rate from i to i+1) and μ_i (death rate from i to i−1). This models population dynamics.
• If you chose A: This would be a general CTMC, not a birth-death process.
• If you chose C: Parity has nothing to do with birth-death transitions.
• If you chose D: Absorbing states have no outgoing transitions; birth-death processes have both.

Practice Problems

1. For the two-state CTMC with Q = [[−2, 2], [1, −1]], compute P(t) and find lim_{t→∞} P(t).
2. Derive the stationary distribution for the M/M/1 queue using the detailed balance equations.
3. A CTMC has state space {0, 1, 2} and Q = [[−3, 2, 1], [1, −2, 1], [0, 3, −3]]. Find the stationary distribution.
4. Show that for a CTMC, holding time in state i is exponentially distributed with rate −Q_{ii}.
5. Write the Q-matrix for an M/M/2 queue (2 servers, arrival rate λ, service rate μ per server).
6. Verify that P(t) = e^{tQ} satisfies the Kolmogorov backward equation.
7. For a birth-death process with λ_i = λ (constant) and μ_i = iμ, find the stationary distribution. What distribution is this?

Summary

• A CTMC spends Exp(λ_i) time in state i, then jumps to j with probability P_{ij}; the generator Q captures rates: Q_{ij}=λ_i P_{ij} (i≠j), Q_{ii}=−λ_i
• Kolmogorov equations: P'(t) = QP(t) (backward) and P'(t) = P(t)Q (forward), solved by P(t) = e^{tQ}
• Birth-death processes have transitions only to neighbors; detailed balance gives π_i ∝ Π(λ_{k−1}/μ_k); M/M/1 queue has geometric stationary distribution when ρ = λ/μ < 1
• Stationary distribution satisfies πQ = 0 (global balance); detailed balance π_i Q_{ij} = π_j Q_{ji} is sufficient
• Explosions (infinite jumps in finite time) occur when Σ 1/λ_i < ∞; avoided in bounded-rate systems

Pitfalls

• Confusing Q-matrix and P-matrix row sums: In discrete time, P has rows summing to 1. In continuous time, Q has rows summing to 0 (rates in = rates out). Treating Q entries as probabilities (e.g., reading Q_{ij} directly as P(X(t+dt)=j | X(t)=i)) is wrong — they must be multiplied by dt.
• Forgetting that holding times are exponential: In a CTMC, the time spent in state i is Exp(−Q_{ii}), not geometric or arbitrary. The memoryless property of the exponential distribution is what makes CTMCs Markovian. Using the wrong holding-time distribution breaks the Markov property.
• Mixing up forward and backward Kolmogorov equations: Backward: P'(t) = QP(t); Forward: P'(t) = P(t)Q. They look similar but differ in whether Q multiplies on the left or right. For infinite state spaces, the forward equation may not hold without additional regularity conditions — the backward equation is more fundamental.
• Assuming a stationary distribution always exists: For the M/M/1 queue, π exists only when ρ = λ/μ < 1. When λ ≥ μ, the queue grows without bound and no stationary distribution exists. Always check the convergence condition before computing π.
• Overlooking explosion conditions: A CTMC can take infinitely many jumps in finite time. This happens when Σ 1/λ_i < ∞ (e.g., a pure birth process with λ_i = i²). Most textbook problems are well-behaved, but real models with unbounded rates can explode — check this before analysis.

Quiz

1. The generator matrix Q of a CTMC has row sums: a) Equal to 1 b) Equal to 0 c) Always positive d) Equal to the number of states Answer: b. Σ_j Q_{ij} = 0 — rates in equal rates out.

2. Q_{ii} for a CTMC is: a) The probability of staying in i b) Negative of the total rate of leaving state i c) Always zero d) The rate of entering state i Answer: b. Q_{ii} = −Σ_{j≠i} Q_{ij} = −λ_i, where λ_i is the total jump rate out of i.

3. The solution to P'(t) = QP(t) with P(0) = I is: a) P(t) = Qᵗ b) P(t) = I + tQ c) P(t) = e^{tQ} d) P(t) = ln(tQ) Answer: c. P(t) = e^{tQ} = Σ (tQ)ⁿ/n! — the matrix exponential.

4. For an M/M/1 queue to have a stationary distribution, we need: a) λ > μ b) λ = μ c) λ < μ d) Always exists Answer: c. Traffic intensity ρ = λ/μ < 1 is required for convergence of Σ ρⁱ.

5. In a birth-death process, detailed balance means: a) λ_i = μ_i b) π_i λ_i = π_{i+1} μ_{i+1} c) π_i = π_{i+1} d) Total birth rate equals total death rate Answer: b. The flux from i to i+1 equals the reverse flux at stationarity.

6. The holding time in state i of a CTMC has distribution: a) Geometric b) Exponential with rate −Q_{ii} c) Uniform d) Poisson Answer: b. The memoryless property of CTMCs: time in i ∼ Exp(λ_i) = Exp(−Q_{ii}).

7. A CTMC "explodes" when: a) The chain visits infinite states b) Infinitely many transitions occur in finite time c) State space is infinite d) The Q-matrix is singular Answer: b. Explosion = infinite jumps in finite time, occurs when Σ 1/λ_i converges.

8. The stationary distribution of a CTMC satisfies: a) πP = π b) πQ = 0 c) Qπ = π d) πQ = π Answer: b. πQ = 0 is the CTMC analog of πP = π for discrete time.

Next Steps

Continue to 11-09 Random Walks for simple and biased random walks on Z, the reflection principle, gambler's ruin, and recurrence properties.