Matpic
mathematics, in pictures
Series

Markov chains — the series

8 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. A rule for moving between 3 states. 3 states drawn as circles with an arrow for every move the rule allows, labelled with its chance; a dashed loop is the chance of staying put.

    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.

    part 1 · probability
  2. A game that stops, over totals 0 to 5. States in a row with arrows up and down between them and the two ends absorbing, above a table of the expected number of steps and the chance of ending at the top from each start.

    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.

    part 2 · probability
  3. A walk on a weighted graph, and a cycle whose traffic goes one way. A weighted graph with the long-run share of each state read off its total weight, beside a three-state cycle whose shares are equal and whose traffic circulates.

    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.

    part 3 · probability
  4. The time a single walk spends in each state, against the share it should hold. Paired bars for each state, one the fraction of a long run's time spent there and one the computed stationary share, above a table of expected return times.

    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.

    part 4 · probability
  5. One walk on the whole numbers, three chances, three different fates. The relative weight of each state for three step-up chances, drawn as bars, with the running total of those weights and what each case means beneath.

    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.

    part 5 · probability
  6. How fast a chain forgets where it started. The total variation distance to the stationary distribution plotted logarithmically against the number of steps, for each of 3 starting states. The curves are straight lines of equal slope.

    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.

    part 6 · probability
  7. The narrowest door in two 6-cliques joined by one edge, and the gap it pins down. two 6-cliques joined by one edge, with the vertex set of smallest conductance coloured and the 1 edges leaving it thickened. Beside it a logarithmic ruler marks half the conductance squared, the spectral gap and twice the conductance, in that order from the bottom.

    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.

    part 7 · probability
  8. How far a deck of 52 is from random after each riffle shuffle. A bar chart over one to 12 riffle shuffles of the exact total variation distance from a uniformly random deck. The bars stay near one for the first few shuffles and drop sharply around 8.

    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.

    part 8 · probability

All series