Matpic
mathematics, in pictures
Series

Random walk — the series

7 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · probability
  2. 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.

    part 2 · probability
  3. 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.

    part 3 · probability
  4. 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.

    part 4 · probability
  5. 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.

    part 5 · probability
  6. The ground a 1,500-step walk covers. A random walk on a square grid drawn as a path, with every grid square it visited shaded and its start and end marked.

    The ground a walk covers

    A random walk of a thousand steps visits far fewer than a thousand places: in one dimension about fifty, in the plane about four hundred, in space about six hundred and sixty. The share of steps that land on new ground is exactly the chance of never coming home — so the number that decides whether a walker returns also decides how much of the world it sees.

    part 6 · probability
  7. Counting walks that never revisit a square. Dots for the ratio of successive counts of self-avoiding walks and for the n-th root of the count, against the number of steps, both approaching a dashed horizontal line at the connective constant.

    A walk that may not step where it has been

    Forbid a walk on the square grid from ever revisiting a site and the number of possible n-step walks grows like 2.638ⁿ instead of 4ⁿ — a number nobody can write down exactly. On the honeycomb it is exactly √(2 + √2), proved in 2010. And the walks spread out like n to the three-quarters, faster than any ordinary walk, which physicists have used since 1949 and mathematicians still cannot prove.

    part 7 · probability

All series