Markov chain
Named by 21 essays across 4 fields — each of them below, with the objects they name alongside it.
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.
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.
A walk that samples a distribution
When a distribution can be evaluated but not drawn from, a wandering point can be arranged to visit each state as often as its weight says. The rule needs no normalising constant, compares two weights and steps or stays.
The chain that stops
Give a chain a state it cannot leave and there is no long run to find — every walk ends. What is worth computing instead is how long it lasts and where it finishes, and both are exact answers to a linear system rather than limits of anything.
The chain that runs the same backwards
Put weights on the edges of a graph, step to a neighbour in proportion to them, and the long-run share of a state is its own weight over the total — read straight off the picture, with nothing to solve. The condition that makes that work is strictly stronger than being stationary.
The time spent and the share held
Stationary shares are a limit of distributions — where the walk probably is after many steps. Here the question is about a single walk: the fraction of its time spent in each state is that state's share, and the expected wait between visits is exactly the reciprocal.
Where the shares have nowhere to go
On finitely many states, a chain that can reach everywhere and is not forced into a rhythm settles down. Give it infinitely many and both conditions can hold while the walk leaves and never returns — or returns with certainty and takes an unbounded average time about it.
How long until it forgets
The essays before this one settle where a chain ends up and how much time it spends there, and none of them asks how long the settling takes. That question has an exact answer, it is a single number, and it is the only thing any practical use of a chain depends on.
Moving a map across a product
The transpose looks like a fact about a matrix: reflect its entries in the diagonal. It is a fact about the inner product. Measure lengths and angles differently and the map that slides to the other side of the product is a different matrix, and a matrix that was symmetric stops being so.
Fair bits from an unfair coin
Read a biased coin's flips in pairs, keep 01 as 0 and 10 as 1, and throw away the rest: the output is exactly fair, whatever the bias, and nobody needs to know the bias. The trick wastes most of the coin, the waste can be recycled almost up to the ceiling Shannon's entropy sets — and it fails quietly the moment the flips remember each other.
A room where nobody is alone
Twenty-three people probably include two who share a birthday. How many are needed before every single person shares a birthday with somebody else in the room? The answer is 3,064 — more than it takes for every day of the year to be somebody's birthday — and the reason is a count of loners, which rises as the room fills, peaks at 134 when the room is the size of the year, and then falls so slowly that the last loner lingers for thousands of arrivals.
A coin that lets the first player win
On a fair coin the second player in Penney's game always has a better pattern than the first, and the first can hold them to no worse than two to one. Bend the coin and every overlap is paid for in the letters it uses: the replies change, the first player's share swings between a third and a half, and past a heads chance of 1/∛2 the first player simply names HHH and wins.
Three patterns in a circle
Race three coin patterns at once and the gamblers' accounting still gives each one's chance of arriving first — one fairness equation per pattern. What it does not give is any way to read the three-way result off the two-way ones. HHHT, TTHH and HTTH beat one another in a circle, and HHH loses both its head-to-head races and still finishes ahead of one of the patterns that beat it.
The narrowest door sets the pace
How fast a chain forgets is an eigenvalue, and nobody can compute the eigenvalues of a chain worth studying. Cheeger's inequality trades the eigenvalue for a picture — the narrowest door in the state space — and pins the one between the square of the other and twice it. Both ends of that range are reached, on graphs small enough to search completely.
The forgetting that happens all at once
A single small chain forgets its start gradually, a little more with every step. A family of large ones can do something different — stay almost perfectly informed about where it began, and then lose all of it inside a window far shorter than the wait. That cliff is the cutoff phenomenon, and it is why "seven shuffles" is an answer rather than a convention.
When a table of moves came from steady rates
A process that jumps between states at constant rates, watched once a year, produces a table of yearly moves that is the exponential of its rates. Most tables that anyone could write down are not — a random three-state table is only about one time in twenty-three — and the few that are can have two different sets of rates behind them, but only once the process has forgotten where it started.
The longest run has no limit
Toss a fair coin n times and the longest run of heads is about log₂ n. The average settles: it is log₂ n − 0.667 to within a few millionths by a million tosses. The distribution does not. Because the run is a whole number and log₂ n is not, the chance of each value swings round the same cycle once every doubling of n, for ever, and computing it exactly to a million tosses shows the swing as large at the end as at the start.
Half the chance for every silent set
In the lights game where a press toggles only the neighbours, a random network can be lit about 56 times in a hundred when it has an even number of vertices and 44 when odd. The numbers are 0.560562 and 0.439438, they add to one, and they come from a chain: each new vertex raises or lowers the dimension of the silent sets by one, and each dimension halves the chance.
Two losing games that win together
Game A is a coin that wins 49.5% of the time. Game B tosses a bad coin when the capital is a multiple of three and a good one otherwise, and it loses too, because the capital spends more than a third of its time on multiples of three. Choose between the two games at random and the walk drifts upwards by 0.0157 a round; play A, B, B over and over and it gains 0.0574. Nothing is wrong with the arithmetic. The losing coin A wins by knocking the capital off the bad remainder.
The route round that rates cannot avoid
A table of yearly moves between states came from steady rates only if it is the exponential of a rate matrix. With two states that is true of half of all tables, with three of one in twenty-four, with four of about one in two thousand, and of none of 400,000 tables drawn at random with five. Even a table that is nine parts staying put fails more and more often as states are added, and always for one reason: rates that carry 1 to 2 and 2 to 3 also carry 1 to 3, and a table whose direct move is rarer than that route round cannot have come from them.
Two losing games with a memory
Parrondo's first paradox needed a game that watched the player's capital. This one watches nothing but the last two results: a coin that wins nine times in ten after two losses, one time in four after a loss and a win, seven times in ten after two wins. Alone it loses, and so does a slightly unfair coin; played at random together they win. The walk treats every position alike, and the paradox survives — because it was never about position.
Named alongside it
The objects these essays reach for when they reach for this one.
Random walkExpectationStationary distributionEigenvalueEigenvectorInvariantLimitProbabilityLinear systemMartingaleMixing timeSpectral gap