Matpic
mathematics, in pictures
Concept

Reversibility

The property of a random process that as much probability flows from one state to another as flows back. It is a condition on each pair of states separately, and it is sufficient for a given distribution to be the one the process settles into.

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

Rotating by √2 − 1 of a turn, 40 times. Points on a circle produced by repeatedly turning through the same angle.

The orbit that must come back

A system with finitely many states has to repeat itself. Poincaré showed the same thing holds when the states are a continuum — almost every starting point returns arbitrarily close to where it began, however complicated the rule, and the argument is the pigeonhole principle with volume in place of counting.

dynamics · Pigeonhole A walk that visits each state as often as its weight says. The target distribution over 12 states with the share of a 40,000-step Metropolis run beside each bar, above the first 300 steps of the walk itself; the two distributions differ by 0.5 per cent in total.

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 · Monte Carlo Rule 30 made reversible: forward 60 steps, then back to the start. Second-order rule 30 on 101 cells: 60 steps forward, then the same rule from the swapped last two rows returns the starting row exactly.

A rule that remembers one row back

Only six of the 256 elementary cellular automata can be run backwards, and all six are trivial: shifts, copies and complements. Every interesting rule forgets. But make the new row depend on the row before the current one as well — combine the rule's output with it cell by cell — and every rule, rule 30 included, becomes exactly reversible: run forwards, swap the last two rows, run the same rule again, and the starting row comes back cell for cell. Nothing is lost, and yet the patterns still look as disordered as ever.

dynamics · Cellular automata Ten thousand steps of disorder, then a highway. Langton's ant from an empty grid: highway from step 9976, moving (-2, -2) every 104 steps; position after 12000 steps (-56, -32).

An ant that builds a highway

Two rules: on a white cell turn right, on a black cell turn left, and flip the colour as you leave. From an empty grid the ant wanders for 9,975 steps without visible order, then falls into a cycle of 104 steps that carries it diagonally for ever. That it always escapes to infinity is proved; that it always ends on a highway is not.

dynamics · Cellular automata

Named alongside it

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

Cellular automatonState spaceConjectureDetailed balanceDeterminismEigenvectorEmergenceEntropyInformationInvariantIrrational rotationIteration

All concepts