HomeVideos

The Strange Math That Predicts (Almost) Anything

Now Playing

The Strange Math That Predicts (Almost) Anything

Transcript

783 segments

0:00

- How many times do you need to shuffle a deck of cards

0:03

to make them truly random?

0:05

How much uranium does it take to build a nuclear bomb?

0:08

(explosion booming)

0:10

How can you predict the next word in a sentence?

0:12

And how does Google know which page

0:15

you're actually searching for?

0:17

Well, the reason we know the answer

0:18

to all of these questions

0:19

is because of a strange math feud in Russia

0:22

that took place over 100 years ago.

0:26

In 1905, socialist groups all across Russia

0:29

rose up against the Tsar, the ruler of the empire.

0:33

They demanded a complete political reform,

0:35

or failing that, that he stepped down from power entirely.

0:39

- This divided the nation into two.

0:41

So on one side you got the Tsarists, right?

0:44

They wanted to defend the status quo

0:46

and keep the Tsar in power.

0:48

But then on the other side,

0:49

you had the socialists

0:50

who wanted this complete political reform.

0:53

And this division was so bad

0:54

that it crept into every part of society

0:57

to the point where even mathematicians

0:59

started picking sides.

1:00

- [Derek] On the side of the Tsar was Pavel Nekrasov,

1:03

unofficially called the Tsar of Probability.

1:06

Nekrasov was a deeply religious and powerful man,

1:10

and he used his status to argue that math could be used

1:13

to explain free will and the will of God.

1:16

- His intellectual nemesis on the socialist side

1:19

was Andrey Markov, also known as Andrey The Furious.

1:24

Markov was an atheist

1:25

and he had no patience for people

1:27

who were being unrigorous,

1:29

something he considered Nekrasov to be,

1:31

because in his eyes,

1:32

math had nothing to do with free will or religion.

1:35

So he publicly criticized Nekrasov's work,

1:38

listing it among "the abuses of mathematics."

1:41

Their feud centered on the main idea

1:43

people had used to do probability for the last 200 years.

1:46

And we can illustrate this with a simple coin flip.

1:50

When I flip the coin 10 times,

1:51

I get six times heads and four times tails,

1:54

which is obviously not the 50/50 you'd expect.

1:57

But if I keep flipping the coin,

1:59

then at first the ratio jumps all over the place.

2:02

But after a large number of flips,

2:04

we see that it slowly settles down and approaches 50/50.

2:08

And in this case, after 100 flips,

2:10

we end up on 51 heads and 49 tails,

2:14

which is almost exactly what you would expect.

2:17

This behavior that the average outcome

2:19

gets closer and closer to the expected value

2:22

as you run more and more independent trials

2:24

is known as the law of large numbers.

2:27

It was first proven by Jacob Bernoulli in 1713,

2:30

and it was the key concept

2:32

at the heart of probability theory

2:34

right up until Markov and Nekrasov.

2:36

But Bernoulli only proved

2:38

that it worked for independent events

2:40

like a fair coin flip,

2:42

or when you ask people to guess

2:43

how much they think an item is worth,

2:45

where one event doesn't influence the others.

2:49

But now imagine that instead of asking each person

2:52

to submit their guess individually,

2:54

you ask people to shout out their answer in public.

2:57

Well, in this case,

2:58

the first person might think

3:00

it's an extraordinarily valuable item,

3:02

and say it's worth around $2,000,

3:05

but now all the other people in the room

3:07

are influenced by this value,

3:09

and so, their guesses have become dependent.

3:12

And now the average doesn't converge to the true value,

3:16

but instead it clusters around a higher amount.

3:19

- And so, for 200 years,

3:21

probability had relied on this key assumption,

3:24

that you need independence

3:26

to observe the law of large numbers.

3:28

And this was the idea

3:30

that sparked Nekrasov and Markov's feud.

3:32

See, Nekrasov agreed with Bernoulli

3:34

that you need independence to get the law of large numbers.

3:37

But he took it one step further.

3:39

He said, if you see the law of large numbers,

3:42

you can infer that the underlying events

3:44

must be independent.

3:47

- Take this table of Belgian marriages from 1841 to 1845.

3:52

Now you see that every year the average is about 29,000.

3:55

And so, it seems like the values converge

3:58

and therefore that they follow the law of large numbers.

4:01

And when Nekrasov looked at other social statistics

4:03

like crime rates and birth rates,

4:05

he noticed a similar pattern.

4:07

But now think about where all this data is coming from.

4:10

It's coming from decisions to get married,

4:12

decisions to commit crimes,

4:14

and decisions to have babies,

4:16

at least for the most part.

4:18

So Nekrasov reasoned that because these statistics

4:20

followed the law of large numbers,

4:22

the decisions causing them must be independent.

4:24

In other words,

4:25

he argued that they must be acts of free will.

4:29

So to him, free will wasn't just something philosophical,

4:32

it was something you could measure.

4:34

It was scientific.

4:37

- [Derek] But to Markov, Nekrasov was delusional.

4:40

He thought it was absurd

4:41

to link mathematical independence to free will.

4:45

So Markov set out to prove that dependent events

4:48

could also follow the law of large numbers,

4:51

and that you can still do probability with dependent events.

4:56

- To do this, he needed something

4:57

where one event clearly depended on what came before,

5:01

and he got the idea that this is what happens in text.

5:04

Whether your next letter is a consonant or a vowel

5:07

depends heavily on what the current letter is.

5:10

So to test this, Markov turned to a poem

5:13

at the heart of Russian literature,

5:15

"Eugene Onegin" by Alexander Pushkin.

5:19

- He took the first 20,000 letters of the poem,

5:21

stripped out all punctuation and spaces,

5:24

and pushed them together into one long string of characters.

5:27

He counted the letters

5:28

and found that 43% were vowels and 57% were consonants.

5:33

Then Markov broke the string into overlapping pairs,

5:37

that gave him four possible combinations,

5:39

vowel-vowel, consonant-consonant,

5:41

vowel-consonant, or consonant-vowel.

5:44

Now, if the letters were independent,

5:46

the probability of a vowel-vowel pair

5:48

would just be the probability of a vowel twice,

5:51

which is about 0.18 or an 18% chance.

5:56

But when Markov actually counted,

5:58

he found vowel-vowel pairs only show up 6% of the time,

6:03

way less than if they were independent.

6:06

And when he checked the other pairs,

6:07

he found that all actual values differed greatly

6:10

from what the independent case would predict.

6:13

So Markov had shown that the letters were dependent.

6:18

And to beat Nekrasov, all he needed to do now was show

6:21

that these letters still followed the law of large numbers.

6:24

So he created a prediction machine of sorts.

6:28

He started by drawing two circles,

6:30

one for a vowel and one for a consonant.

6:32

These were his states.

6:34

Now, say you're at a vowel,

6:36

then the next letter could either be a vowel or a consonant.

6:39

So he drew two arrows to represent these transitions.

6:42

But what are these transition probabilities?

6:46

Well, Markov knew that if you pick a random starting point,

6:49

there is a 43% chance that it'll be a vowel.

6:52

He also knew that vowel-vowel pairs

6:54

occur about 6% of the time.

6:57

So to find the probability

6:58

of going from a vowel to another vowel,

7:00

he divided 0.06 by 0.43

7:03

to find a transition probability of about 13%.

7:07

And since there is a 100% chance

7:09

that another letter comes next,

7:11

all the arrows going from the same state

7:13

need to add up to one.

7:15

So the chance of going to a consonant

7:17

is one minus 0.13, or 87%.

7:21

He repeated this process for the consonants

7:23

to complete his predictive machine.

7:25

So let's see how it works.

7:28

We'll start at a vowel.

7:31

Next, we generate a random number between zero and one.

7:34

If it's below 0.13, we get another vowel,

7:37

if it's above, we get a consonant.

7:39

We got 0.78, so we get a consonant,

7:42

then we generate another number,

7:43

and check if it's above or below 0.67,

7:46

0.21, so we get a vowel.

7:50

Now, we can keep doing this

7:51

and keep track of the ratio of vowels to consonants.

7:54

At first, the ratio jumps all over the place,

7:57

but after a while, it converges to a steady value,

8:00

43% vowels and 57% consonants,

8:04

the exact split Markov had counted by hand.

8:09

So Markov had built a dependent system,

8:11

a literal chain of events,

8:13

and he showed that it still followed

8:15

the law of large numbers,

8:17

which meant that observing convergence in social statistics

8:20

didn't prove that the underlying decisions were independent.

8:23

In other words,

8:24

those statistics don't prove free will at all.

8:27

Markov had shattered Nekrasov's argument, and he knew it.

8:31

So he ended his paper with one final dig at his rival.

8:34

"Thus, free will is not necessary to do probability."

8:39

In fact, independence

8:40

isn't even necessary to do probability.

8:43

With this Markov chain, as it came to be known,

8:45

he found a way to do probability with dependent events.

8:49

This should have been a huge breakthrough,

8:51

because in the real world,

8:53

almost everything is dependent on something else.

8:56

I mean, the weather tomorrow

8:57

depends on the conditions today.

9:00

How a disease spreads

9:01

depends on who's infected right now,

9:03

and the behavior of particles

9:05

depends on the behavior of particles around them.

9:08

Many of these processes

9:10

could be modeled using Markov chains.

9:13

Do people think it was like a mic drop moment

9:15

and like, "Oh, Nekrasov's out, like, Markov's the man"?

9:19

Or people didn't really notice, or it was obscure, or?

9:22

- I feel like people didn't really notice,

9:25

like, it wasn't a really big thing.

9:28

And Markov himself seemingly didn't care much

9:31

about how it might be applied to practical events.

9:34

He wrote, "I'm concerned only with questions

9:37

of pure analysis.

9:38

I refer to the question of the applicability

9:41

with indifference."

9:43

Little did he know that this new form of probability theory

9:47

would soon play a major role

9:49

in one of the most important developments

9:51

of the 20th century.

9:54

On the morning of the 16th of July, 1945,

9:58

the United States detonated The Gadget,

10:01

the world's first nuclear bomb.

10:04

The six kilogram plutonium bomb created an explosion

10:08

that was equivalent to nearly 25,000 tons of TNT.

10:12

This was the culmination

10:14

of the top secret Manhattan Project,

10:16

a three-year long effort

10:18

by some of the smartest people alive,

10:20

including people like J. Robert Oppenheimer,

10:23

John von Neumann,

10:24

and a little known mathematician named Stanislaw Ulam.

10:29

- [Derek] Even after the war ended,

10:31

Ulam continued trying to figure out

10:33

how neutrons behave inside a nuclear bomb.

10:35

Now, a nuclear bomb works something like this.

10:38

Say you have a core of uranium-235,

10:41

then when a neutron hits a U-235 nucleus,

10:44

the nucleus splits releasing energy

10:46

and, crucially, two or three more neutrons.

10:50

If, on average, those new neutrons go on to hit

10:52

and split more than one other U-235 nucleus,

10:56

you get a runaway chain reaction,

10:58

so you have a nuclear bomb.

11:00

But uranium-235, the fissile fuel needed for the bombs

11:03

was really hard to get.

11:05

So one of the key questions was just how much of it

11:08

do you need to build a bomb?

11:10

And this is why Ulam wanted to understand

11:12

how the neutrons behave.

11:15

- [Casper] But then in January of 1946,

11:18

everything came to a halt.

11:20

Ulam was struck by a sudden and severe case of encephalitis,

11:24

an inflammation of the brain, that nearly killed him.

11:28

His recovery was long and slow,

11:30

with Ulam spending most of his time in beds.

11:34

To pass the time, he played a simple card game, Solitaire.

11:38

But as he played countless games,

11:40

winning some, losing others,

11:42

one question kept nagging at him,

11:45

what are the chances

11:46

that a randomly-shuffled game of Solitaire could be won?

11:50

It was a deceivingly difficult problem to solve.

11:53

Ulam played with all 52 cards

11:55

where each arrangement created a unique game,

11:58

so the total number of possible games was 52 factorial,

12:02

or about eight times 10 to 67.

12:06

So solving this analytically was hopeless.

12:10

But then Ulam had a flash of insight,

12:12

what if I just play hundreds of games

12:14

and count how many could be won?

12:16

That would give him

12:17

some sort of statistical approximation of the answer.

12:21

Back at Los Alamos, the remaining scientists

12:23

grappled with much harder problems than Solitaire,

12:26

like figuring out how neutrons behave inside a nuclear core.

12:31

In a nuclear core,

12:32

there are trillions and trillions of neutrons

12:34

all interacting with their surroundings.

12:36

So the number of possible outcomes is immense,

12:39

and computing it directly seemed impossible.

12:42

- [Derek] But when Ulam returned to work,

12:44

he had a sudden revelation.

12:46

What if we could simulate these systems

12:48

by generating lots of random outcomes

12:50

like I did with Solitaire?

12:52

He shared this idea with von Neumann,

12:54

who immediately recognized its power,

12:57

but also spotted a key problem.

13:00

- See, in Solitaire, each game is independent.

13:03

How the cards are dealt in one game

13:05

have no effect on the next, but neutrons aren't like that.

13:09

A neutron's behavior depends on where it is

13:11

and what it has done before.

13:14

So you couldn't just sample random outcomes

13:17

like in Solitaire.

13:18

Instead, you needed to model a whole chain of events

13:21

where each step influenced the next.

13:24

What von Neumann realized

13:25

is that you needed a Markov chain.

13:28

So they made one

13:30

and a much simplified version of it

13:32

works something like this.

13:34

Now, the starting state

13:35

is just a neutron traveling through the core,

13:37

and from there, three things can happen.

13:39

It can scatter off an atom and keep traveling,

13:42

so that gives you an arrow going back to itself.

13:45

It can leave the system

13:46

or get absorbed by a non-fissile material,

13:49

in which case it no longer takes part in the chain reaction,

13:52

and so it ends its Markov chain,

13:55

or it can strike another uranium-235 atom,

13:58

triggering a fission event

14:00

and releasing two or three more neutrons

14:02

that then start their own chains.

14:05

But in this chain,

14:06

the transition probabilities aren't fixed,

14:08

they depend on things like the neutron's position,

14:11

velocity and energy,

14:12

as well as the overall configuration and mass of uranium.

14:16

So a fast-moving neutron might have a 30% chance to scatter,

14:20

a 50% chance to be absorbed or leave,

14:22

and a 20% chance to cause fission.

14:25

But a slower-moving neutron

14:26

would have different probabilities.

14:29

Next, they ran this chain

14:31

on the world's first electronic computer, the ENIAC.

14:34

The computer started

14:35

by randomly generating a neutron starting conditions

14:38

and stepped through the chain

14:39

to keep track of how many neutrons

14:40

were produced on average per run,

14:43

known as the multiplication factor k.

14:46

So if, on average, one neutron

14:48

produces another two neutrons, then k is equal to two.

14:52

And if on average every two neutrons produce three neutrons,

14:55

then k is equal to three over two, and so on.

14:59

Then, after stepping through the full chain

15:01

for a specified number of steps,

15:03

we collect the average k-value

15:04

and record that number in a histogram.

15:07

This process was then repeated hundreds of times,

15:10

and the results tallied up,

15:11

giving you a statistical distribution of the outcome.

15:15

If you find that in most cases, k is less than one,

15:18

the reaction dies down.

15:19

If it's equal to one,

15:21

there's a self-sustaining chain reaction,

15:23

but it doesn't grow.

15:24

And if k is larger than one,

15:26

the reaction grows exponentially

15:28

and you've got a bomb.

15:31

- With it, von Neumann and Ulam had a statistical way

15:34

to figure out how many neutrons were produced

15:36

without having to do any exact calculations.

15:39

In other words,

15:40

they could approximate differential equations

15:42

that were too hard to solve analytically.

15:45

All that was needed was a name for the new method.

15:48

Now, Ulam's uncle was a gambler,

15:51

and the random sampling

15:52

and high stakes reminded Ulam

15:54

of the Monte Carlo Casino in Monaco, and the name stuck.

15:58

The Monte Carlo method was born.

16:01

The method was so successful

16:03

that it didn't stay secret for long.

16:05

By the end of 1948,

16:07

scientists at another lab, Argonne, in Chicago,

16:10

used it to study nuclear reactor designs,

16:13

and from there, the idea spread quickly.

16:16

Ulam later remarked,

16:18

"It is still an unending source of surprise for me

16:21

to see how a few scribbles on a blackboard

16:23

could change the course of human affairs."

16:27

And it wouldn't be the last time

16:28

Markov chain based method

16:30

changed the course of human affairs.

16:32

(upbeat music)

16:35

- In 1993, the internet was open to the public,

16:39

and soon it exploded.

16:41

By the mid-1990s, thousands of new pages appeared every day,

16:44

and that number was only growing.

16:48

This created a new kind of problem.

16:50

I mean, how do you find anything

16:52

in this ever-expending sea of information?

16:55

In 1994, two Stanford PhD students,

16:58

Jerry Yang and David Filo,

17:00

founded the search engine Yahoo,

17:02

to address this issue, but they needed money.

17:06

So a year later, they arranged to meet

17:08

with Japanese billionaire, Masayoshi Son,

17:11

also known as the Bill Gates of Japan.

17:13

(gong clangs)

17:15

- They were looking to raise $5 million

17:17

for their next startup, but Son has other plans.

17:22

He offers to invest a full $100 million instead.

17:26

That's 20 times more than what the founders asked for.

17:29

So Jerry Yang declines saying, "We don't need that much,"

17:33

but Son disagrees,

17:35

"Jerry, everyone needs $100 million."

17:38

(Son laughs)

17:40

Before the founders get a chance to respond,

17:42

Son jumps in again and asks,

17:44

"Who are your biggest competitors?"

17:46

"Excite and lycos," the pair respond.

17:49

Son orders his associate to write those names down.

17:51

And then he says, "If you don't let me invest in Yahoo,

17:54

I will invest in one of them and I'll kill you."

17:59

See, Son had realized something.

18:01

None of the leading search engines at the time

18:03

had any superior technology.

18:05

They didn't have a technological advantage over the others.

18:09

They all just ranked pages

18:10

by how often a search term appears on a given page.

18:14

So the battle for the number one search engine

18:16

would be decided by who could attract the most users,

18:19

who could spend the most on marketing.

18:21

- [Announcer 1] Lycos, go get it.

18:23

- [Announcer 2] Get Lycos, or get lost.

18:26

- [Announcer 3] This is revolution.

18:28

(upbeat funky music)

18:31

♪ Yahoo ♪

18:33

- [Derek] And marketing required a lot of money,

18:35

money that Son had, so he could decide who won the war.

18:40

Yahoo's founders realized they were left with no real choice

18:43

but to accept Son's investment.

18:46

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

18:48

- [Derek] And within four years,

18:49

Yahoo became the most popular site on the planet.

18:52

- [Reporter] In the time it takes to say this sentence,

18:55

Yahoo will answer 79,000 information requests worldwide,

19:00

the two men are now worth $120 million each.

19:04

♪ Yahoo ♪

19:07

- But Yahoo had a critical weakness.

19:11

See, Yahoo's keyword search was easy to trick.

19:14

To get your page ranked highly,

19:15

you could just repeat keywords hundreds of times,

19:18

hidden with white text on a white background.

19:21

- One thing they didn't have in those early days

19:25

was a notion of quality of the result.

19:28

So they had a notion of relevance saying,

19:31

does this document talk about the thing

19:33

that you're interested in?

19:35

But there wasn't really a notion of which ones are better.

19:39

- What they really needed was a way to rank pages

19:41

by both relevance and quality.

19:44

But how do you measure the quality of a webpage?

19:46

Well, to understand that,

19:48

we need to borrow an idea from libraries.

19:50

- So I'm old enough that library books

19:53

used to have a paper card in it

19:55

that was a stamp of all the due dates

19:57

of when it was due back.

19:58

You took a book and if it had a lot of those,

20:00

you said, "Oh, this is probably a good book."

20:01

And if it didn't have any, you said,

20:03

"Well, maybe this isn't the best book."

20:06

- Stamps acted like endorsements.

20:07

The more stamps, the better the book must be.

20:09

And the same idea can be applied to the web.

20:12

Over at Stanford, two PhD students,

20:15

Sergey Brin and Larry Page,

20:16

were working on this exact problem.

20:19

Brin and Page realized that each link to a page

20:22

can be thought of as an endorsement.

20:24

And the more links a page sends out,

20:26

the less valuable each vote becomes.

20:29

So what they realized is that we can model the web

20:32

as a Markov chain.

20:34

- [Derek] To see how this works,

20:36

imagine a toy internet with just four webpages.

20:39

Call them Amy, Ben, Chris, and Dan.

20:42

These are our states.

20:44

Typically, one webpage links to others,

20:46

allowing you to move between them.

20:48

These are our transitions.

20:50

In this setup, Amy only links to Ben,

20:52

so there's a 100% chance of going from Amy to Ben.

20:56

Ben links to Amy, Chris, and Dan,

20:58

so there's a 33% chance of going to any of those pages,

21:02

and we can fill out the other transition probabilities

21:05

in the same way.

21:07

So now we can run this Markov chain and see what happens.

21:10

Imagine you're a surfer on this web.

21:13

You start on a random page, say, Amy,

21:15

and you keep running the machine

21:17

and keep track of the percentage of time

21:19

you spend on each page.

21:21

Over time, the ratio settles

21:23

and the scores give us some measure

21:25

of the relative importance of these pages.

21:28

You spend the most time on Ben,

21:29

so Ben is ranked first, followed by Amy, then Dan,

21:32

and lastly Chris.

21:34

It might seem like there's an easy way to beat the system,

21:37

just make 100 pages all linking to your website.

21:40

Now you get 100 full votes

21:42

and you'll always rank on top, but that is not the case.

21:47

While during their first few steps,

21:48

they might make your page seem important,

21:50

none of the other websites link to them.

21:53

So over many steps, their contributions don't matter.

21:57

You might have many links,

21:58

but they're not quality links,

22:00

so they don't affect the algorithm.

22:03

- But there is still one problem, though,

22:05

not all pages are connected.

22:07

In networks like this one,

22:09

a random server can get stuck in a loop,

22:11

never reaching the rest of the web.

22:13

So to fix this,

22:15

we can set a rule that 85% of the time,

22:17

our random server just follows a link like normal.

22:20

But then for about 15% of the time,

22:22

they just jump to a page at random.

22:25

This damping factor makes sure

22:27

that we explore all possible parts of the web

22:29

without ever getting stuck.

22:32

By using Markov chains,

22:34

Page and Brin had built a better search engine,

22:36

and they called it PageRank.

22:38

- Because it's talking about how pages react,

22:42

webpages react with each other

22:43

and also 'cause the founder's name is Larry Page,

22:46

so he snuck that in.

22:48

- With PageRank,

22:49

Google got much better search results,

22:51

often getting you to the site

22:52

you were looking for in one go.

22:54

Although, to some, this sounded like a terrible idea.

22:58

- Others said, "Oh, well you're telling me you get a search

23:00

that will get the right result on the first answer?

23:04

Well, I don't want that

23:05

because if it takes them three or four chances,

23:08

searches to get the right answer,

23:10

then I have three or four chances to show ads,

23:13

and if you get 'em the answer right away,

23:15

I'm just gonna lose them.

23:16

So, you know, I don't see why better search is better."

23:20

- But Page and Brin disagreed.

23:22

They were convinced that if their product was far superior,

23:24

then people would flock to it.

23:26

- I would say it actually is a democracy that works.

23:30

If all pages were equal,

23:32

anybody can manufacture as many pages as they want.

23:35

I can set up a billion pages in my server tomorrow.

23:38

We shouldn't treat them all as equal.

23:40

Just looking at the data out of curiosity,

23:42

we found that we had technology

23:44

to do a better job of search,

23:45

and we realized how impactful having great search can be.

23:49

- And so, in 1998, they launched their new search engine

23:53

to take on Yahoo.

23:54

Initially, they called it BackRub,

23:56

after the backlinks it analyzed,

23:58

but then they realized

23:59

that maybe that's not the most attractive name.

24:02

Now, their ambitions were big

24:03

to essentially index all the pages on the internet,

24:06

and they needed a name equally as big.

24:09

So they thought of the largest number they could think of,

24:12

10 to the power of 100, a googol.

24:15

But then when trying to register their domain,

24:17

they accidentally misspelled it.

24:19

And so, Google was born.

24:21

(dramatic music)

24:26

Over the next four years,

24:27

Google overthrew Yahoo

24:29

to become the most used search engine.

24:31

- Everyone who knows the internet

24:32

almost certainly knows Google.

24:34

- Googling is like oxygen to teenagers.

24:37

- [Casper] And today, Alphabet,

24:39

which is Google's parent company,

24:40

is worth around $2 trillion.

24:43

- When Google makes even the slightest change

24:45

in its algorithms, it can have huge effects.

24:48

- Google. - Google.

24:49

- Google. - Google.

24:51

- They're on fire.

24:52

And the reason why they're on fire

24:53

is because they're focused

24:55

and they're more focused than Yahoo who does search,

24:57

they're more focused than Microsoft

24:58

who does search with Bing.

24:59

Yahoo has lots of traffic, they always have,

25:01

they have some really great properties,

25:03

but I don't think Yahoo is the go-to place, you know.

25:06

- And at the heart of this trillion dollar algorithm

25:09

is a Markov chain, which only looks at the current state

25:12

to predict what's going to happen next.

25:15

But in the 1940s, Claude Shannon,

25:18

the father of information theory,

25:20

started asking a different question.

25:23

He went back to Markov's original idea of predicting text,

25:26

but instead of just using vowels and consonants,

25:29

he focused on individual letters.

25:31

And he wondered,

25:32

what if instead of looking

25:34

at only the last letter as a predictor,

25:36

I look at the last two?

25:37

Well, with that, he got text that looked like this.

25:41

Now, it doesn't make much sense,

25:42

but there are some recognizable words

25:44

like "whey", "of", and "the".

25:47

But Shannon was convinced he could do better.

25:49

So next, instead of looking at letters,

25:52

he wondered, what if I use entire words as predictors?

25:55

That gave him sentences like this,

25:57

"The head and in frontal attack on an English writer

26:00

that the character of this point

26:02

is therefore another method for the letters

26:04

that the time of who ever told the problem

26:07

for an unexpected."

26:09

Now, clearly, this doesn't make any sense,

26:12

but Shannon did notice that sequences of four words or so

26:15

generally did make sense.

26:17

For instance, "attack on an English writer"

26:19

kind of makes sense.

26:21

So Shannon learned that you can make better

26:23

and better predictions

26:24

about what the next word is going to be

26:26

by taking into account more and more of the previous words.

26:30

It's kind of like what Gmail does

26:32

when it predicts what you're going to type next.

26:35

And this is no coincidence,

26:37

the algorithms that make these predictions

26:39

are based on Markov chains.

26:41

- They're not necessarily using letters, you know,

26:44

-Yeah

26:45

they use what they call tokens,

26:47

some of which are letters, some of which are words,

26:50

marks of punctuation, whatever.

26:52

So it's a bigger set than just the alphabet.

26:56

The game is simply, we have this string of tokens

27:00

that, you know, might be 30 long,

27:04

and we're asking what are the odds

27:06

that the next token is this or this or this?

27:09

- [Derek] But today's large language models

27:10

don't treat all those tokens equally,

27:13

because unlike simple Markov chains,

27:15

they also use something called attention,

27:17

which tells the model what to pay attention to.

27:20

So in the phrase, "the structure of the cell,"

27:22

the model can use previous context

27:24

like blood and mitochondria

27:25

to know the cell most likely refers

27:28

to biology rather than a prison cell.

27:30

And it uses that to tune its prediction.

27:33

But as large language models become more widespread,

27:36

one concern is that the text they produce

27:38

ends up on the internet

27:39

and that becomes training data for future models.

27:43

- When you start doing that,

27:47

the game is very soon over.

27:48

You come, in this case, to us, a very dull, stable state,

27:52

it just says the same thing

27:53

over and over and over again forever.

27:55

The language models are vulnerable to this process.

27:59

- And any system like this where we have a feedback loop,

28:02

will become hard to model using Markov chains.

28:05

Take global warming, for instance,

28:07

as we increase the amount of carbon dioxide in the air,

28:09

the average temperature of the Earth increases.

28:12

But as the temperature increases,

28:13

the atmosphere can hold more water vapor,

28:15

which is an incredibly powerful greenhouse gas.

28:18

And with more water vapor,

28:19

the temperature increases further

28:21

allowing for even more water vapor.

28:23

So you get this positive feedback loop,

28:25

which makes it hard to predict what's going to happen next.

28:28

So there are some systems where Markov chains don't work,

28:31

but for many other dependent systems,

28:33

they offer a way of doing probability.

28:36

- But what's fascinating

28:37

is that all these systems have extremely long histories.

28:41

I mean, you could trace back all the letters in a text,

28:43

trace back all the interactions of what a neutron did,

28:46

or trace back the weather for weeks.

28:49

But the beautiful thing Markov and others found

28:51

is that for many of these systems

28:53

you can ignore almost all of that.

28:55

You can just look at the current state

28:57

and forget about the rest,

29:00

that makes these systems memoryless.

29:02

And it's this memoryless property

29:05

that makes Markov chains so powerful

29:07

because it's what allows you

29:09

to take these extremely complex systems

29:11

and simplify them a lot

29:13

to still make meaningful predictions.

29:16

- [Derek] As one paper put it, "Problem-solving

29:18

is often a matter of cooking up

29:19

an appropriate Markov chain."

29:22

- It's kind of ridiculous to me

29:23

that this basic fact of mathematics

29:26

would come out of a fight like that,

29:28

which, you know, really had nothing to do with it.

29:31

But all the evidence suggests

29:33

that it really was this determination

29:36

to show up Nekrasov that led Markov to do the work.

29:41

- But there's one question we still haven't answered.

29:44

When playing Solitaire,

29:46

how did Ulam know his cards were perfectly shuffled?

29:49

I mean, how many shuffles does it take

29:51

to get a completely random arrangement of cards?

29:56

- If you have a deck of cards,

29:57

you need to shuffle it, right?

30:00

How often, if you're shuffling, like, you know,

30:02

you split it in half, and then you do the

30:04

(cards riffling).

30:05

How often do you have to shuffle it

30:07

to make it completely random?

30:09

- Two. - Two?

30:11

I'm going with 26.

30:12

- Yeah, four times. - Four times?

30:13

- I don't know, 52 times?

30:15

- Okay. Okay.

30:16

It's not a bad guess.

30:18

- Seven?

30:19

- It is seven.

30:21

- Really? - Yeah.

30:22

So you can think of card shuffling as a Markov chain

30:24

where each deck arrangement is a state,

30:26

and then each shuffle is a step.

30:28

And so for a deck of 52 cards,

30:30

if you riffle shuffle it seven times,

30:32

then every arrangement of the deck is about equally likely,

30:35

so it's basically random.

30:38

But I can't shuffle like that.

30:40

So for me, what I do is I do it like this.

30:43

How many times do you think you have to shuffle like this

30:45

to get it random?

30:47

(beeping)

30:48

- What do you think?

30:49

And perhaps more importantly,

30:51

how would you go about working it out?

30:54

Well, that's where today's sponsor Brilliant comes in.

30:56

Brilliant is a learning app

30:57

that gets you hands-on with problems just like this.

31:01

Whether it's math, physics, programming,

31:03

or even AI, Brilliant's interactive lessons and challenges

31:07

let you play your way to a sharper mind.

31:09

You can discover how large language models actually work

31:12

from basic Markov chains to complex neural networks,

31:16

or dig into the math behind this shuffling question.

31:19

It's a fun way to build knowledge and skills

31:21

that help you solve all kinds of problems,

31:24

which brings us back to our shuffle.

31:26

So Casper, what actually is the answer?

31:29

- It's actually over 2,000.

31:31

- What? - Over-

31:32

- Crazy, right? - Yeah.

31:33

- So the next time someone offers to shuffle before a game,

31:36

make sure they're doing it right,

31:37

seven riffles or it doesn't count.

31:40

But the interesting part

31:41

isn't just knowing that, it's understanding why

31:43

and seeing how a simple question

31:45

can lead you to some surprisingly complex mathematics.

31:49

And that's what Brilliant is all about.

31:52

So to try everything Brilliant has to offer for free

31:55

for a full 30 days,

31:56

visit brilliant.org/veritasium,

31:58

click that link in the description

32:00

or scan this handy QR code.

32:02

And if you sign up,

32:03

you'll also get 20% off their annual premium subscription.

32:07

So I wanna thank Brilliant for sponsoring this video

32:09

and I wanna thank you for watching.

32:11

(upbeat music)

32:21

- Easy.

32:22

(light music)

Interactive Summary

The video explores the history and real-world applications of Markov chains, a mathematical concept born from a 1905 debate between mathematicians Andrey Markov and Pavel Nekrasov. While Nekrasov tried to use probability to argue for free will, Markov countered by developing a way to model dependent events, eventually creating what is now known as a Markov chain. The video illustrates how this 'memoryless' system—which predicts future states based solely on current ones—became essential for the Manhattan Project's Monte Carlo methods, Google's PageRank algorithm, and modern language modeling, while also addressing questions about card shuffling and randomization.

Suggested questions

4 ready-made prompts