## Origin of Markov chains | Journey into information theory | Computer Science | Khan Academy

Voiceover: When observing

the natural world, many of us notice a somewhat

beautiful dichotomy. No two things are ever exactly alike, but they all seem to follow

some underlying form. Plato believed that the true forms of the universe were hidden from us. Through observation of the natural world, we could merely acquire

approximate knowledge of them. They were hidden blueprints. The pure forms were only

accessible through abstract reasoning of philosophy and mathematics. For example, the circle he describes as that which has the distance from its circumference to

its center everywhere equal. Yet we will never find

a material manifestation of a perfect circle or a

perfectly straight line. Though interestingly, Plato speculated that after an uncountable number of years, the universe will reach an ideal state, returning to its perfect form. This Platonic focus on abstract pure forms remained popular for centuries. It wasn’t until the 16th century when people tried to embrace the messy variation in the real world and apply mathematics to

tease out underlying patterns. Bernoulli refined the idea of expectation. He was focused on a method

of accurately estimating the unknown probability

of some event based on the number of times the event

occurs in independent trials. He uses a simple example. Suppose that without your knowledge, 3,000 light pebbles and 2,000 dark pebbles are hidden in an urn,

and that to determine the ratio of white versus

black by experiment, you draw one pebble after another, with replacement, and note how many times a white pebble is drawn versus black. He went on to prove

that the expected value of white versus black observations will converge on the actual ratio as the number of trials increases, known as the weak law of large numbers. He concluded by saying, “If observations “of all events be continued

for the entire infinity, “it will be noticed that

everything in the world “is governed by precise ratios “and a constant law of change.” This idea was quickly extended as it was noticed that not only did things converge on

an expected average, but the probability of

variation away from averages also follow a familiar, underlying shape, or distribution. A great example of this is

Francis Galton’s bean machine. Imagine each collision as

a single independent event, such as a coin flip. After 10 collisions or events, the bean falls into a bucket representing the ratio of left versus right deflection, or heads versus tails. This overall curvature, known

as the binomial distribution, appears to be an ideal form as it kept appearing everywhere any time you looked at the variation of a large number of random trials. It seems the average fate of these events is somehow predetermined, known today as the central limit theorem. This was a dangerous

philosophical idea to some. Pavel Nekrasov, originally

a theologian by training, later took up mathematics and was a strong proponent of the religious

doctrine of free will. He didn’t like the idea of us having this predetermined statistical fate. He made a famous claim that independence is a necessary condition for

the law of large numbers, since independence just

describes these toy examples using beans or dice, where the outcome of previous events doesn’t

change the probability of the current or future events. However, as we all can relate, most things in the physical world are clearly dependent on prior outcomes, such as the chance of fire or sun or even our life expectancy. When the probability

of some event depends, or is conditional, on previous events, we say they are dependent events, or dependent variables. This claim angered another

Russian mathematician, Andrey Markov, who

maintained a very public animosity towards Nekrasov. He goes on to say in a letter

that “this circumstance “prompts me to explain

in a series of articles “that the law of large numbers can apply “to dependent variables,” using a construction which he brags Nekrasov cannot even dream about. Markov extends Bernoulli’s results to dependent variables using

an ingenious construction. Imagine a coin flip

which isn’t independent, but dependent on the previous outcome, so it has short-term memory of one event. This can be visualized

using a hypothetical machine which contains two cups, which we call states. In one state we have a 50-50 mix of light versus dark beads, while in the other state we

have more dark versus light. One cup we can call state zero. It represents a dark

having previously occurred, and the other state, we can call one, it represents a light bead

having previously occurred. To run our machine, we simply

start in a random state and make a selection. Then we move to either state zero or one, depending on that event. Based on the outcome of that selection, we output either a zero if it’s dark, or a one if it’s light. With this two-state machine, we can identify four possible transitions. If we are in state zero

and a black occurs, we loop back to the same

state and select again. If a light bead is selected, we jump over to state one, which can

also loop back on itself, or jump back to state

zero if a dark is chosen. The probability of a light

versus dark selection is clearly not independent here, since it depends on the previous outcome. But Markov proved that

as long as every state in the machine is reachable, when you run these machines in a sequence, they reach equilibrium. That is, no matter where you start, once you begin the sequence, the number of times you visit each state converges to some specific

ratio, or a probability. This simple example

disproved Nekrasov’s claim that only independent

events could converge on predictable distributions. But the concept of modeling sequences of random events using states and transitions between states became known as a Markov chain. One of the first and

most famous applications of Markov chains was

published by Claude Shannon.

## Sid Hollander

August 26, 2014 at 11:44 pmSOUND!!!!!Are you kidding

## Alex Galea

February 11, 2015 at 12:42 amHey Brit, good video – where did you find the quote from Bernoulli about the universe being governed by ratios?

## TheResonating

May 10, 2015 at 3:09 am@Brit Cruise Im confused, are markov chains both independent and dependent? Because the next outcome only depends on the current one and not the previous ones before the current.

## Mubashir Ul Haq

November 29, 2015 at 2:16 amBrilliant explanation. 🙂

## Maitreyi Sinha

March 16, 2016 at 11:57 amThat was fantastic! Do you have more such videos on the Markov Property?

## Katherine Broderick

May 13, 2016 at 9:26 pmGreat explanation and perfect pacing. Thanks!

## Vinay Seth

September 5, 2016 at 4:37 pm3:34– Could someone please tel me the name of the theologian-turned-mathematician? Seems like an interesting guy; would love to read up on him, but the name wasn't clear in the video.

Oh, and brilliant video! Love Khan Academy for sharing these gems for free!

## diegofloor

October 28, 2016 at 4:18 pmThis is really good!

## annoying guy

December 18, 2016 at 5:51 amat least quantum tunneling of particles is random(unless there's a pattern, but that would be really bad).

## Michael Evans

January 15, 2017 at 8:26 pmI just love this video! Question: At 4 minutes, 30 seconds, what are the tables you are using? I can see how they sum up but I'm not sure of the application.

Also, the slide from 7 minutes and 3 seconds is used on Wikipedia talking about the Folding @ Home Project. Everyone check this out! Thanks again for a great video.

## wirechair

February 1, 2017 at 6:12 amthis was amazing. little bit cloudy on the transition states but this has been so much more enlightening than scholarly literature about it

## klam77

March 15, 2017 at 11:41 pmwow!

Plato –> Bernouilli

~~–~~> Nekrasove –>Markov! philosophy is mixed in! Love it!this isn't Sal Khan narrating?

## David Davidson

May 4, 2017 at 12:45 amI wish you would cite sources on videos like this that are more about historical facts than your original contributions.

Good video though!

## Crispin Semmens

December 5, 2017 at 9:55 pmexcellent backgrounder/intro!

## JD

January 2, 2018 at 11:59 am2018.

## Nima Sanjabi

February 4, 2018 at 3:29 amOne of the most inspiring videos I´ve seen during the last two years. I am an AI student, and the first video that shook me like this was from Vsauce about zipf's law.

## Hiphop101ize

May 9, 2018 at 6:58 pmHow do you watch videos at double speed o your phone?

## Thomas Bingel

August 16, 2018 at 5:42 amVery recommendable

## Kirito Kirigaya

September 23, 2018 at 2:07 pmoriginal video is here: https://www.youtube.com/watch?v=o-jdJxXL_W4

## Otie Brown

October 29, 2018 at 6:05 pmRemember Caude Shannon!

## The Reverend

November 16, 2018 at 1:11 pmI love your channel! Your videos always make these things easy!