Matpic
mathematics, in pictures
Concept

Random walk

A path built by taking each step in a direction chosen at random, independently of the ones before. Its position after n steps has variance exactly n, which is why space scales as the square root of time in the limit.

Named by 13 essays across 3 fields — each of them below, with the objects they name alongside it.

Nine walks, and the square root. 9 independent walks of 400 steps, each step one place left or right. The dashed curves are ±√n: the walks stay near them, spill past them, and come back — which is what a typical distance means as opposed to a limit.

A walk that always comes home, until it does not

Step left or right at random, forever, and the walk returns to where it started with certainty. On a grid it also returns. In space it does not, and about a third of walks leave and never come back.

probability · Random walk 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.

probability · Markov chains five values, unevenly weighted, and the mass outside 3 standard deviations. A distribution drawn as bars, with the windows one and a half, two and three standard deviations wide marked. The probability outside each window is summed and compared with the bound that knows only the variance.

How far from the average a thing can be

Knowing only an average and a spread — nothing about the shape, nothing about the number of outcomes, nothing about symmetry — the chance of landing three standard deviations out is at most one in nine. And there is a distribution that lands there exactly that often, so the bound cannot be improved.

probability · Concentration A path folded about the first time it touches. A walk from 2 to 4 that touches the axis, with the part before its first touch reflected. The reflection is a path from the mirrored start to the same endpoint, and the correspondence is exact.

The path folded at its first touch

Counting the walks that touch a line looks like a question about a walk's whole history. Fold each one where it first touches, and it becomes a question about where walks end up — which is a binomial coefficient, and is already known.

probability · Random walk Time spent on one side of the axis. The exact distribution of the number of steps a 40-step fair walk spends above the axis. It is U-shaped: the extremes are the likeliest outcomes and an even split is the rarest.

Half the time is the rarest answer

In a fair game of many rounds, the fraction of the time one side is ahead is not usually near a half. It is usually near nought or one, and an even split is the single least likely outcome there is.

probability · Random walk A walk with a barrier at each end. Three games played to absorption on a table of 12, beside the chance of ruin from each starting stake — a straight line, because the walk is fair.

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 One walk at three magnifications, and the shape it is heading for. The same random walk over three windows, each ten times longer than the last and scaled vertically by the square root of ten, so all three look alike. Beside them, the exact distribution of the position after a few step counts, standardised, closing on the bell curve.

The walk that becomes a curve

Shrink the steps of a random walk and it disappears. Shrink them while stretching the time in the right proportion — space by the square root of whatever time is divided by — and something is left behind, which is a curve nobody could draw.

probability · Random walk 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.

probability · Markov chains 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.

probability · Markov chains 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

The first rung's shares were a limit of distributions — where the walk probably is after many steps. This one 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.

probability · Markov chains 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.

probability · Markov chains A bad path, and the path it reflects to. Two grids, 6 by 5. On the left a monotone path that dips below the diagonal, with its first offending step marked; on the right the same path with everything after that step reflected, which ends one square right and one square below the corner.

Counting the paths that go wrong

The number of good paths across a grid has no obvious formula. The number of bad ones does, because every bad path can be reflected into a path to a different corner, and that reflection is a perfect matching between two sets nobody chose to relate.

discrete · Catalan numbers Downhill on average, and never on purpose. The logarithms of 4 Collatz orbits plotted against step number, each wandering upward and downward and each ending at one. A separate sample of four thousand starts gives an average fall of -0.15 per step.

The heuristic that cannot be a proof

There is a two-line argument that the Collatz conjecture is true, it is convincing, and everybody who works on the problem believes it. It also cannot be turned into a proof, and understanding exactly where it fails is more instructive than the argument itself.

dynamics · Collatz

Named alongside it

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

ExpectationMarkov chainLimitInvariantProbabilityNormal distributionReflection principleStationary distributionAbsorbing stateBallot problemBijectionBinomial coefficient

All concepts