Markov Chains
20 min
A Markov chain moves between a fixed set of states, where the probability of the next state depends ONLY on the current state — not on how you got there. That's the Markov property ("memorylessness"), and it's what makes these systems tractable: you don't need the whole history, just the current state.
A transition matrix encodes all the probabilities: row i, column
j is the probability of moving from state i to state j (each row
sums to 1). A simple 2-state weather model — 0 = sunny, 1 = rainy:
transition = [
[0.9, 0.1], # from sunny: 90% stay sunny, 10% become rainy
[0.5, 0.5], # from rainy: 50% stay rainy, 50% become sunny
]
Picking the next state: draw one random number, then walk through the current row's probabilities, accumulating until you pass the random draw -- the standard way to sample from a discrete distribution given only its probabilities.
Run a Markov chain long enough and the fraction of time spent in each state settles down to a fixed long-run value — the stationary distribution — regardless of where you started. For the weather chain above, that turns out to be about 5/6 sunny, 1/6 rainy: sunny days are "sticky" (90% chance of staying sunny), so the chain spends most of its long-run time there even though rainy days can occur.
You can estimate the stationary distribution exactly the way you'd estimate anything else in this course — Monte Carlo style: simulate many steps, and count how often the chain is in each state.
Write `simulate_markov_chain(transition, start_state, n_steps, seed=42)`. `transition` is a list of lists where `transition[i][j]` is the probability of moving from state `i` to state `j`. Simulate `n_steps` transitions starting from `start_state` and return the final state (an int index).
Write `estimate_stationary_distribution(transition, start_state, n_steps, seed=42)`: run the chain for `n_steps` transitions, count how many of those steps land in state 0, and return that count divided by `n_steps`, rounded to 4 decimals — an estimate of state 0's long-run (stationary) probability.
What is the 'Markov property' (the defining feature of a Markov chain)?
You can simulate a Markov chain from a transition matrix and estimate its stationary distribution by counting state visits over a long run.