Markov Chain: Chapman–Kolmogorov Explained with Worked Examples

The -step transition probabilities are the entries of the matrix power , and : to go in steps, go in steps to some state and then steps from there.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Markov chain: Chapman–Kolmogorov means

For : , so , summing over the intermediate state with the law of total probability. Squaring again, , and .

As grows the rows of approach the stationary distribution (the stationary distribution): already has rows and . The matrix products are computed as in matrix multiplication; for large powers use diagonalisation (diagonalisation, eigenvalues of a 2 × 2 matrix).

The equation is the Markov (memoryless) property combined with total probability: the multiplication rule (the multiplication rule) for each path and addition over intermediate states. Its continuous-time counterpart is the Kolmogorov equations, and it also appears in the Poisson process and Brownian motion.

What is it used for?

The Chapman–Kolmogorov equation says that multi-step probabilities come from multiplying the transition matrix by itself.

How to use markov chain: chapman–kolmogorov

  1. Write the one-step matrix .
  2. Compute , and if needed.
  3. Read off the entry for the -step probability.
  4. Check that each row sums to 1.

Graph

Entries of P⁴ for the two-state chain: 0.8376, 0.1624, 0.812, 0.188P⁴(1,1) = 0.8376P⁴(1,2) = 0.162400.511.522.533.544.5500.20.40.60.81Entries of P⁴ for the two-state chain: 0.8376, 0.1624, 0.812, 0.188entryyGraph with x from 0 to 5 and y from 0 to 1. Shows bars (4); point P⁴(1,1) = 0.8376 at (1, 0.8376); point P⁴(1,2) = 0.1624 at (2, 0.1624).

Each row of P⁴ adds to 1 and is close to the stationary distribution.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: a two-step probability

Find .

Worked example
Answer
0.140.14
  1. Formula

Example 2: four steps

Find .

Worked example
Answer
0.83760.8376
  1. Formula

Example 3: three steps

Find .

Worked example
Answer
0.220.22
  1. P³ = P²P

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

P = (0.9 0.1; 0.5 0.5)

P²(1,1) = 0.9·0.9 + 0.1·0.5

0.86.

P²(1,2)

0.9·0.1 + 0.1·0.5

0.14.

P²(2,1)

0.5·0.9 + 0.5·0.5

0.70.

Row sum

P²(1,1) + P²(1,2)

1.

Word problems

P⁽ⁿ⁺ᵐ⁾ = P⁽ⁿ⁾P⁽ᵐ⁾: go n steps to an intermediate state, then m steps. The n-step probabilities are the entries of Pⁿ.

Stay in 1

Find P²(1,1).

  1. 0.81 + 0.05
  2. Check: ✓0.86

1 to 2

Find P²(1,2).

  1. 0.09 + 0.05
  2. Check: ✓0.14

2 to 1 Higher

Find P²(2,1).

  1. 0.45 + 0.25
  2. Check: ✓0.7

Row sum Higher

Check P²(1,1) + P²(1,2).

  1. 0.86 + 0.14
  2. Check: ✓1

Common mistakes

Squaring entries

entrywise squares ✗

matrix product ✓

Sum over intermediates.

Missing a path

only one middle state ✗

sum over all ✓

Chapman–Kolmogorov.

Columns summing to 1

check columns ✗

rows sum to 1 ✓

Row-stochastic.

Order of multiplication

PP is symmetric ✗

P⁽ⁿ⁾P⁽ᵐ⁾ commutes for powers ✓

Same matrix.

Exam tips

  1. Matrix power.
  2. Sum over middle states.
  3. Rows sum to 1.
  4. P⁰ = I.
  5. Check by row sums.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. P²(1,1) for a=0.2,b=0.4: 0.8·0.8+0.2·0.4 Foundation

0.72

2. P²(1,2) same chain Foundation

0.28

3. P²(2,1) same chain Foundation

0.56

4. P²(2,2) same chain Higher

0.44

5. Row 1 sum of P² Higher

1

6. P²(1,1) for P=(0.5 0.5;0.5 0.5) Higher

0.5

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Chapman–Kolmogorov equation
P⁽ⁿ⁺ᵐ⁾ = P⁽ⁿ⁾P⁽ᵐ⁾.
n-step probability
Entry of Pⁿ.
Transition matrix
One-step P.
Intermediate state
Visited at step n.
Row-stochastic
Rows sum to 1.
Markov property
Memoryless.

Frequently asked questions

What is the Chapman–Kolmogorov equation?

P⁽ⁿ⁺ᵐ⁾ = P⁽ⁿ⁾P⁽ᵐ⁾.

How do I get two-step probabilities?

Square the transition matrix.

Why sum over states?

Any intermediate state may be visited.

What should each row sum to?

1.

Which page covers stationary distributions?

stationary distribution.

Which page covers the Poisson process?

Poisson process.

More in Advanced statistics and stochastic processes and the formula sheets.