About this experiment
A Markov chain hops between states at random, but the chance of each hop depends only on where it is now, not on how it got there. Tomorrow's weather depends on today's, a web surfer's next page depends on the current one, and a molecule's next shape depends on its present shape. However the chain starts, a well-behaved chain forgets its beginning and settles into a steady state π. Edit the transition probabilities, run the chain, and watch both the long-run frequencies and the distribution pₙ converge to π.
Learning goals
- Write the transition matrix of a Markov chain and check that each row sums to 1
- Compute the distribution after n steps as p₀Pⁿ
- Find the stationary distribution by solving πP = π
- Relate the speed of convergence to the second-largest eigenvalue of P
- Recognise chains that do not converge, such as periodic chains
How to use it
- 1With the Weather chain, press Run and watch the token. Then press 1000 steps. How close are the bars to the dashed lines?
- 2Change the starting state. Does the steady state change? Does the early part of the upper graph change?
- 3Check the steady state by hand: multiply π by the matrix and show you get π back.
- 4Choose Slow to mix. How many steps does the upper graph need to settle? Compare with |λ₂| and the readout.
- 5Choose Periodic cycle. Why does the upper graph never settle, even though the share of time in each state does?
- 6Choose Forgets at once. Why does the distribution reach π after a single step?
The model
Assumptions
- Three states and time-homogeneous transition probabilities. Each row is edited with two sliders; the probability of staying put is what is left.
- The sample path comes from a seeded random generator, so the same run number always gives the same path; New run changes the seed.
- The steady state is found by solving the linear equations exactly. The steps to get within 1 % are estimated as ln 100 / (-ln |λ₂|).
Try this in class
- Q1For P = [[0.9, 0.1], [0.5, 0.5]], find the stationary distribution.
- Q2Show that the uniform distribution is stationary whenever every column of P also sums to 1.
- Q3A chain has |λ₂| = 0.95. Roughly how many steps does it need to forget its starting state?
- Q4Explain why the Periodic cycle chain has a stationary distribution but pₙ does not converge to it.
- Q5Google's original PageRank is the stationary distribution of a random surfer. Why did it add a small chance of jumping to any page?
Frequently asked questions
What does memoryless mean here?
The future depends on the past only through the present state. If you know today is rainy, knowing that last week was sunny tells you nothing more about tomorrow.
Does every chain have a steady state?
Every finite chain has at least one stationary distribution. It is unique if every state can reach every other, and pₙ converges to it from any start if, in addition, the chain is not periodic.
Where are Markov chains used?
In queueing and reliability models, genetics, speech recognition, text prediction, finance, and in Markov chain Monte Carlo, which builds a chain whose steady state is a distribution you want to sample.