Probability & Uncertainty

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

walker's share of dayslong-run answer (power iteration)

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

Take a walk: let the walker travel 100 days.
Settle down: after 2,000 days, every bar lands within 3.5 points of the long-run marker.
Make it rain: edit the table so rain happens more than half of all days in the long run.
Write a sentence with the tiny text writer.
Look back 2 words and write a sentence. Does it sound more like the story?

What just happened?

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).