Markov chain

In 1906, Andrey Markov was 50 years old and semi-retired from St. Petersburg University—stubborn, contrarian, and deeply atheist in Tsarist Russia. The invention arose from an academic dispute. Mathematician Pavel Nekrasov claimed that independence between events was necessary for the weak law of large numbers. Markov disagreed and needed to prove that sequences of dependent events could still exhibit predictable long-run behavior.

Starting with a simple two-state system, Markov proved that if all transition probabilities were greater than zero and less than one, the frequency of each state would converge to a fixed average over time—even though each event depended on what came before. This was the birth of the Markov chain: a "memoryless" sequence where the next state depends only on the current state, with no connection to earlier history.

On January 23, 1913, Markov presented his most surprising application: he had taken Pushkin's novel Eugene Onegin and transcribed the first 20,000 letters into continuous string, eliminating punctuation. He found 43% were vowels, 57% consonants. A vowel was followed by consonant 87% of the time. The letters formed a Markov chain—each letter's probability depended on its predecessor, yet the system exhibited stable patterns.

Markov died in 1922, never seeing the cascade. In 1931, Kolmogorov extended discrete-time chains to continuous processes. When Larry Page and Sergey Brin built Google's PageRank in 1996, they modeled web surfing as a Markov chain—each webpage a state, hyperlinks as transitions. For 322 million links, the algorithm converged in 52 iterations.

Hidden Markov Models revolutionized speech recognition in the 1980s. DNA sequences exhibit Markovian properties—nucleotide probability depends on preceding bases. Financial regime-switching models use Markov chains to identify economic transitions. The memoryless property Markov discovered turns out to describe phenomena from Google searches to genetic mutations to economic crashes.