Predicting the Next Letter: Markov Chains and Autocomplete
Statistics & Probability
Your phone's keyboard predicts your next word from the last one or two. Build the simplest version of that predictor and find out how far you can push it with a Markov chain.
Introduction
A Markov chain predicts what happens next from the current state alone, ignoring everything before it. Predictive text on a phone keyboard works close to exactly this way: given the last letter (or word) you typed, what is the most likely next one? This exploration builds a transition matrix from a real block of text (a book, your own messages, song lyrics), uses it to generate predictions and even nonsense text, and tests how much accuracy you lose by ignoring everything before the current letter.
Guiding Questions
- Take a real text source and build a transition matrix: given the current letter (or word), what is the probability of each possible next one?
- Use matrix powers to predict the letter distribution several steps ahead. Does it converge to something, and what does that limit mean for the text?
- Generate text by following your chain step by step. How recognisable is the result, and what does that tell you about how much a single previous letter actually predicts?
- Real language has more memory than one letter back. Build a chain that looks two letters back instead of one, and test whether its predictions improve, and by how much.