Markov Chains Explained: From Russian Feud to Modern Algorithms

[00:00:00]- How many times do you need to shuffle a deck of cards to make them truly random?

[00:00:05]How much uranium does it take to build a nuclear bomb?

[00:00:08](explosion booming) How can you predict the next word in a sentence?

[00:00:12]And how does Google know which page you're actually searching for?

[00:00:17]Well, the reason we know the answer to all of these questions is because of a strange math feud in Russia that took place over 100 years ago.

[00:00:26]In 1905, socialist groups all across Russia rose up against the Tsar, the ruler of the empire.

[00:00:33]They demanded a complete political reform, or failing that, that he stepped down from power entirely.

[00:00:39]- This divided the nation into two.

[00:00:41]So on one side you got the Tsarists, right?

[00:00:44]They wanted to defend the status quo and keep the Tsar in power.

[00:00:48]But then on the other side, you had the socialists who wanted this complete political reform.

[00:00:53]And this division was so bad that it crept into every part of society to the point where even mathematicians started picking sides.

[00:01:00]- [Derek] On the side of the Tsar was Pavel Nekrasov, unofficially called the Tsar of Probability.

[00:01:06]Nekrasov was a deeply religious and powerful man, and he used his status to argue that math could be used to explain free will and the will of God.

[00:01:16]- His intellectual nemesis on the socialist side was Andrey Markov, also known as Andrey The Furious.

[00:01:24]Markov was an atheist and he had no patience for people who were being unrigorous, something he considered Nekrasov to be, because in his eyes, math had nothing to do with free will or religion.

[00:01:35]So he publicly criticized Nekrasov's work, listing it among "the abuses of mathematics."

[00:01:41]Their feud centered on the main idea people had used to do probability for the last 200 years.

[00:01:46]And we can illustrate this with a simple coin flip.

[00:01:50]When I flip the coin 10 times, I get six times heads and four times tails, which is obviously not the 50/50 you'd expect.

[00:01:57]But if I keep flipping the coin, then at first the ratio jumps all over the place.

[00:02:02]But after a large number of flips, we see that it slowly settles down and approaches 50/50.

[00:02:08]And in this case, after 100 flips, we end up on 51 heads and 49 tails, which is almost exactly what you would expect.

[00:02:17]This behavior that the average outcome gets closer and closer to the expected value as you run more and more independent trials is known as the law of large numbers.

[00:02:27]It was first proven by Jacob Bernoulli in 1713, and it was the key concept at the heart of probability theory right up until Markov and Nekrasov.

[00:02:36]But Bernoulli only proved that it worked for independent events like a fair coin flip, or when you ask people to guess how much they think an item is worth, where one event doesn't influence the others.

[00:02:49]But now imagine that instead of asking each person to submit their guess individually, you ask people to shout out their answer in public.

[00:02:57]Well, in this case, the first person might think it's an extraordinarily valuable item, and say it's worth around $2,000, but now all the other people in the room are influenced by this value, and so, their guesses have become dependent.

[00:03:12]And now the average doesn't converge to the true value, but instead it clusters around a higher amount.

[00:03:19]- And so, for 200 years, probability had relied on this key assumption, that you need independence to observe the law of large numbers.

[00:03:28]And this was the idea that sparked Nekrasov and Markov's feud.

[00:03:32]See, Nekrasov agreed with Bernoulli that you need independence to get the law of large numbers.

[00:03:37]But he took it one step further.

[00:03:39]He said, if you see the law of large numbers, you can infer that the underlying events must be independent.

[00:03:47]- Take this table of Belgian marriages from 1841 to 1845.

[00:03:52]Now you see that every year the average is about 29,000.

[00:03:55]And so, it seems like the values converge and therefore that they follow the law of large numbers.

[00:04:01]And when Nekrasov looked at other social statistics like crime rates and birth rates, he noticed a similar pattern.

[00:04:07]But now think about where all this data is coming from.

[00:04:10]It's coming from decisions to get married, decisions to commit crimes, and decisions to have babies, at least for the most part.

[00:04:18]So Nekrasov reasoned that because these statistics followed the law of large numbers, the decisions causing them must be independent.

[00:04:24]In other words, he argued that they must be acts of free will.

[00:04:29]So to him, free will wasn't just something philosophical, it was something you could measure.

[00:04:34]It was scientific.

[00:04:37]- [Derek] But to Markov, Nekrasov was delusional.

[00:04:40]He thought it was absurd to link mathematical independence to free will.

[00:04:45]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.

[00:04:56]- 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.

[00:05:04]Whether your next letter is a consonant or a vowel depends heavily on what the current letter is.

[00:05:10]So to test this, Markov turned to a poem at the heart of Russian literature, "Eugene Onegin" by Alexander Pushkin.

[00:05:19]- 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.

[00:05:27]He counted the letters and found that 43% were vowels and 57% were consonants.

[00:05:33]Then Markov broke the string into overlapping pairs, that gave him four possible combinations, vowel-vowel, consonant-consonant, vowel-consonant, or consonant-vowel.

[00:05:44]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.

[00:05:56]But when Markov actually counted, he found vowel-vowel pairs only show up 6% of the time, way less than if they were independent.

[00:06:06]And when he checked the other pairs, he found that all actual values differed greatly from what the independent case would predict.

[00:06:13]So Markov had shown that the letters were dependent.

[00:06:18]And to beat Nekrasov, all he needed to do now was show that these letters still followed the law of large numbers.

[00:06:24]So he created a prediction machine of sorts.

[00:06:28]He started by drawing two circles, one for a vowel and one for a consonant.

[00:06:32]These were his states.

[00:06:34]Now, say you're at a vowel, then the next letter could either be a vowel or a consonant.

[00:06:39]So he drew two arrows to represent these transitions.

[00:06:42]But what are these transition probabilities?

[00:06:46]Well, Markov knew that if you pick a random starting point, there is a 43% chance that it'll be a vowel.

[00:06:52]He also knew that vowel-vowel pairs occur about 6% of the time.

[00:06:57]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%.

[00:07:07]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.

[00:07:15]So the chance of going to a consonant is one minus 0.13, or 87%.

[00:07:21]He repeated this process for the consonants to complete his predictive machine.

[00:07:25]So let's see how it works.

[00:07:28]We'll start at a vowel.

[00:07:31]Next, we generate a random number between zero and one.

[00:07:34]If it's below 0.13, we get another vowel, if it's above, we get a consonant.

[00:07:39]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.

[00:07:50]Now, we can keep doing this and keep track of the ratio of vowels to consonants.

[00:07:54]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.

[00:08:09]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.

[00:08:23]In other words, those statistics don't prove free will at all.

[00:08:27]Markov had shattered Nekrasov's argument, and he knew it.

[00:08:31]So he ended his paper with one final dig at his rival.

[00:08:34]"Thus, free will is not necessary to do probability."

[00:08:39]In fact, independence isn't even necessary to do probability.

[00:08:43]With this Markov chain, as it came to be known, he found a way to do probability with dependent events.

[00:08:49]This should have been a huge breakthrough, because in the real world, almost everything is dependent on something else.

[00:08:56]I mean, the weather tomorrow depends on the conditions today.

[00:09:00]How a disease spreads depends on who's infected right now, and the behavior of particles depends on the behavior of particles around them.

[00:09:08]Many of these processes could be modeled using Markov chains.

[00:09:13]Do people think it was like a mic drop moment and like, "Oh, Nekrasov's out, like, Markov's the man"?

[00:09:19]Or people didn't really notice, or it was obscure, or?

[00:09:22]- I feel like people didn't really notice, like, it wasn't a really big thing.

[00:09:28]And Markov himself seemingly didn't care much about how it might be applied to practical events.

[00:09:34]He wrote, "I'm concerned only with questions of pure analysis.

[00:09:38]I refer to the question of the applicability with indifference."

[00:09:43]Little did he know that this new form of probability theory would soon play a major role in one of the most important developments of the 20th century.

[00:09:54]On the morning of the 16th of July, 1945, the United States detonated The Gadget, the world's first nuclear bomb.

[00:10:04]The six kilogram plutonium bomb created an explosion that was equivalent to nearly 25,000 tons of TNT.

[00:10:12]This was the culmination of the top secret Manhattan Project, a three-year long effort by some of the smartest people alive, including people like J. Robert Oppenheimer, John von Neumann, and a little known mathematician named Stanislaw Ulam.

[00:10:29]- [Derek] Even after the war ended, Ulam continued trying to figure out how neutrons behave inside a nuclear bomb.

[00:10:35]Now, a nuclear bomb works something like this.

[00:10:38]Say you have a core of uranium-235, then when a neutron hits a U-235 nucleus, the nucleus splits releasing energy and, crucially, two or three more neutrons.

[00:10:50]If, on average, those new neutrons go on to hit and split more than one other U-235 nucleus, you get a runaway chain reaction, so you have a nuclear bomb.

[00:11:00]But uranium-235, the fissile fuel needed for the bombs was really hard to get.

[00:11:05]So one of the key questions was just how much of it do you need to build a bomb?

[00:11:10]And this is why Ulam wanted to understand how the neutrons behave.

[00:11:15]- [Casper] But then in January of 1946, everything came to a halt.

[00:11:20]Ulam was struck by a sudden and severe case of encephalitis, an inflammation of the brain, that nearly killed him.

[00:11:28]His recovery was long and slow, with Ulam spending most of his time in beds.

[00:11:34]To pass the time, he played a simple card game, Solitaire.

[00:11:38]But as he played countless games, winning some, losing others, one question kept nagging at him, what are the chances that a randomly-shuffled game of Solitaire could be won?

[00:11:50]It was a deceivingly difficult problem to solve.

[00:11:53]Ulam played with all 52 cards where each arrangement created a unique game, so the total number of possible games was 52 factorial, or about eight times 10 to 67.

[00:12:06]So solving this analytically was hopeless.

[00:12:10]But then Ulam had a flash of insight, what if I just play hundreds of games and count how many could be won?

[00:12:16]That would give him some sort of statistical approximation of the answer.

[00:12:21]Back at Los Alamos, the remaining scientists grappled with much harder problems than Solitaire, like figuring out how neutrons behave inside a nuclear core.

[00:12:31]In a nuclear core, there are trillions and trillions of neutrons all interacting with their surroundings.

[00:12:36]So the number of possible outcomes is immense, and computing it directly seemed impossible.

[00:12:42]- [Derek] But when Ulam returned to work, he had a sudden revelation.

[00:12:46]What if we could simulate these systems by generating lots of random outcomes like I did with Solitaire?

[00:12:52]He shared this idea with von Neumann, who immediately recognized its power, but also spotted a key problem.

[00:13:00]- See, in Solitaire, each game is independent.

[00:13:03]How the cards are dealt in one game have no effect on the next, but neutrons aren't like that.

[00:13:09]A neutron's behavior depends on where it is and what it has done before.

[00:13:14]So you couldn't just sample random outcomes like in Solitaire.

[00:13:18]Instead, you needed to model a whole chain of events where each step influenced the next.

[00:13:24]What von Neumann realized is that you needed a Markov chain.

[00:13:28]So they made one and a much simplified version of it works something like this.

[00:13:34]Now, the starting state is just a neutron traveling through the core, and from there, three things can happen.

[00:13:39]It can scatter off an atom and keep traveling, so that gives you an arrow going back to itself.

[00:13:45]It can leave the system or get absorbed by a non-fissile material, in which case it no longer takes part in the chain reaction, and so it ends its Markov chain, or it can strike another uranium-235 atom, triggering a fission event and releasing two or three more neutrons that then start their own chains.

[00:14:05]But in this chain, the transition probabilities aren't fixed, they depend on things like the neutron's position, velocity and energy, as well as the overall configuration and mass of uranium.

[00:14:16]So a fast-moving neutron might have a 30% chance to scatter, a 50% chance to be absorbed or leave, and a 20% chance to cause fission.

[00:14:25]But a slower-moving neutron would have different probabilities.

[00:14:29]Next, they ran this chain on the world's first electronic computer, the ENIAC.

[00:14:34]The computer started by randomly generating a neutron starting conditions and stepped through the chain to keep track of how many neutrons were produced on average per run, known as the multiplication factor k.

[00:14:46]So if, on average, one neutron produces another two neutrons, then k is equal to two.

[00:14:52]And if on average every two neutrons produce three neutrons, then k is equal to three over two, and so on.

[00:14:59]Then, after stepping through the full chain for a specified number of steps, we collect the average k-value and record that number in a histogram.

[00:15:07]This process was then repeated hundreds of times, and the results tallied up, giving you a statistical distribution of the outcome.

[00:15:15]If you find that in most cases, k is less than one, the reaction dies down.

[00:15:19]If it's equal to one, there's a self-sustaining chain reaction, but it doesn't grow.

[00:15:24]And if k is larger than one, the reaction grows exponentially and you've got a bomb.

[00:15:31]- With it, von Neumann and Ulam had a statistical way to figure out how many neutrons were produced without having to do any exact calculations.

[00:15:39]In other words, they could approximate differential equations that were too hard to solve analytically.

[00:15:45]All that was needed was a name for the new method.

[00:15:48]Now, Ulam's uncle was a gambler, and the random sampling and high stakes reminded Ulam of the Monte Carlo Casino in Monaco, and the name stuck.

[00:15:58]The Monte Carlo method was born.

[00:16:01]The method was so successful that it didn't stay secret for long.

[00:16:05]By the end of 1948, scientists at another lab, Argonne, in Chicago, used it to study nuclear reactor designs, and from there, the idea spread quickly.

[00:16:16]Ulam later remarked, "It is still an unending source of surprise for me to see how a few scribbles on a blackboard could change the course of human affairs."

[00:16:27]And it wouldn't be the last time Markov chain based method changed the course of human affairs.

[00:16:32](upbeat music) - In 1993, the internet was open to the public, and soon it exploded.

[00:16:41]By the mid-1990s, thousands of new pages appeared every day, and that number was only growing.

[00:16:48]This created a new kind of problem.

[00:16:50]I mean, how do you find anything in this ever-expending sea of information?

[00:16:55]In 1994, two Stanford PhD students, Jerry Yang and David Filo, founded the search engine Yahoo, to address this issue, but they needed money.

[00:17:06]So a year later, they arranged to meet with Japanese billionaire, Masayoshi Son, also known as the Bill Gates of Japan.

[00:17:13](gong clangs) - They were looking to raise $5 million for their next startup, but Son has other plans.

[00:17:22]He offers to invest a full $100 million instead.

[00:17:26]That's 20 times more than what the founders asked for.

[00:17:29]So Jerry Yang declines saying, "We don't need that much," but Son disagrees, "Jerry, everyone needs $100 million."

[00:17:38](Son laughs) Before the founders get a chance to respond, Son jumps in again and asks, "Who are your biggest competitors?"

[00:17:46]"Excite and lycos," the pair respond.

[00:17:49]Son orders his associate to write those names down.

[00:17:51]And then he says, "If you don't let me invest in Yahoo, I will invest in one of them and I'll kill you."

[00:17:59]See, Son had realized something.

[00:18:01]None of the leading search engines at the time had any superior technology.

[00:18:05]They didn't have a technological advantage over the others.

[00:18:09]They all just ranked pages by how often a search term appears on a given page.

[00:18:14]So the battle for the number one search engine would be decided by who could attract the most users, who could spend the most on marketing.

[00:18:21]- [Announcer 1] Lycos, go get it.

[00:18:23]- [Announcer 2] Get Lycos, or get lost.

[00:18:26]- [Announcer 3] This is revolution.

[00:18:28](upbeat funky music) ♪ Yahoo ♪ - [Derek] And marketing required a lot of money, money that Son had, so he could decide who won the war.

[00:18:40]Yahoo's founders realized they were left with no real choice but to accept Son's investment.

[00:18:46]- [Speaker] So here we are, right in the middle of Yahoo.

[00:18:48]- [Derek] And within four years, Yahoo became the most popular site on the planet.

[00:18:52]- [Reporter] In the time it takes to say this sentence, Yahoo will answer 79,000 information requests worldwide, the two men are now worth $120 million each.

[00:19:04]♪ Yahoo ♪ - But Yahoo had a critical weakness.

[00:19:11]See, Yahoo's keyword search was easy to trick.

[00:19:14]To get your page ranked highly, you could just repeat keywords hundreds of times, hidden with white text on a white background.

[00:19:21]- One thing they didn't have in those early days was a notion of quality of the result.

[00:19:28]So they had a notion of relevance saying, does this document talk about the thing that you're interested in?

[00:19:35]But there wasn't really a notion of which ones are better.

[00:19:39]- What they really needed was a way to rank pages by both relevance and quality.

[00:19:44]But how do you measure the quality of a webpage?

[00:19:46]Well, to understand that, we need to borrow an idea from libraries.

[00:19:50]- So I'm old enough that library books used to have a paper card in it that was a stamp of all the due dates of when it was due back.

[00:19:58]You took a book and if it had a lot of those, you said, "Oh, this is probably a good book."

[00:20:01]And if it didn't have any, you said, "Well, maybe this isn't the best book."

[00:20:06]- Stamps acted like endorsements.

[00:20:07]The more stamps, the better the book must be.

[00:20:09]And the same idea can be applied to the web.

[00:20:12]Over at Stanford, two PhD students, Sergey Brin and Larry Page, were working on this exact problem.

[00:20:19]Brin and Page realized that each link to a page can be thought of as an endorsement.

[00:20:24]And the more links a page sends out, the less valuable each vote becomes.

[00:20:29]So what they realized is that we can model the web as a Markov chain.

[00:20:34]- [Derek] To see how this works, imagine a toy internet with just four webpages.

[00:20:39]Call them Amy, Ben, Chris, and Dan.

[00:20:42]These are our states.

[00:20:44]Typically, one webpage links to others, allowing you to move between them.

[00:20:48]These are our transitions.

[00:20:50]In this setup, Amy only links to Ben, so there's a 100% chance of going from Amy to Ben.

[00:20:56]Ben links to Amy, Chris, and Dan, so there's a 33% chance of going to any of those pages, and we can fill out the other transition probabilities in the same way.

[00:21:07]So now we can run this Markov chain and see what happens.

[00:21:10]Imagine you're a surfer on this web.

[00:21:13]You start on a random page, say, Amy, and you keep running the machine and keep track of the percentage of time you spend on each page.

[00:21:21]Over time, the ratio settles and the scores give us some measure of the relative importance of these pages.

[00:21:28]You spend the most time on Ben, so Ben is ranked first, followed by Amy, then Dan, and lastly Chris.

[00:21:34]It might seem like there's an easy way to beat the system, just make 100 pages all linking to your website.

[00:21:40]Now you get 100 full votes and you'll always rank on top, but that is not the case.

[00:21:47]While during their first few steps, they might make your page seem important, none of the other websites link to them.

[00:21:53]So over many steps, their contributions don't matter.

[00:21:57]You might have many links, but they're not quality links, so they don't affect the algorithm.

[00:22:03]- But there is still one problem, though, not all pages are connected.

[00:22:07]In networks like this one, a random server can get stuck in a loop, never reaching the rest of the web.

[00:22:13]So to fix this, we can set a rule that 85% of the time, our random server just follows a link like normal.

[00:22:20]But then for about 15% of the time, they just jump to a page at random.

[00:22:25]This damping factor makes sure that we explore all possible parts of the web without ever getting stuck.

[00:22:32]By using Markov chains, Page and Brin had built a better search engine, and they called it PageRank.

[00:22:38]- Because it's talking about how pages react, webpages react with each other and also 'cause the founder's name is Larry Page, so he snuck that in.

[00:22:48]- With PageRank, Google got much better search results, often getting you to the site you were looking for in one go.

[00:22:54]Although, to some, this sounded like a terrible idea.

[00:22:58]- Others said, "Oh, well you're telling me you get a search that will get the right result on the first answer?

[00:23:04]Well, I don't want that because if it takes them three or four chances, searches to get the right answer, then I have three or four chances to show ads, and if you get 'em the answer right away, I'm just gonna lose them.

[00:23:16]So, you know, I don't see why better search is better."

[00:23:20]- But Page and Brin disagreed.

[00:23:22]They were convinced that if their product was far superior, then people would flock to it.

[00:23:26]- I would say it actually is a democracy that works.

[00:23:30]If all pages were equal, anybody can manufacture as many pages as they want.

[00:23:35]I can set up a billion pages in my server tomorrow.

[00:23:38]We shouldn't treat them all as equal.

[00:23:40]Just looking at the data out of curiosity, we found that we had technology to do a better job of search, and we realized how impactful having great search can be.

[00:23:49]- And so, in 1998, they launched their new search engine to take on Yahoo.

[00:23:54]Initially, they called it BackRub, after the backlinks it analyzed, but then they realized that maybe that's not the most attractive name.

[00:24:02]Now, their ambitions were big to essentially index all the pages on the internet, and they needed a name equally as big.

[00:24:09]So they thought of the largest number they could think of, 10 to the power of 100, a googol.

[00:24:15]But then when trying to register their domain, they accidentally misspelled it.

[00:24:19]And so, Google was born.

[00:24:21](dramatic music) Over the next four years, Google overthrew Yahoo to become the most used search engine.

[00:24:31]- Everyone who knows the internet almost certainly knows Google.

[00:24:34]- Googling is like oxygen to teenagers.

[00:24:37]- [Casper] And today, Alphabet, which is Google's parent company, is worth around $2 trillion.

[00:24:43]- When Google makes even the slightest change in its algorithms, it can have huge effects.

[00:24:48]- Google. - Google.

[00:24:49]- Google. - Google.

[00:24:51]- They're on fire.

[00:24:52]And the reason why they're on fire is because they're focused and they're more focused than Yahoo who does search, they're more focused than Microsoft who does search with Bing.

[00:24:59]Yahoo has lots of traffic, they always have, they have some really great properties, but I don't think Yahoo is the go-to place, you know.

[00:25:06]- And at the heart of this trillion dollar algorithm is a Markov chain, which only looks at the current state to predict what's going to happen next.

[00:25:15]But in the 1940s, Claude Shannon, the father of information theory, started asking a different question.

[00:25:23]He went back to Markov's original idea of predicting text, but instead of just using vowels and consonants, he focused on individual letters.

[00:25:31]And he wondered, what if instead of looking at only the last letter as a predictor, I look at the last two?

[00:25:37]Well, with that, he got text that looked like this.

[00:25:41]Now, it doesn't make much sense, but there are some recognizable words like "whey", "of", and "the".

[00:25:47]But Shannon was convinced he could do better.

[00:25:49]So next, instead of looking at letters, he wondered, what if I use entire words as predictors?

[00:25:55]That gave him sentences like this, "The head and in frontal attack on an English writer that the character of this point is therefore another method for the letters that the time of who ever told the problem for an unexpected."

[00:26:09]Now, clearly, this doesn't make any sense, but Shannon did notice that sequences of four words or so generally did make sense.

[00:26:17]For instance, "attack on an English writer" kind of makes sense.

[00:26:21]So Shannon learned that you can make better and better predictions about what the next word is going to be by taking into account more and more of the previous words.

[00:26:30]It's kind of like what Gmail does when it predicts what you're going to type next.

[00:26:35]And this is no coincidence, the algorithms that make these predictions are based on Markov chains.

[00:26:41]- They're not necessarily using letters, you know, -Yeah they use what they call tokens, some of which are letters, some of which are words, marks of punctuation, whatever.

[00:26:52]So it's a bigger set than just the alphabet.

[00:26:56]The game is simply, we have this string of tokens that, you know, might be 30 long, and we're asking what are the odds that the next token is this or this or this?

[00:27:09]- [Derek] But today's large language models don't treat all those tokens equally, because unlike simple Markov chains, they also use something called attention, which tells the model what to pay attention to.

[00:27:20]So in the phrase, "the structure of the cell," the model can use previous context like blood and mitochondria to know the cell most likely refers to biology rather than a prison cell.

[00:27:30]And it uses that to tune its prediction.

[00:27:33]But as large language models become more widespread, one concern is that the text they produce ends up on the internet and that becomes training data for future models.

[00:27:43]- When you start doing that, the game is very soon over.

[00:27:48]You come, in this case, to us, a very dull, stable state, it just says the same thing over and over and over again forever.

[00:27:55]The language models are vulnerable to this process.

[00:27:59]- And any system like this where we have a feedback loop, will become hard to model using Markov chains.

[00:28:05]Take global warming, for instance, as we increase the amount of carbon dioxide in the air, the average temperature of the Earth increases.

[00:28:12]But as the temperature increases, the atmosphere can hold more water vapor, which is an incredibly powerful greenhouse gas.

[00:28:18]And with more water vapor, the temperature increases further allowing for even more water vapor.

[00:28:23]So you get this positive feedback loop, which makes it hard to predict what's going to happen next.

[00:28:28]So there are some systems where Markov chains don't work, but for many other dependent systems, they offer a way of doing probability.

[00:28:36]- But what's fascinating is that all these systems have extremely long histories.

[00:28:41]I mean, you could trace back all the letters in a text, trace back all the interactions of what a neutron did, or trace back the weather for weeks.

[00:28:49]But the beautiful thing Markov and others found is that for many of these systems you can ignore almost all of that.

[00:28:55]You can just look at the current state and forget about the rest, that makes these systems memoryless.

[00:29:02]And it's this memoryless property that makes Markov chains so powerful because it's what allows you to take these extremely complex systems and simplify them a lot to still make meaningful predictions.

[00:29:16]- [Derek] As one paper put it, "Problem-solving is often a matter of cooking up an appropriate Markov chain."

[00:29:22]- It's kind of ridiculous to me that this basic fact of mathematics would come out of a fight like that, which, you know, really had nothing to do with it.

[00:29:31]But all the evidence suggests that it really was this determination to show up Nekrasov that led Markov to do the work.

[00:29:41]- But there's one question we still haven't answered.

[00:29:44]When playing Solitaire, how did Ulam know his cards were perfectly shuffled?

[00:29:49]I mean, how many shuffles does it take to get a completely random arrangement of cards?

[00:29:56]- If you have a deck of cards, you need to shuffle it, right?

[00:30:00]How often, if you're shuffling, like, you know, you split it in half, and then you do the (cards riffling).

[00:30:05]How often do you have to shuffle it to make it completely random?

[00:30:09]- Two. - Two?

[00:30:11]I'm going with 26.

[00:30:12]- Yeah, four times. - Four times?

[00:30:13]- I don't know, 52 times?

[00:30:15]- Okay. Okay.

[00:30:16]It's not a bad guess.

[00:30:18]- Seven?

[00:30:19]- It is seven.

[00:30:21]- Really? - Yeah.

[00:30:22]So you can think of card shuffling as a Markov chain where each deck arrangement is a state, and then each shuffle is a step.

[00:30:28]And so for a deck of 52 cards, if you riffle shuffle it seven times, then every arrangement of the deck is about equally likely, so it's basically random.

[00:30:38]But I can't shuffle like that.

[00:30:40]So for me, what I do is I do it like this.

[00:30:43]How many times do you think you have to shuffle like this to get it random?

[00:30:47](beeping) - What do you think?

[00:30:49]And perhaps more importantly, how would you go about working it out?

[00:30:54]Well, that's where today's sponsor Brilliant comes in.

[00:30:56]Brilliant is a learning app that gets you hands-on with problems just like this.

[00:31:01]Whether it's math, physics, programming, or even AI, Brilliant's interactive lessons and challenges let you play your way to a sharper mind.

[00:31:09]You can discover how large language models actually work from basic Markov chains to complex neural networks, or dig into the math behind this shuffling question.

[00:31:19]It's a fun way to build knowledge and skills that help you solve all kinds of problems, which brings us back to our shuffle.

[00:31:26]So Casper, what actually is the answer?

[00:31:29]- It's actually over 2,000.

[00:31:31]- What? - Over- - Crazy, right? - Yeah.

[00:31:33]- So the next time someone offers to shuffle before a game, make sure they're doing it right, seven riffles or it doesn't count.

[00:31:40]But the interesting part isn't just knowing that, it's understanding why and seeing how a simple question can lead you to some surprisingly complex mathematics.

[00:31:49]And that's what Brilliant is all about.

[00:31:52]So to try everything Brilliant has to offer for free for a full 30 days, visit brilliant.org/veritasium, click that link in the description or scan this handy QR code.

[00:32:02]And if you sign up, you'll also get 20% off their annual premium subscription.

[00:32:07]So I wanna thank Brilliant for sponsoring this video and I wanna thank you for watching.

[00:32:11](upbeat music) - Easy.

[00:32:22](light music)