Generator

Nine walks, and the square root

A generator in the probability library, called 35 times across 12 essays. Below: what it draws at its defaults 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.

At its defaults

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.

`show: "spread"`

Where the walks ended. The endpoints of 4000 walks of 60 steps, against the exact binomial they are drawn from. The spread is 7.9, and √60 is 7.7.

`show: "lattice"`

The same walk, on a grid. 4000 steps on the square lattice, each one place along one axis. The walk returned to its starting square 9 times, and it will return again however long it goes on — but nothing in the picture shows why.

`show: "return"`

Coming home, in one, two and three dimensions. 4000 walks in each of one, two and three dimensions, each run for up to 3000 steps. On a line and in a plane a walk returns to its start with probability one; in space it returns with probability about 0.66, so roughly a third of walks never come back.

`show: "arcsine"`

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.

`show: "reflect"`

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.

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 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
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
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 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
ruin is certain with nothing left ×1
some walk goes outside the envelope, because √n is typical and not maximal ×1
the distribution sums to one ×1
the drawn path really does touch the level ×1
the drawn walk's mean square displacement per step is near one in every window ×1
the durations satisfy their own recurrence ×1
the enumerated check runs at an even length between 4 and 16 ×1
the extremes are more likely than the middle, which is the whole surprise ×1
the least likely outcome is an even split ×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 ruin probabilities satisfy their own recurrence ×1
the spread of the endpoints is of the order of the square root of the steps ×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

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

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 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 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

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

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