Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 36 · Markov Chains

n-Step Transitions and the Chapman-Kolmogorov Equations

Compute multi-step probabilities of a Markov chain with matrix powers: the Chapman-Kolmogorov equations and the distribution of X_n, checked in Python.

One step of a Markov chain is easy: look up a row of P. But the questions you actually care about are usually about many steps. If it is rainy today, what is the chance of rain in a week? The answer is a matrix power, and this lesson shows why.

Two-step probabilities

Define the n-step transition probability

Text
p_ij^(n) = P(X_(m+n) = j | X_m = i)

For two steps, you must pass through some intermediate state k after one step. By the law of total probability and the Markov property,

Text
p_ij^(2) = Σ_k p_ik p_kj

This is exactly the entry in row i, column j of the matrix product P × P = P². So the two-step matrix is P².

The Chapman-Kolmogorov equations

The same argument works for any split of the steps. For m, n >= 0,

Text
p_ij^(m+n) = Σ_k p_ik^(m) p_kj^(n)       equivalently       P^(m+n) = P^m P^n

These are the Chapman-Kolmogorov equations. Going m + n steps means going m steps to some state k and then n more steps. Applying this repeatedly, the n-step matrix is simply the n-th power P^n.

flowchart LR
    i["i"] -->|"m steps"| k1["k_1"]
    i -->|"m steps"| k2["k_2"]
    i -->|"m steps"| k3["k_3"]
    k1 -->|"n steps"| j["j"]
    k2 -->|"n steps"| j
    k3 -->|"n steps"| j

To go from i to j in m + n steps, sum over every possible state k visited after m steps.

Python Matrix powers for the weather chain

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.

Notice that the two probabilities for rain in 7 days are nearly equal even though today's weather differs. The chain is forgetting its starting point. That is the main story of Chapter 4.

The distribution of X_n

Often you do not know the starting state for sure. Let μ_0 be the initial distribution, a row vector with μ_0(i) = P(X_0 = i). Then the distribution at time n is

Text
μ_n = μ_0 P^n

and you can update one step at a time with μ_(n+1) = μ_n P. Row vector times matrix, in that order.

Python Evolve the distribution day by day

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.

The probabilities change less and less from day to day. They are converging to a fixed distribution, which we will compute exactly in Chapter 4.

Check with simulation

Simulating many independent chains and counting where they are at time n must give μ_n.

Python Simulation versus P^n

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.

The trick (u > cum[state]).sum() counts how many cumulative thresholds the uniform draw exceeds, which is the index of the chosen state. It samples every chain at once.

A caution on matrix multiplication

P @ P multiplies matrices; P * P multiplies entries one by one, which is not what Chapman-Kolmogorov needs. Also remember that the rows are the "from" states, so P^n row i is the distribution after n steps starting from i.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. The two-step transition matrix is...

    p_ij^(2) = Σ_k p_ik p_kj is the (i, j) entry of the matrix product P·P.
  2. 2. If μ_0 is a row vector with the starting distribution, the distribution at time n is...

    Row vector times the n-step matrix: μ_n = μ_0 P^n.
  3. 3. The Chapman-Kolmogorov equations state that P^(m+n) equals...

    Going m + n steps is going m steps and then n steps.
  4. 4. Row sums of P^n are always...

    P^n is itself a stochastic matrix, so each row is a probability distribution.

Summary

  • p_ij^(n) is the (i, j) entry of P^n.
  • Chapman-Kolmogorov: P^(m+n) = P^m P^n; sum over the intermediate state.
  • μ_n = μ_0 P^n gives the distribution at time n.
  • For a good chain, μ_n stops changing as n grows: a preview of stationary distributions.

Next: Classification of States