Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 36 ยท Markov Chains

The Markov Property and Transition Matrices

Learn what a Markov chain is: the Markov property, states, transition probabilities and the transition matrix, with a weather chain you simulate in Python.

A Markov chain is the simplest process with memory that is still easy to analyze. It remembers exactly one thing: where it is now. Everything about how it got here is forgotten. That single restriction makes the mathematics beautiful, and it fits an astonishing number of real systems: weather states, web page navigation, board games, genetics, queues, and the page-ranking idea behind search engines.

The Markov property

Consider a process X_0, X_1, X_2, ... with a finite or countable state space S. It is a (discrete-time) Markov chain if for every n and all states,

Text
P(X_(n+1) = j | X_n = i, X_(n-1) = i_(n-1), ..., X_0 = i_0) = P(X_(n+1) = j | X_n = i)

The next state depends on the history only through the current state. We also assume the chain is time-homogeneous: the probability does not depend on n. Then we can write

Text
p_ij = P(X_(n+1) = j | X_n = i)

for the transition probability from i to j. These are non-negative, and from each state they sum to 1: ฮฃ_j p_ij = 1.

The transition matrix

Collect the probabilities in a matrix P whose entry in row i, column j is p_ij. Each row sums to 1; such a matrix is called a stochastic matrix (columns need not sum to 1).

Example: a weather chain

Suppose each day is Sunny (S), Cloudy (C) or Rainy (R), with these transition probabilities (invented for illustration):

from \ to S C R
S 0.7 0.2 0.1
C 0.3 0.4 0.3
R 0.2 0.3 0.5

Read row S as: after a sunny day, tomorrow is sunny with probability 0.7, cloudy 0.2, rainy 0.1.

flowchart LR
    S((S)) -->|"0.7"| S
    S -->|"0.2"| C((C))
    S -->|"0.1"| R((R))
    C -->|"0.3"| S
    C -->|"0.4"| C
    C -->|"0.3"| R
    R -->|"0.2"| S
    R -->|"0.3"| C
    R -->|"0.5"| R

The state diagram: circles are states, arrows carry transition probabilities.

Python Build the matrix and validate it

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.

Simulating a chain

To step a chain from state i, draw the next state from row i of P.

Python Simulate the weather for 20 days

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 estimated matrix (each row of counts divided by its total) should be close to P. This is also how real transition matrices are fitted from data.

What the Markov property does and does not say

  • It says: given today, yesterday does not matter for tomorrow.
  • It does not say: yesterday does not matter at all. Yesterday influences today, and today influences tomorrow.
  • A process that is not Markov can often be made Markov by enlarging the state. If tomorrow's weather depended on the last two days, use pairs such as (yesterday, today) as states.

Time-homogeneous means the matrix P is the same every day. Seasonal weather would need a different matrix for each month, which gives a time-inhomogeneous chain. We study only homogeneous chains in this track.

More examples

System States Why it is (approximately) Markov
Gambler's fortune dollars held next fortune depends only on current fortune and the bet
Board game like snakes and ladders square number dice are independent of history
Web surfer current page choose a random link on the page
Inventory stock level next level depends on current stock and random demand

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a transition matrix P, what must be true of each row?

    Row i lists the probabilities of moving from i to each state, so it is a probability distribution.
  2. 2. The Markov property says the next state depends on the past...

    Given the present, the earlier history carries no extra information about the next step.
  3. 3. In the weather chain above, what is P(rainy tomorrow | sunny today)?

    That is the entry in row S, column R.
  4. 4. If tomorrow depends on the last TWO days, how can you still use a Markov chain?

    Enlarging the state to include the needed history restores the Markov property.

Summary

  • A Markov chain forgets everything except the present state.
  • Time-homogeneous chains have fixed transition probabilities p_ij, collected in a row-stochastic matrix P.
  • A state diagram draws the same information as arrows between states.
  • Chains are simulated by sampling from the row of the current state, and P can be estimated by counting transitions.

Next: n-Step Transitions and the Chapman-Kolmogorov Equations