📐 Concept diagram

Phase 11: Probability Theory II

Subject 11-07: Markov Chains (Discrete Time)

Prerequisites: 10-04 (Discrete Random Variables), 10-10 (Joint Distributions), linear algebra (matrix multiplication, eigenvalues)

Learning Objectives

1. Define a discrete-time Markov chain with state space S and transition matrix P
2. State the Markov property and the Chapman-Kolmogorov equations
3. Compute n-step transition probabilities P(Xₙ = j | X₀ = i) = (Pⁿ)_{ij}
4. Classify states as recurrent, transient, absorbing, and determine periodicity
5. Define and compute stationary distributions π = πP and apply the ergodic theorem

Core Content

1. Definition and Markov Property

A discrete-time Markov chain is a sequence of random variables {Xₙ : n = 0, 1, 2, ...} taking values in a countable state space S, satisfying the Markov property:

$P(X_{n+1} = j | Xₙ = i, X_{n−1} = i_{n−1}, ..., X₀ = i₀) = P(X_{n+1} = j | Xₙ = i)
$

"The future depends on the past only through the present." Given the current state, the future is conditionally independent of the past.

Time-homogeneous (we'll focus on this case): Transition probabilities don't depend on n:

$P_{ij} = P(X_{n+1} = j | Xₙ = i)
$

The transition matrix P is an |S| × |S| matrix where P_{ij} = probability of moving from i to j in one step.

Properties of P: 1. P_{ij} ≥ 0 for all i, j (non-negative entries) 2. Σ_j P_{ij} = 1 for each i (each row sums to 1 — a stochastic matrix) 3. P 1 = 1 (the vector of all ones is a right eigenvector with eigenvalue 1)

⚠️ CRITICAL: P_{ij} means "from i TO j." The row is the starting state, the column is the destination.

2. Chapman-Kolmogorov Equations

For n-step transition probabilities, let P^{(n)}_{ij} = P(Xₙ = j | X₀ = i). Then:

P^{(n+m)}_{ij} = Σ_k P^{(n)}_{ik} P^{(m)}_{kj}

Equivalently: P^{(n)} = Pⁿ — the n-step transition matrix is the n-th power of P.

Proof: To go from i to j in n+m steps, you must be at some state k after n steps, then go from k to j in m steps. The Markov property makes the future segment conditionally independent.

Example — Two-state chain:

$P = [1−α    α ]
    [ β    1−β]
$

with 0 < α, β < 1. Pⁿ can be computed explicitly by diagonalizing P:

$Pⁿ = 1/(α+β) [β  α]  +  (1−α−β)ⁿ/(α+β) [α  −α]
             [β  α]                       [−β  β]
$

As n → ∞, the second term vanishes if |1−α−β| < 1, and:

$lim Pⁿ = [β/(α+β)  α/(α+β)]
         [β/(α+β)  α/(α+β)]
$

The rows become identical — the chain "forgets" its initial state.

3. State Classification

Accessibility and communication: - j is accessible from i (i → j) if P^{(n)}_{ij} > 0 for some n ≥ 0 - i and j communicate (i ↔ j) if i → j and j → i - Communication is an equivalence relation — partitions the state space into communicating classes

Recurrence and transience: Let f_{ii} = P(chain ever returns to i | X₀ = i).

• State i is recurrent if f_{ii} = 1 — the chain returns to i with probability 1
• State i is transient if f_{ii} < 1 — there's a positive probability of never returning
• For a recurrent state: expected number of visits is infinite. For transient: expected visits is finite.

Test: i is recurrent iff Σ_{n=1}^{∞} P^{(n)}_{ii} = ∞. (If the sum converges, i is transient.)

Absorbing states: P_{ii} = 1. Once you enter, you can never leave. Absorbing states are always recurrent.

Periodicity: The period of state i is d(i) = gcd{n ≥ 1 : P^{(n)}_{ii} > 0}. If d(i) = 1, the state is aperiodic. If all states are aperiodic, the chain is aperiodic.

4. Stationary Distributions

A probability distribution π = (π₁, π₂, ...) on S is a stationary distribution (or invariant distribution) if:

π = πP    i.e.    π_j = Σ_i π_i P_{ij}  for all j

If X₀ ~ π, then Xₙ ~ π for all n. The distribution is "stationary" — it doesn't change over time.

Existence: Every finite-state Markov chain has at least one stationary distribution. Uniqueness: If the chain is irreducible (all states communicate) and positive recurrent (expected return time is finite), the stationary distribution is unique.

Interpretation of π_j: Long-run proportion of time spent in state j:

π_j = lim_{n→∞} (1/n) Σ_{k=1}^{n} 1_{X_k = j}

Computing π: Solve the linear system πP = π with Σ πᵢ = 1 (and πᵢ ≥ 0).

For the two-state chain:

$π₀(1−α) + π₁β = π₀  →  −απ₀ + βπ₁ = 0  →  π₁ = (α/β)π₀
$

With π₀ + π₁ = 1: π₀ = β/(α+β), π₁ = α/(α+β). ✓ (Matches the limit of Pⁿ.)

5. Ergodic Theorem

For an irreducible, aperiodic, positive recurrent Markov chain with stationary distribution π:

lim_{n→∞} P^{(n)}_{ij} = π_j    for all i, j

The chain "forgets" its initial state and converges to the stationary distribution.

Ergodic theorem for Markov chains:

$(1/n) Σ_{k=1}^{n} f(X_k) → E_π[f] = Σ_i π_i f(i)    almost surely
$

Long-run averages converge to expectations under the stationary distribution. This justifies MCMC methods — run a Markov chain with stationary distribution π, then average f(X_k) to estimate E_π[f].

Detailed balance (sufficient for stationarity): If there exists π such that π_i P_{ij} = π_j P_{ji} for all i, j, then π is stationary. (Proof: sum over i to get πP = π.) This is the foundation of the Metropolis-Hastings algorithm.

Key Terms

• Detailed balance
• Markov property
• Time-homogeneous

Worked Examples

Example 1: Weather Model

A simple weather model: if it's sunny today, tomorrow is sunny with probability 0.8, rainy with 0.2. If rainy today, tomorrow is sunny with probability 0.4, rainy with 0.6.

(a) Write the transition matrix. (b) If today is sunny, what's the probability it's rainy in 2 days? (c) Find the stationary distribution.

Solution:

(a) States: S=Sunny, R=Rainy.

$P = [0.8  0.2]
    [0.4  0.6]
$

(b) P² = [[0.8²+0.2·0.4, 0.8·0.2+0.2·0.6], [0.4·0.8+0.6·0.4, 0.4·0.2+0.6²]] = [[0.64+0.08, 0.16+0.12], [0.32+0.24, 0.08+0.36]] = [[0.72, 0.28], [0.56, 0.44]] P(rainy in 2 days | sunny today) = P²_{S,R} = 0.28.

(c) π₀ = π₀(0.8) + π₁(0.4), π₁ = π₀(0.2) + π₁(0.6). With π₀+π₁=1: π₀ = 0.8π₀ + 0.4(1−π₀) → π₀ = 0.8π₀ + 0.4 − 0.4π₀ → 0.6π₀ = 0.4 → π₀ = 2/3, π₁ = 1/3. Long run: sunny 2/3 of days, rainy 1/3.

Example 2: Gambler's Ruin

A gambler starts with $k and plays a fair game: wins $1 with probability 0.5, loses $1 with probability 0.5. Stops when broke ($0) or reaches goal of $N. What is the probability of reaching $N before going broke?

Solution:

Let p_i = P(reach N before 0 | start at i), for i = 0, 1, ..., N.

Boundary: p₀ = 0, p_N = 1. For 1 ≤ i ≤ N−1: p_i = (1/2) p_{i+1} + (1/2) p_{i-1}.

This is a linear difference equation: p_{i+1} − 2p_i + p_{i-1} = 0. Solution: p_i = A + Bi.

From boundary conditions: p₀ = A = 0, p_N = BN = 1 → B = 1/N. So p_i = i/N.

For the gambler starting with k dollars and goal N: P(win) = k/N. With a fair game, ruin is certain in the long run against an infinitely wealthy opponent.

Example 3: Ehrenfest Urn Model

N balls distributed between two urns. Each step, pick a ball uniformly at random and move it to the other urn. Let Xₙ = number of balls in urn 1.

Solution:

Transitions: from i balls, pick one of i balls from urn 1 (prob i/N) → move to urn 2 → state i−1. Or pick from urn 2 (prob (N−i)/N) → move to urn 1 → i+1.

P_{i,i−1} = i/N, P_{i,i+1} = (N−i)/N, P_{i,i} = 0.

Stationary: detailed balance holds! π_i P_{i,i+1} = π_{i+1} P_{i+1,i}: π_i · (N−i)/N = π_{i+1} · (i+1)/N → π_{i+1} = π_i (N−i)/(i+1).

Solving recursively: π_i = C(N, i) (1/2)^N. This is Binomial(N, 0.5) — at stationarity, each ball is equally likely to be in either urn.

Quiz

Q1: The Markov property for a discrete-time chain states:

A) P(X_{n+1} = j | X_n = i) depends on all previous states B) P(X_{n+1} = j | X_n = i, X_{n−1}, ..., X₀) = P(X_{n+1} = j | X_n = i) C) The chain always converges to a stationary distribution D) All states communicate with each other

Correct: B)

• If you chose B: Correct! The future depends on the past only through the present. Given X_n, X_{n+1} is conditionally independent of X_{n−1}, ..., X₀.
• If you chose A: This violates the Markov property — the whole point is that only the current state matters.
• If you chose C: Convergence depends on chain properties (irreducibility, aperiodicity, positive recurrence).
• If you chose D: Communication is a property of some chains (irreducible), not part of the Markov definition.

Q2: The n-step transition probability P(X_n = j | X₀ = i) is given by:

A) P^n, the n-th power of the transition matrix B) n · P C) The sum of n copies of P D) P, independent of n

Correct: A)

• If you chose A: Correct! This follows from the Chapman-Kolmogorov equations: P^{(n)} = P^n. The (i,j) entry of P^n gives P(X_n = j | X₀ = i).
• If you chose B: This would give probabilities > 1 for n > 1.
• If you chose C: This doesn't account for the sequential nature of transitions.
• If you chose D: Multi-step probabilities change with n.

Q5: A stationary distribution π satisfies:

A) π = P π B) π = π P and Σ πᵢ = 1 C) π = P D) π = π^T P

Correct: B)

• If you chose B: Correct! π P = π means the distribution is invariant under the transition matrix, and it must be a proper probability distribution (sum to 1).
• If you chose A: This is the eigenvalue equation Ax = λx with λ = 1 — close but the vector multiplies P from the LEFT in π P = π.
• If you chose C: The stationary distribution is generally different from the transition matrix.
• If you chose D: π is a row vector; π^T would be a column vector, making dimensions wrong.

Practice Problems

1. For P = [[0.3, 0.7], [0.6, 0.4]], compute P² and P³. Find the stationary distribution.
2. Classify all states in P = [[0.5, 0.5, 0], [0, 0, 1], [0.2, 0.8, 0]] as recurrent or transient.
3. Show that a finite-state irreducible Markov chain has a unique stationary distribution.
4. For the two-state chain with α=0.1, β=0.2, what is the expected number of steps to return to state 0 given X₀=0?
5. Verify the detailed balance condition for the Ehrenfest urn model and confirm it gives the binomial stationary distribution.
6. A Markov chain has transition matrix P. Show that λ=1 is always an eigenvalue and find a left eigenvector.
7. For the gambler's ruin with a biased coin (P(win) = 0.4, P(lose) = 0.6), derive P(reaching goal) when starting with $k.

Summary

• A Markov chain satisfies P(X_{n+1}=j | Xₙ=i, history) = P(X_{n+1}=j | Xₙ=i); the future depends on the past only through the present
• Transition matrix P has rows summing to 1; n-step transitions are Pⁿ by Chapman-Kolmogorov
• States are recurrent (return probability 1) or transient; irreducible = all states communicate; aperiodic = period 1
• Stationary distribution π satisfies πP = π; for irreducible, aperiodic, positive recurrent chains, Pⁿ → π (ergodic theorem)
• Detailed balance π_i P_{ij} = π_j P_{ji} is a sufficient condition for stationarity — basis of MCMC

Pitfalls

• Confusing the direction of P_{ij}: P_{ij} = P(X_{n+1} = j | Xₙ = i) means "from row i to column j." A common error is transposing the matrix or reading from column to row. Always verify: each row sums to 1.
• Mixing up πP = π with Pπ = π: The stationary distribution π is a row vector satisfying πP = π (left eigenvector with eigenvalue 1). Writing Pπ = π implies π is a column vector — wrong dimensions and wrong equation.
• Assuming every Markov chain converges to a stationary distribution: Convergence (the ergodic theorem) requires irreducibility, aperiodicity, and positive recurrence. A periodic chain (e.g., period 2) does not have lim Pⁿ = π; instead Pⁿ oscillates. A chain with transient states may have its limiting distribution concentrated on recurrent classes only.
• Forgetting to check aperiodicity: Irreducibility alone is not enough. The simple random walk on a bipartite graph (period 2) is irreducible but Pⁿ does not converge — entries alternate between zero and non-zero. You need aperiodicity for the limit to exist.
• Misapplying the sum test for recurrence: State i is recurrent iff Σ_{n=1}^{∞} P^{(n)}_{ii} = ∞. If this sum converges, i is transient. A common mistake is checking only a few terms — the sum may appear to converge for small n but diverge eventually.

Quiz

1. The Markov property means: a) States are independent b) Future is conditionally independent of the past given the present c) The chain is deterministic d) Transitions depend on all previous states Answer: b. P(X_{n+1} | Xₙ, ..., X₀) = P(X_{n+1} | Xₙ).

2. The n-step transition matrix is: a) nP b) Pⁿ c) P/n d) e^{nP} Answer: b. By Chapman-Kolmogorov, P^{(n)} = Pⁿ.

3. A state i is recurrent if: a) P_{ii} = 0 b) The chain returns to i with probability 1 c) The chain never returns to i d) i is the only state Answer: b. f_{ii} = P(ever return | start at i) = 1 for a recurrent state.

4. The stationary distribution π satisfies: a) Pπ = π b) πP = π c) π = P d) πP = 1 Answer: b. π is a row vector with πP = π (a left eigenvector with eigenvalue 1).

5. For an irreducible, aperiodic, positive recurrent chain, P^{(n)}{ij} →: a) 0 b) 1 c) π_j (independent of i) d) P{ij} Answer: c. The chain forgets its initial state — the limit depends only on the destination.

6. The detailed balance condition is: a) P_{ij} = P_{ji} b) π_i P_{ij} = π_j P_{ji} c) π_i = π_j d) P_{ij} P_{ji} = 1 Answer: b. Detailed balance means the probability flux from i to j equals flux from j to i at stationarity.

7. An absorbing state has: a) P_{ii} = 0 b) P_{ii} = 1 c) All outgoing probabilities equal d) P_{ii} = 0.5 Answer: b. Once entered, the chain stays there forever.

8. In a finite irreducible Markov chain, the stationary distribution is: a) Always uniform b) Unique c) May not exist d) Always has π_i = 1/|S| Answer: b. For finite irreducible chains, the stationary distribution exists and is unique.

Next Steps

Continue to 11-08 Markov Chains (Continuous Time) for the continuous-time analog: Q-matrices, exponential holding times, and birth-death processes.