Generator

Nine walks, and the square root

A generator in the probability library, called 45 times across 14 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

walk is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

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.

Where the walks ended

The same walk, on a grid

Coming home, in one, two and three dimensions

Counting walks that never revisit a square

Every 4-step self-avoiding walk

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

the enumeration finds the known number of 0-step walks ×20
the formula agrees with the enumeration at 0 steps above ×7
the sum of 4 steps has probabilities adding to one ×4
the sum of 4 steps has some spread to speak of ×4
between 2 and 5 steps ×2
in 2 dimensions the measured range is within 25% of the classical law at 10,000 steps ×2
a walk in space escapes, and the simulation sees it ×1
a walk on a line comes back, and the horizon barely hides it ×1
a walk on a plane comes back too, but more slowly ×1
a walk takes a whole positive number of steps ×1
an endpoint has the parity of the step count ×1
an even number of steps between 8 and 200 ×1
and impossible with everything ×1
and moves the start to its mirror image ×1
and so are the reflected ones ×1
and the distribution is symmetric ×1
and the gap to the bell curve closes at every step ×1
and the variance of its position is exactly the number of steps ×1
and their spread is the square root of the number of steps ×1
between 4 and 16 steps are drawn, since every path of them is enumerated ×1
dim is read only by the range view ×1
each exact distribution is of between 2 and 400 steps ×1
each step moves one place along one axis ×1
every game drawn ends at a barrier ×1
every path from below the level has to cross it ×1
every path is counted once ×1
every step is drawn ×1
every step is one place, either way ×1
every step is to a neighbour ×1
every walk is counted once ×1
folding leaves the endpoint alone ×1
folding matches the touching paths with the paths from the mirrored start one for one ×1
in 1 dimension the measured range is within 6% of the classical law at 10,000 steps ×1
in one dimension the range is the width of the explored interval ×1
lattice is read only by the sawcount view ×1
ruin is certain with nothing left ×1
some walk goes outside the envelope, because √n is typical and not maximal ×1
steps is not read by the views that fix their own lengths ×1
the distribution sums to one ×1
the drawn path really does touch the level ×1
the drawn walk is in one or two dimensions ×1
the drawn walk's mean square displacement per step is near one in every window ×1
the drawn walks are exactly the known number ×1
the durations satisfy their own recurrence ×1
the enumerated check runs at an even length between 4 and 16 ×1
the enumeration finds the known counts ×1
the extremes are more likely than the middle, which is the whole surprise ×1
the lattice is the square grid or the honeycomb ×1
the least likely outcome is an even split ×1
the one-dimensional survival matches C(2m, m)/4^m ×1
the paths ending where they end are counted by a binomial coefficient ×1
the player starts with something and not everything ×1
the position has the parity of the step count ×1
the quoted constant is Pólya's ×1
the range is the number of distinct sites on the path ×1
the ruin probabilities satisfy their own recurrence ×1
the sampled walk never revisits a site ×1
the spread of the endpoints is of the order of the square root of the steps ×1
the squared distance grows faster than the simple walk's n, with exponent near 3/2 ×1
the table holds between 4 and 40 units ×1
the three windows are whole numbers of steps ×1
the three windows are whole numbers of steps inside the walk ×1
the time spent above is always even ×1
the view is one the family draws ×1
the walk can reach its endpoint in the steps allowed ×1
the walk comes back to where it started at least once ×1
the walk has no drift ×1
the walk is between 400 and 60,000 steps long ×1
the walk starts above the level it may touch ×1
the walks are centred on where they started ×1
the win probability is a probability ×1
three-dimensional walks that have not returned by step 2,000 are about 1 − 0.3405 of them ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Probability

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

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.

Probability

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.

Probability

An average that never settles

The average of many independent quantities is supposed to steady as their number grows. For one famous distribution it does not steady at all — the average of a thousand draws has exactly the same distribution as a single draw, and no amount of further averaging changes it.

Probability

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

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

How fast the bell arrives

The limit theorem says a standardised sum approaches the bell curve and says nothing about when. The rate is one over the square root of the number of terms, the constant in front is made of the third moment, and both are visible.

Probability

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

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.

Probability

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

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.

Probability

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

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

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.

The whole library · What the figures prove