Markov Chains

By 1906 the fight was already personal. Pavel Nekrasov, a pious, seminary-trained mathematician in Moscow, had been arguing that the law of large numbers required independence, and that independence was the statistical face of free will. Social counts settle. Crime figures settle. Nekrasov treated the settling as evidence that the acts underneath were voluntary, with no causal tug from one act to the next. Andrey Markov, a combative, atheist probabilist in Petersburg, called that performance “an abuse of mathematics.”

The law itself is older than either man. Jacob Bernoulli’s version, published in 1713 in Ars Conjectandi, says that independent trials average out. Flip a coin long enough and the share of heads sits near the coin’s true chance. The trials are forbidden to remember each other. Nekrasov treated the hypothesis as a requirement, and carried the requirement into an argument for free will. If the averages settle, the trials must have been independent. If human statistics settle, the humans must have been free. Markov went after the mathematical step. A sequence can remember its last outcome and still average out, if the memory is the right shape.

The 1906 paper builds the smallest such shape. Two states. The next state depends on the current one and on nothing earlier. That is the whole memory. For the first case he required every transition probability to sit strictly between zero and one, so the chain can always leave its current state, and no jump is certain. Under that condition, a long chain is very likely to spend a share of its time in each state close to one fixed value. The start washes out. The transitions remain. That is a weak law of large numbers for dependent trials. He widened the argument over the next few years. The name came later. Sergei Bernstein put “Markov chain” into print in 1926.

Markov’s temper was public. In February 1912 he asked the Holy Synod to excommunicate him. He gave his reasons: disbelief in the biblical stories, and no important difference between icons and idols. The Synod refused the rite. It recorded that he had already fallen away from the Church. An internal comment said excommunication would be too great an honor.

The demonstration that traveled was a poem. On 23 January 1913 Markov lectured the Imperial Academy of Sciences in St. Petersburg. The year was the Romanov tercentenary. It was also two hundred years since Bernoulli’s book. In a letter of 15 January he reminded the statistician Alexander Chuprov that the law of large numbers had a bicentenary, and asked that the anniversary be marked. For the lecture he took Alexander Pushkin’s Eugene Onegin, the whole first chapter and sixteen stanzas of the second, removed spaces and punctuation, and dropped the hard and soft signs, which do not sound by themselves. Twenty thousand letters remained. He called each letter a vowel or a consonant and counted. 8,638 vowels. 11,362 consonants. The vowel share was 0.432.

Independence would keep the chance of a vowel near 0.432 no matter what the previous letter was. Markov’s pairs sit far from that flat chance. A vowel followed a vowel 1,104 times. Divided by the 8,638 vowels, that chance is 0.128. After a consonant, the chance of a vowel rose to 0.663. Pushkin’s letters prefer to alternate. The next letter depends on the current one, and the lean is large. He did the arithmetic by hand, in two hundred blocks of one hundred letters. The same census on 100,000 letters of Sergei Aksakov’s childhood memoir gave a vowel share of 0.449, a vowel-after-vowel chance of 0.552, and a vowel-after-consonant chance of 0.365. Different book, different lean, same kind of chain. In the 1913 edition of his textbook he closed with Onegin as a good example of dependent trials that can still be treated as a simple chain.

The quarrel was a necessity claim. Nekrasov said the law of large numbers demands independence, and he carried that demand into an argument about free will. Markov showed a large class of dependent sequences still obey a weak law. The mathematical point he was fighting is closed.

The 1913 lecture did a second job. It showed this kind of dependence in the letters of a novel in verse that Russian schoolchildren recite. A memoryless vowel probability of 8,638 out of 20,000 would produce about 3,730 vowel-vowel pairs among the 19,999 adjacent pairs. Markov counted 1,104. The memoryless benchmark is more than three times that count. The name Markov chain is Bernstein’s, from 1926. The mathematics was already in the 1906 paper, and the poem was already in the lecture.

The existence of that share is settled. How fast a very large chain approaches it is a separate, active subject called mixing. Search rankings and sampling methods live on that speed. They rest on a theorem that already has its answer.