Generator

A rule for moving between 3 states

A generator in the probability library, called 42 times across 11 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.

chain 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

`show: "stationary"`

`show: "collect"`

Waiting for all 6 kinds. One bar per new kind: the expected number of draws needed to see a kind not yet seen, rising as fewer of them are left, and adding to 14.70 draws in total.

`show: "graph"`

`show: "absorb"`

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.

`show: "mixing"`

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.

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 wait for a new one at 0 seen is 6/6 ×21
the 6 waits add to 6 times the harmonic sum ×3
a run of the game reproduces the expected length ×1
a walk of 40000 steps spends about the solved share of its time at A ×1
a walk of 40000 steps spends about the solved share of its time at B ×1
a walk of 40000 steps spends about the solved share of its time at C ×1
and comes back to A about as often as the solve says ×1
and comes back to B about as often as the solve says ×1
and comes back to C about as often as the solve says ×1
and it is still climbing at the same rate ×1
and it really is stationary ×1
and that sum is bounded, so the shares can be normalised ×1
and the chance of ending at the top satisfies B = R + Q B ×1
and the chance of ever coming back is less than one ×1
and the chance of winning is the share of the stake held ×1
and the share of wins reproduces the computed chance ×1
and the traffic round the cycle is not equal in the two directions ×1
and they are the shares the rule leaves alone ×1
as much traffic goes from A to B as comes back ×1
as much traffic goes from A to C as comes back ×1
as much traffic goes from A to D as comes back ×1
as much traffic goes from A to E as comes back ×1
as much traffic goes from B to C as comes back ×1
as much traffic goes from B to D as comes back ×1
as much traffic goes from B to E as comes back ×1
as much traffic goes from C to D as comes back ×1
as much traffic goes from C to E as comes back ×1
as much traffic goes from D to E as comes back ×1
at even odds the expected length is k times N minus k ×1
at least two chains, so the comparison says something ×1
away from even odds the chance of winning is the ratio the odds give ×1
between six and sixty steps are drawn ×1
between two and four step-up chances are drawn ×1
every chain named is one the family carries ×1
every start can go either way ×1
every state has somewhere to go ×1
every state holds a share ×1
iterating from A reaches the same share for A ×1
iterating from A reaches the same share for B ×1
iterating from A reaches the same share for C ×1
no two edge weights are drawn on top of one another ×1
row A holds probabilities ×1
row B holds probabilities ×1
row C holds probabilities ×1
row D holds probabilities ×1
row E holds probabilities ×1
row F holds probabilities ×1
row G holds probabilities ×1
row H holds probabilities ×1
the chain is one of mixing, cycle, reducible, lazy ×1
the chain is one the family carries ×1
the chain with the smaller gap really does take longer ×1
the chance of a win is strictly between nothing and everything ×1
the chances of leaving A add to one ×1
the chances of leaving B add to one ×1
the chances of leaving C add to one ×1
the chances of leaving D add to one ×1
the chances of leaving E add to one ×1
the chances of leaving F add to one ×1
the chances of leaving G add to one ×1
the chances of leaving H add to one ×1
the corroborating run is between 500 and 40,000 games ×1
the cycle's forward chance is between a half and one ×1
the cycle's shares are stationary even so ×1
the cycle's stationary shares are equal ×1
the distance to stationarity never rises ×1
the drawing runs out to between 10 and 60 states ×1
the expected number of steps satisfies t = 1 + Q t ×1
the expected return to A is one over its share ×1
the expected return to B is one over its share ×1
the expected return to C is one over its share ×1
the game is played over between four and nine totals ×1
the long-run shares are drawn only for a chain that has them ×1
the measured decay rate is the second eigenvalue ×1
the measured mixing time follows the eigenvalue's prediction ×1
the number of kinds to collect is between 2 and 16 ×1
the panels drawn are genuinely different cases ×1
the return chances satisfy the rule that defines them ×1
the rows never move further apart as the power rises ×1
the run is between 2,000 and 400,000 steps ×1
the run spends its time in A in the computed share ×1
the run spends its time in B in the computed share ×1
the run spends its time in C in the computed share ×1
the same current flows across every edge of the cycle ×1
the series is added over between 60 and 4,000 terms ×1
the share read off the weights is the share the equations give ×1
the shares add to one ×1
the solved share for A survives a step ×1
the solved share for B survives a step ×1
the solved share for C survives a step ×1
the stationary distribution adds to one ×1
the system is not singular ×1
the traffic between neighbours balances ×1
the view is one the family draws ×1
the walk is between a thousand and four hundred thousand steps ×1
the weights add to the geometric sum they are ×1
the weights are a square table of between three and six states ×1
the weights are all one, so the sum grows without bound ×1
the weights are symmetric and never negative ×1
the weights grow, so there is nothing to normalise ×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 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.

Computation

Every word once, around a cycle

A cyclic string of eight bits holds all eight three-bit words, each exactly once — and the reason such a thing exists is that the constraint linking overlapping windows is itself the construction.

Probability

How long until every one turns up

Draw at random from six equally likely kinds until all six have appeared. The wait is not six draws, and it is not sixty; it is fourteen point seven, and the number is a harmonic sum wearing a hat.

Probability

How long until it forgets

The ladder's four rungs 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.

Probability

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

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

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

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