What is a Markov Chain?

- [Derek] But to Markov, Nekrasov was delusional. He thought it was absurd to link mathematical independence to free will. So Markov set out to prove that dependent events could also follow the law of large numbers, and that you can still do probability with dependent events. - To do this, he needed something where one event clearly depended on what came before, and he got the idea that this is what happens in text.

Whether your next letter is a consonant or a vowel depends heavily on what the current letter is. So to test this, Markov turned to a poem at the heart of Russian literature, "Eugene Onegin" by Alexander Pushkin. - He took the first 20,000 letters of the poem, stripped out all punctuation and spaces, and pushed them together into one long string of characters. He counted the letters and found that 43% were vowels and 57% were consonants.

Then Markov broke the string into overlapping pairs, that gave him four possible combinations, vowel-vowel, consonant-consonant, vowel-consonant, or consonant-vowel. Now, if the letters were independent, the probability of a vowel-vowel pair would just be the probability of a vowel twice, which is about 0.18 or an 18% chance. But when Markov actually counted, he found vowel-vowel pairs only show up 6% of the time, way less than if they were independent.

And when he checked the other pairs, he found that all actual values differed greatly from what the independent case would predict. So Markov had shown that the letters were dependent. And to beat Nekrasov, all he needed to do now was show that these letters still followed the law of large numbers. So he created a prediction machine of sorts. He started by drawing two circles, one for a vowel and one for a consonant.

These were his states. Now, say you're at a vowel, then the next letter could either be a vowel or a consonant. So he drew two arrows to represent these transitions. But what are these transition probabilities? Well, Markov knew that if you pick a random starting point, there is a 43% chance that it'll be a vowel. He also knew that vowel-vowel pairs occur about 6% of the time. So to find the probability of going from a vowel to another vowel, he divided 0.06 by 0.43 to find a transition probability of about 13%.

And since there is a 100% chance that another letter comes next, all the arrows going from the same state need to add up to one. So the chance of going to a consonant is one minus 0.13, or 87%. He repeated this process for the consonants to complete his predictive machine. So let's see how it works. We'll start at a vowel. Next, we generate a random number between zero and one. If it's below 0.13, we get another vowel, if it's above, we get a consonant.

We got 0.78, so we get a consonant, then we generate another number, and check if it's above or below 0.67, 0.21, so we get a vowel. Now, we can keep doing this and keep track of the ratio of vowels to consonants. At first, the ratio jumps all over the place, but after a while, it converges to a steady value, 43% vowels and 57% consonants, the exact split Markov had counted by hand. So Markov had built a dependent system, a literal chain of events, and he showed that it still followed the law of large numbers, which meant that observing convergence in social statistics didn't prove that the underlying decisions were independent.

In other words, those statistics don't prove free will at all. Markov had shattered Nekrasov's argument, and he knew it. So he ended his paper with one final dig at his rival. "Thus, free will is not necessary to do probability." In fact, independence isn't even necessary to do probability. With this Markov chain, as it came to be known, he found a way to do probability with dependent events. This should have been a huge breakthrough, because in the real world, almost everything is dependent on something else.

I mean, the weather tomorrow depends on the conditions today. How a disease spreads depends on who's infected right now, and the behavior of particles depends on the behavior of particles around them. Many of these processes could be modeled using Markov chains. Do people think it was like a mic drop moment and like, "Oh, Nekrasov's out, like, Markov's the man"? Or people didn't really notice, or it was obscure, or?

- I feel like people didn't really notice, like, it wasn't a really big thing. And Markov himself seemingly didn't care much about how it might be applied to practical events. He wrote, "I'm concerned only with questions of pure analysis. I refer to the question of the applicability with indifference."