The History of AI

Markov chains

Era 1 · The foundations (1763–1942) › Probability and statistics

Lineage
Data and learning
Kind
Theory

Who

University of St. Petersburg

What happened

Andrey Markov studies sequences of events in which each one depends on the one before. In 1913 Markov applies the idea to the first 20,000 letters of Pushkin's Eugene Onegin.

Why it mattered

Markov chains: the first mathematical model of a sequence in which each element depends on the previous one, and the first analysis of a text as a sequence of dependent events. They underlie statistical language models and methods such as PageRank.

The full story

The law of large numbers says that if an experiment is repeated many times, the average of the results settles down. In 1902 the Moscow mathematician Pavel Nekrasov argued that the law requires the events to be independent, and drew from this an argument for free will. Andrey Markov, a professor in St. Petersburg, thought this was false, and in 1906 proved it.

Markov studied sequences in which each event depends on the one before: a system that moves from one state to another with fixed probabilities. Even then, the proof showed, the frequency with which each state appears tends toward fixed values. Independence was not needed.

On January 23, 1913, before the St. Petersburg Academy of Sciences, Markov applied the idea to a text. Taking the first 20,000 letters of Pushkin's Eugene Onegin, without punctuation or spaces, Markov sorted them into vowels and consonants: 8,638 vowels and 11,362 consonants. Counting pairs of adjacent letters showed that vowels and consonants tend to alternate: after a vowel, the next letter is a vowel only about 13 percent of the time. The letters of a text are not independent, and their dependence can be measured.

In 1948 Claude Shannon modeled text as a Markov process in the theory of information. The statistical language models that predict the next word from the previous ones descend from that idea.

Two circles, vowel and consonant, joined by arrows in both directions, with a loop on each; every arrow carries its percentage.

The two classes of letters in Eugene Onegin as a two-state chain, with the transition frequencies Markov counted.

Under the hood

A Markov chain is a sequence of states in which the probability of the next one depends only on the current one: P(Xₙ₊₁ | Xₙ, Xₙ₋₁, …) = P(Xₙ₊₁ | Xₙ). It is described by a transition matrix, whose row i gives the probabilities of moving from state i to each of the others.

In the analysis of Eugene Onegin there are two states, vowel and consonant. Markov estimated the probability of each transition by counting pairs of adjacent letters and found that they did not match what independent letters would give. A language model that predicts each word from the previous n is a Markov chain of order n.

Leads to

  • A Mathematical Theory of Communication (July 1948)

    Documented direct influence

    Shannon models the source of a message as a Markov process and illustrates it with letter-by-letter approximations to English

Sources

How to cite

“Markov chains.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/markov-chains

This entry was last reviewed on November 13, 2026.

Open in the interactive timeline