Next State Please
Tomorrow's weather depends only on today's. Edit the chances, let a walker wander, and see where it settles.
Press Next day a few times, or hold Play. The walker only looks at today to pick tomorrow!
The weather walker
How often each weather happened
A tiny text writer
The same trick with words. The "weather" is the current word, and the table says which word tends to come next. It learned from this tiny story:
Press the button!
After each word, the chain only looks at the last word or two. A big language model also predicts the next word, but looks at far more words and learned from billions of sentences.
Challenges
What just happened?
- A Markov chain only needs today to guess tomorrow. It forgets everything before.
- Walk long enough and the share of days in each state settles to fixed numbers, no matter where you started.
- Power iteration finds those numbers without walking at all: just keep applying the table to a spread of chances until it stops changing.
- Change the table and the long-run weather changes with it.
- Next-word writing works the same way. Looking back 2 words copies the story more closely. Real language models look back at thousands of words.
For grown-ups: what's really going on
A Markov chain is a random process with the Markov property: P(Xt+1 | Xt, Xt−1, …) = P(Xt+1 | Xt). It is described by a row-stochastic transition matrix P (each row sums to 1).
- A distribution row vector π evolves as
πt+1 = πt P. The stationary distribution satisfiesπ = π P(a left eigenvector with eigenvalue 1). Power iteration repeats the multiplication until it converges. - For a chain that is irreducible and aperiodic (every state reachable, no rigid cycles) the stationary distribution is unique and the chain converges to it from any start (ergodic theorem). The speed depends on the second-largest eigenvalue modulus. A table with a state that never leaves (an absorbing state) breaks uniqueness.
- The walker's visit frequencies converge to π by the law of large numbers for Markov chains. Consecutive days are correlated, so convergence is slower than for independent draws.
- The text writer is an n-gram model: order 1 is a bigram chain (state = last word), order 2 a trigram chain (state = last two words). Counts from the story become probabilities. It can only reproduce word combinations it has seen.
- Modern language models also predict a distribution over the next token, but condition on a long context using a learned neural network instead of a count table. MCMC, PageRank and hidden Markov models are other famous uses of chains.
Further reading: Norris, Markov Chains · Brin and Page (1998), the PageRank paper · Shannon (1948), A Mathematical Theory of Communication (the first n-gram text).