1 Modelling context

Lesson 1 developed the one-step specification of a Markov chain. In applications, however, the questions of interest are usually about multiple steps: what is the probability of being in a given state after n steps, and what does the chain look like in the long run?

This lesson develops the n-step transition matrix via the Chapman–Kolmogorov equations, and the stationary distribution that describes the chain's long-run behaviour. Both are computed from the one-step transition matrix, so the specification work of Lesson 1 is the foundation for everything in this lesson.

2 Learning objectives

3 Prerequisite review

Matrix powers

For a square matrix P, the power P^n is the product of n copies of P. Computed iteratively or by diagonalization.

Eigenvalues and eigenvectors

A nonzero vector v with P v = λ v is an eigenvector of P with eigenvalue λ. The stationary distribution is related to the left eigenvector with eigenvalue 1.

Law of total probability

P(A) = Σ_i P(A | B_i) P(B_i) for a partition {B_i}. Used to derive the Chapman–Kolmogorov equations.

Convergence

The property that P^n tends to a limit as n → ∞. Guaranteed under irreducibility and aperiodicity.

4 Mathematical formulation

The Chapman–Kolmogorov equations

Let P_ij^(n) denote the probability of being in state j after n steps, starting from state i. The Chapman–Kolmogorov equations express the n-step probabilities in terms of intermediate steps:

P_ij^(n+m) = Σ_k P_ik^(n) P_kj^(m)

In matrix form, this says that the n-step transition matrix is P^n. So

P^(n) = P^n  (matrix power)

The n-step state distribution from an initial distribution π^(0) is therefore

π^(n) = π^(0) P^n

The stationary distribution

The stationary distribution of a Markov chain is a probability distribution π* that satisfies

π* P = π*

Equivalently, π* is a left eigenvector of P with eigenvalue 1, normalised to sum to 1. If the chain starts in its stationary distribution, the distribution does not change: π^(0) = π* implies π^(t) = π* for all t ≥ 0.

Existence and uniqueness

For a finite-state Markov chain, the existence of a stationary distribution is guaranteed. Uniqueness requires additional conditions:

• Irreducibility. Every state is reachable from every other state. If the chain has multiple closed communicating classes, the stationary distribution is not unique.
• Positive recurrence. Every state is visited infinitely often with probability 1. For finite irreducible chains, this is automatic.

For an irreducible, aperiodic chain with n states:

lim_{t→∞} P^t = [ 1 ; 1 ; … ; 1 ] π*

In words: the rows of P^t all converge to the same distribution π*, regardless of the starting state.

Solving for the stationary distribution

The stationary distribution satisfies the linear system

π* P = π*
Σ_i π*_i = 1

Rearranged, this is

π* ( P − I ) = 0
Σ_i π*_i = 1

This is a linear system in the n unknown components of π*. Since the rows of P sum to 1, the matrix P − I is singular, so the n equations are not independent. The normalisation condition Σ π*_i = 1 supplies the additional constraint.

A standard approach is to drop one of the n equations from π* (P − I) = 0, replace it with the normalisation, and solve the resulting n × n system.

Long-run proportion of time

A useful interpretation: for an ergodic chain, the component π*_i equals the long-run proportion of time the chain spends in state i:

π*_i = lim_{T→∞} (1/T) Σ_{t=1}^T 1{X_t = i}

This is the ergodic theorem for Markov chains. It is the bridge between the theory of Markov chains and the empirical behaviour observed in simulation (Lesson 3).

5 Worked example

       S    C    R
S   [ 0.7  0.2  0.1 ]
C   [ 0.3  0.4  0.3 ]
R   [ 0.2  0.3  0.5 ]

0.7 π_S + 0.3 π_C + 0.2 π_R = π_S    (1)
0.2 π_S + 0.4 π_C + 0.3 π_R = π_C    (2)
0.1 π_S + 0.3 π_C + 0.5 π_R = π_R    (3)

−0.3 π_S + 0.3 π_C + 0.2 π_R = 0
 0.2 π_S − 0.6 π_C + 0.3 π_R = 0
 0.1 π_S + 0.3 π_C − 0.5 π_R = 0

−0.3 π_S + 0.3 π_C + 0.2 π_R = 0    (1)
 0.2 π_S − 0.6 π_C + 0.3 π_R = 0    (2)
 π_S + π_C + π_R = 1                (N)

−0.3 π_S + 0.3 π_C + 0.2(1 − π_S − π_C) = 0
−0.5 π_S + 0.1 π_C + 0.2 = 0
−0.5 π_S + 0.1 π_C = −0.2
5 π_S − π_C = 2                (1')

0.2 π_S − 0.6 π_C + 0.3(1 − π_S − π_C) = 0
−0.1 π_S − 0.9 π_C + 0.3 = 0
0.1 π_S + 0.9 π_C = 0.3
π_S + 9 π_C = 3                (2')

π_S + 9(5 π_S − 2) = 3
π_S + 45 π_S − 18 = 3
46 π_S = 21
π_S ≈ 0.4565

π* P = (0.4565, 0.2826, 0.2609) P
     ≈ (0.4565, 0.2826, 0.2609) = π*  ✓

6 Verification check

7 Interpretation

The stationary distribution is the central quantity in Markov-chain analysis. Its main interpretations:

• Long-run proportion of time. The component π*_i is the fraction of time the chain spends in state i over a long horizon.
• Limiting distribution. For an irreducible, aperiodic chain, the distribution of X_t converges to π* as t → ∞, regardless of the starting distribution.
• Left eigenvector with eigenvalue 1. The stationary distribution is the unique normalised left eigenvector of P corresponding to eigenvalue 1.

These three interpretations coincide for an ergodic chain. For non-ergodic chains they may differ, and the interpretation must be stated carefully.

8 Uncertainty and limitations

The stationary distribution carries the uncertainty of the transition matrix from which it was computed. Two sources are worth distinguishing.

9 Common implementation errors

10 Independent modelling task

11 Reflection prompt

12 Lesson summary

§ Self-quiz, practice, and homework