🎲 Markov Chains
3
Row i holds the chances of moving from state i. Change one cell and the rest of that row is rescaled so it still adds up to 1.
4.0

About Markov chains

A Markov chain describes something that moves at random between a handful of situations, where the chance of each next move depends only on where it is now and not on how it got there. Andrey Markov introduced the idea in 1906 partly to settle an argument: mathematicians of the time held that the law of large numbers required independent events, and he wanted to show that dependent ones could obey it too. To prove the point he counted the alternation of vowels and consonants through twenty thousand letters of Pushkin's Eugene Onegin, which is why the first application of the theory was to poetry rather than physics.

The forgetfulness of such a process is what makes it tractable, and it leads to a striking result. Run most chains long enough and the fraction of time spent in each situation settles down to fixed values that no longer depend on where the process started — the stationary distribution. How quickly that happens is a separate question with a practical answer, and chains that never forget their starting point at all, because they cycle rigidly or get trapped in a dead end, are exactly the interesting exceptions.

The idea turned out to fit an enormous range of subjects: queues at a counter, the weather, board games, credit ratings, the wear of machinery, gene sequences, and the behaviour of a gambler betting until either broke or satisfied. Google's original page ranking treated a web surfer clicking at random as a chain and used its stationary distribution as a measure of importance, while the sampling methods behind much of modern statistics and physics deliberately build a chain whose stationary distribution is the answer being sought, then let it run.