Markov Chains

From ForcaWiki, the simple encyclopedia

Meet a very forgetful frog. It sits on a lily pad in a pond, and every few seconds it hops to another pad. To decide where to jump next, the frog looks only at the pad it is sitting on right now. It has completely forgotten every pad it visited before. Where it goes next depends on where it is this very moment, and nothing else.

That forgetful hopping is the heart of a Markov chain. A Markov chain is a way to describe something that moves from one situation to another in steps, where the next step depends only on the situation it is in right now, not on the whole story of how it got there.

The pieces of a Markov chain

A Markov chain runs on chance, the thing mathematicians study under the name Probability, and it is built from two simple parts:

• "States," which are the situations the thing can be in. For the frog, each lily pad is a state.
• The chances of moving from one state to another. Maybe from the middle pad the frog jumps left half the time and right half the time.

Let us try a weather example, using pretend numbers. Suppose the weather can be in one of two states, Sunny or Rainy, and we notice a pattern:

• If it is sunny today, there is an 8 in 10 chance it will be sunny again tomorrow, and a 2 in 10 chance it will rain.
• If it is rainy today, there is a 6 in 10 chance it will rain again tomorrow, and a 4 in 10 chance the sun comes out.

With just those chances, you can make a good guess about tomorrow. And the only thing you need to know is what today is like.

The special rule: only "now" matters

The big idea of a Markov chain is that the past does not matter, only the present. To guess tomorrow's weather, you do not need to know that it was sunny all last week. You only need to know that it is sunny today. The chain has no memory, which is why people call it "memoryless."

A board game you may have played is secretly a Markov chain: Snakes and Ladders (also called Chutes and Ladders). Where your piece lands next depends only on the square you are on now and your dice roll. It makes no difference at all how you reached that square. The frog, the weather, and the game all follow the same memoryless rule. In fact, a frog hopping around at random like this is such a common example that it has its own name, a Random Walk.

Why is this useful?

Because a Markov chain only cares about the present, it is a simple but surprisingly powerful way to make predictions and to model the world. If you let the chain run for a long time, you can even work out patterns like "how often is it sunny in the long run?" People use Markov chains to study the weather, board games, how a shuffled deck of cards behaves, how diseases spread, and much more.

Fun facts

• Markov chains are named after Andrey Markov, a Russian mathematician who came up with them in the early 1900s. To show them off, he once used one to study the pattern of vowels and consonants in a famous long poem.
• The very first version of Google's search used a giant Markov chain to decide which web pages mattered most, by imagining a person clicking link after link at random, on and on forever.
• The simple kind of next word guessing, like the word suggestions on an older phone keyboard, works like a Markov chain: it looks at the word you just typed and picks a likely word to come next.