Matpic
mathematics, in pictures
Concept

Markov chain

A process moving between states with fixed probabilities that depend only on the state it is in, never on how it got there.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

.6.3.4.4.3.3.10.20.40ABCevery state can be reached from every other, and no length of walk is forcedevery arrow out of a state carries a chance, and the chances out of each state add to one

The rule that forgets where it came from

A walk between a few states, with the next step decided by the current one and nothing else. Run it long enough and the starting point stops mattering — but only when two conditions hold, and both of them have a picture in which they fail.

probability · markov chains 020406080024681012stepsstakethe table's limitruin00.2500.5000.750102.5057.5010starting stakechance of ruin0.58average length from 5: 35 stepsa fair game against a table of 12, started at 5: ruin comes with probability 0.583, which is 7 in 12and the game lasts 35 steps on average — the product of the two stakes, which is why a small player against a largeone is ruined quickly rather than slowly

Two barriers and a fair game

A fair walk between two absorbing barriers is ruined with a probability that is a straight line in the starting stake, and lasts for a number of steps that is the product of what each side can lose. Both facts come from the same two-line recurrence, and both are bad news for the smaller player.

probability · random walk

Named alongside it

The objects these essays reach for when they reach for this one.

Random walkAbsorbing stateConvergenceEigenvectorExpectationFixed pointGamblers ruinInvariantLimitMartingaleMatrixPeriodicity

All concepts