Concept

Random walk

A path built by taking each step in a direction chosen at random, independently of the ones before. Its position after n steps has variance exactly n, which is why space scales as the square root of time in the limit.

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

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.

probability · Random walk
A rule for moving between 3 states. 3 states drawn as circles with an arrow for every move the rule allows, labelled with its chance; a dashed loop is the chance of staying put.

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 · Markov chains
five values, unevenly weighted, and the mass outside 3 standard deviations. A distribution drawn as bars, with the windows one and a half, two and three standard deviations wide marked. The probability outside each window is summed and compared with the bound that knows only the variance.

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 · Concentration
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.

probability · Random walk
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.

probability · Random walk
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.

probability · Random walk
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.

probability · Random walk
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.

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 · Markov chains
A walk on a weighted graph, and a cycle whose traffic goes one way. A weighted graph with the long-run share of each state read off its total weight, beside a three-state cycle whose shares are equal and whose traffic circulates.

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 · Markov chains
The time a single walk spends in each state, against the share it should hold. Paired bars for each state, one the fraction of a long run's time spent there and one the computed stationary share, above a table of expected return times.

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 · Markov chains
One walk on the whole numbers, three chances, three different fates. The relative weight of each state for three step-up chances, drawn as bars, with the running total of those weights and what each case means beneath.

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.

probability · Markov chains
A bad path, and the path it reflects to. Two grids, 6 by 5. On the left a monotone path that dips below the diagonal, with its first offending step marked; on the right the same path with everything after that step reflected, which ends one square right and one square below the corner.

Counting the paths that go wrong

The number of good paths across a grid has no obvious formula. The number of bad ones does, because every bad path can be reflected into a path to a different corner, and that reflection is a perfect matching between two sets nobody chose to relate.

discrete · Catalan numbers
Downhill on average, and never on purpose. The logarithms of 4 Collatz orbits plotted against step number, each wandering upward and downward and each ending at one. A separate sample of four thousand starts gives an average fall of -0.15 per step.

The heuristic that cannot be a proof

There is a two-line argument that the Collatz conjecture is true, it is convincing, and everybody who works on the problem believes it. It also cannot be turned into a proof, and understanding exactly where it fails is more instructive than the argument itself.

dynamics · Collatz
The coefficients of (1 + x)¹² sorted by remainder mod 3. The binomial coefficients of the 12th power coloured by the remainder of their index on division by 3, beside the 3 points one plus a root of unity, whose powers averaged pick out each colour's total.

Every third coefficient

Add every third number in the twelfth row of Pascal's triangle and the answer is 1366 — a third of 4096, rounded up. Which way the rounding goes is decided by two arrows of length one in the complex plane, and the same average over the roots of unity counts dice totals, subsets and necklaces.

algebra · Roots of unity
The cubic curves over GF(43) with the most and the fewest points. The solutions of two equations y squared equals x cubed plus ax plus b over the field with 43 elements, drawn as dots on a square grid: the curve with the most points and the curve with the fewest.

Give or take twice the square root

A cubic curve over the integers mod 43 should have about 44 points — one for each value of x, on average, and one at infinity. No curve misses by more than 13, the largest whole number below 2√43, and every count from 31 to 57 belongs to some curve. The first fact is Hasse's theorem, the second Deuring's, and the way the counts spread between the limits is a semicircle.

computation · Finite fields
What one input can do, over 1024 cases. A table of functions of several inputs with the largest effect any single input has on each, the bound that effect implies, and the true tail probability — computed by enumerating every input.

No single input can move it far

Independence was never the hypothesis doing the work. A quantity built from many separately drawn inputs concentrates whenever changing one of them moves it only a little — and that covers quantities which are not sums of anything and have no formula at all.

probability · Concentration
Rule 184 at density 0.30. A space-time diagram of rule 184 on a ring of 120 cells, 80 steps down the page, starting from a random row with 36 cars. The diagonal stripes are free-moving cars; the jams dissolve.

A road where nobody overtakes

Rule 184 moves every 1 one cell to the right whenever the cell ahead is empty. It is one of only five elementary rules that never change the number of 1s, and that single property turns it into a model of traffic with an exact transition: below half density every jam dissolves, above it jams can never all clear and drift backwards against the flow.

dynamics · Cellular automata
12 harmonic series with random signs, each settling on its own sum. Partial sums of the harmonic series with each sign chosen by a fair coin, for several independent runs, plotted against the number of terms on a logarithmic scale, beside the all-plus and alternating sign patterns.

A coin in front of every term

Put all plus signs in front of 1, 1/2, 1/3, … and the sum runs off to infinity; alternate them and it settles on log 2. Toss a fair coin for each sign instead, and the sum settles — every time, on a different number. Where it tends to settle has a smooth, flat-topped shape, and at the value 2 that shape takes a height that agrees with one eighth to forty-two decimal places and is not one eighth.

analysis · Harmonic series
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.

probability · Random walk
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.

probability · Random walk
Evidence as steps on a scale of decibans. A horizontal decibel scale of odds with a starting dot at the prior and one arrow per piece of evidence, ending at a posterior probability of 44.2%.

Evidence measured in decibans

Write a probability as odds and take the logarithm, and every piece of evidence becomes a length. A positive result on a good test is thirteen decibans; a negative one is minus twenty. Lay the lengths end to end from the prior and the posterior is where they stop, in any order. The rule fails in exactly one way — when two pieces of evidence share a cause — and Turing built a code-breaking method on the arithmetic.

probability · Bayes
Switching envelopes when the largest amount is 64. A bar chart of the probability-weighted gain from switching at each amount that might be seen, 1 to 64: small positive bars and one large negative bar, adding to zero.

The envelope that always looks better

Two envelopes, one holding twice as much as the other. Open one, see an amount, and reason that the other holds double or half with equal chance — so switching gains a quarter on average. By symmetry the same argument says switch back. The step that fails is not the arithmetic; it is the claim that double and half are equally likely whatever amount is seen, which no honest prior allows — and there is one prior under which the other envelope really does look better at every amount.

probability · Bayes
The narrowest door in two 6-cliques joined by one edge, and the gap it pins down. two 6-cliques joined by one edge, with the vertex set of smallest conductance coloured and the 1 edges leaving it thickened. Beside it a logarithmic ruler marks half the conductance squared, the spectral gap and twice the conductance, in that order from the bottom.

The narrowest door sets the pace

How fast a chain forgets is an eigenvalue, and nobody can compute the eigenvalues of a chain worth studying. Cheeger's inequality trades the eigenvalue for a picture — the narrowest door in the state space — and pins the one between the square of the other and twice it. Both ends of that range are reached, on graphs small enough to search completely.

probability · Markov chains
How far a deck of 52 is from random after each riffle shuffle. A bar chart over one to 12 riffle shuffles of the exact total variation distance from a uniformly random deck. The bars stay near one for the first few shuffles and drop sharply around 8.

The forgetting that happens all at once

A single small chain forgets its start gradually, a little more with every step. A family of large ones can do something different — stay almost perfectly informed about where it began, and then lose all of it inside a window far shorter than the wait. That cliff is the cutoff phenomenon, and it is why "seven shuffles" is an answer rather than a convention.

probability · Markov chains
The cube drawn by putting every point at the average of its neighbours. Tutte's barycentric drawing of the cube: outer face of 4 sides, 0 crossings.

Every point at the average of its neighbours

A planar graph can be drawn without crossings, but finding such a drawing looks like a search. Tutte found in 1963 that it is not: pin one face to a convex polygon, put every other point at the average of its neighbours, and the drawing that results has straight edges, convex faces and no crossings at all — provided no two points can cut the graph apart. It is the position a network of equal springs settles into, and it is also where a random walk expects to leave.

discrete · Planarity
Traffic with random dawdling: jams from nowhere at density 0.18. Nagel–Schreckenberg traffic, 29 cars on 160 cells, top speed 5, dawdling probability 0.25; up to 11 cars stopped at once.

A jam that comes from nowhere

Give cars on a ring road a top speed of five cells a step, let each slow to the gap ahead, and add one more rule: now and then, at random, a driver eases off by one. That is the whole of the Nagel–Schreckenberg model, and it produces what the exactly solvable rule 184 could not — jams that form in free traffic with no obstacle, drift backwards against the flow, and cost the road more than a third of its capacity. Set the top speed to one and remove the chance, and it is rule 184 again, cell for cell.

dynamics · Cellular automata
How often a closed random polygon is certainly knotted, by length. 10: 0.8% (mean crossings 2.8); 20: 1.5% (mean crossings 7.9); 40: 6.3% (mean crossings 21.2); 60: 10.5% (mean crossings 35.1); 80: 20.8% (mean crossings 51.3); 100: 22.0% (mean crossings 66.9); 130: 32.3% (mean crossings 94.9); 160: 45.7% (mean crossings 122.6); 200: 47.0% (mean crossings 154.5); 250: 51.7% (mean crossings 205.5).

Almost every long loop is knotted

Close a random walk into a loop and ask whether it is knotted. With ten steps almost never; with a hundred, more than one time in five it can be proved knotted by a single number; with two hundred and fifty, more than half. The chance of staying unknotted falls exponentially with length — Frisch, Wasserman and Delbrück guessed it for polymer rings around 1961, and it was proved in 1988 — because a knot needs only one small tangle somewhere, and a long loop has room for many.

topology · Knots
A random walk across the regions to the one that satisfies every clause. Four overlapping ellipses with a dot in each of their sixteen regions, one marked as the only assignment satisfying the clauses, and a path of arrows from a random starting region to it, each arrow crossing one ellipse.

A walk that beats trying everything

To decide whether clauses of three letters can all be satisfied, the obvious method tries all 2ⁿ assignments. Uwe Schöning's method, from 1999, starts at a random assignment and wanders: pick a clause that is false, flip one of its letters at random, and repeat three times as many times as there are letters. A single try usually fails, but it succeeds with chance at least about (3/4)ⁿ, so about (4/3)ⁿ tries are enough — and the reason is a walk on a line that goes the wrong way two times in three.

logic · Class diagrams
A fair coin judged by someone who thinks it is biased. Posterior probabilities of three wrong coin biases over two thousand tosses of a fair coin, for five runs; the bias 0.6 wins every run.

Certain of a coin that is not there

Bayes' theorem is exact, and it is only as good as the list of hypotheses it is given. Hand it a list that leaves out the truth and it does not hesitate: it becomes certain of the entry that is least wrong, in a precise sense — the one closest in Kullback–Leibler divergence — and if two entries are equally wrong it never settles at all. Hand it a model that assumes independence where there is none, and its intervals shrink as fast as they would for honest data while covering the truth less and less often.

probability · Bayes
How often a walk comes home, on three lattices and a tree. Four curves of the logarithm of the return probability after 2n steps, for n up to 60: three lattices flattening, and the free group falling along a straight line.

How rarely a walk on a group comes home

Walk at random on the picture of a group, one generator at a time, and ask for the chance of standing at the start after 2n steps. On the line, the plane and three-dimensional space it falls like a power of n. On the tree that pictures the free group it falls by the factor √3/2 every step, exponentially. Kesten proved in 1959 that this is no accident of two examples: the chance falls exponentially exactly when the group's balls are mostly boundary, so a probabilistic rate and a geometric ratio are the same measurement.

algebra · Cayley graph
Walks that prefer the steps they have taken. 12 Pólya-urn walks of 2000 steps, each heading off along its own straight line, with final speeds 0.99, −0.87, −0.02, −0.66, 0.01, 0.78, 0.47, 0.44, −0.04, 0.38, 0.83, 0.55, against the ±2√n band of an ordinary walk.

A walk that follows its own footsteps

Let a walk step up with probability equal to the share of up-steps it has taken so far, and every count of up-steps after twenty steps is exactly equally likely. The walk leaves along a straight line at a speed chosen by its first few steps, and although it is expected to come back to its start infinitely often, almost every run comes back only a few times.

probability · Random walk
Five urns, each drawn as walks. Simulated walks of 2000 draws for urns with replacement matrices (0,1,1,0), (2,1,1,2), (3,1,1,3), (7,1,1,7), (1,0,0,1).

An urn forgets its start only below one half

Let each draw from an urn add balls of both colours in fixed amounts, and the long run depends on a single ratio of two eigenvalues. Below one half the urn behaves like a coin, its fluctuations spread like the square root of the draws and settle into a bell. Above one half the first few draws decide most of the outcome, the spread grows faster, and the shape that results is not a bell and depends on how the urn began.

probability · Random walk
A random sequence that shrinks, grows or wanders, by one parameter. Runs of tₖ₊₁ = tₖ ± β·tₖ₋₁ at β = 0.6, 0.70258, 0.8 on a logarithmic scale: shrinking, wandering and growing.

A threshold no average can see

Damp the random Fibonacci sequence — add or subtract β times the term before last, by a coin — and somewhere between β = 0.6 and β = 0.8 almost every run stops shrinking and starts growing. The switch is at β ≈ 0.70258. The average of the squares, which can be computed exactly, grows for every β there is, so the one number that decides the sequence's fate is invisible to the one number anybody can compute.

dynamics · Sensitive dependence
A loop that cannot be undone, and the surface it bounds. The loop aba⁻¹b⁻¹ on the figure eight, which cannot be pulled tight, beside a square whose boundary reads the same word, showing that the loop bounds a surface.

What homology forgets about a loop

Let the letters of a loop commute and the loop group of a space becomes its first homology group: a loop now records only how often it went round each hole. What is thrown away is exactly the loops that bound a surface. On the figure eight that is nearly everything — of the loops of sixty letters that homology calls nought, about one in 6,700 is a loop that actually shrinks.

topology · Homotopy
Where a random walk from the centre leaves the snowflake. 60,000 walks on spheres from the centre of the level-6 snowflake; the most-visited 10% of 768 boundary pieces receive 62.7% of the walks; one walk of 9 jumps drawn.

Where a random walk leaves the snowflake

Start a random walk at the centre of the Koch snowflake and record where it first touches the edge. The edge has dimension 1.26, but the places the walks arrive form a set of dimension one: 60,000 walks spread their entropy by ln 3 a level, not ln 4, and the busiest fifth of the edge takes nine tenths of them. Makarov proved in 1985 that it must be so for every simply connected region in the plane.

analysis · Measure
A chain locks whole or breaks at its weakest link. Chain of 40, Kₗ = 4.4817 at link 27; frequency spread 1.86e-5 at 1.04 Kₗ, 0.0645 at 0.96 Kₗ.

A long enough chain never locks

Line oscillators with different natural rhythms up in a row and let each feel only its two neighbours. The chain locks into one frequency exactly when the coupling exceeds the largest running total of their frequency differences — a random walk tied down at both ends — so the coupling needed grows like √N, and its law is Kolmogorov's, the same distribution that tests whether a sample fits a curve.

dynamics · Sensitive dependence
Watching a fair coin until it looks unfair. Fair coins, 2000 runs to 100000: share reaching p<0.05 by 10³ 0.468, by 10⁵ 0.697; share reaching BF₁₀≥20 by 10³ 0.0280, by 10⁵ 0.0340.

Peeking until the answer is yes

Toss a fair coin, test for bias after every toss, and stop the moment the result is significant at 5%. Within a thousand tosses nearly half of fair coins have been declared biased, and with no limit on the tosses every one of them is. Watch a Bayes factor the same way, stopping at twenty to one, and no amount of watching gets more than one fair coin in twenty past the line.

probability · Bayes
Two losing games that win together. A alone: -3.000 after 300; B alone: -3.131 after 300; A or B at random: 4.428 after 300; A A B B repeated: 4.322 after 300.

Two losing games that win together

Game A is a coin that wins 49.5% of the time. Game B tosses a bad coin when the capital is a multiple of three and a good one otherwise, and it loses too, because the capital spends more than a third of its time on multiples of three. Choose between the two games at random and the walk drifts upwards by 0.0157 a round; play A, B, B over and over and it gains 0.0574. Nothing is wrong with the arithmetic. The losing coin A wins by knocking the capital off the bad remainder.

probability · Random walk
A random walk winding round a puncture. Lattice walk of 4000 steps around (½, ½); final winding -4.861 turns; box -12..26 × -29..22.

How a random path winds round a point

A path in the plane with one point removed has a class in the punctured plane's fundamental group: how many times it has wound round the point. For a random path the class grows like the logarithm of time, and its spread has a law. Brownian motion follows Spitzer's Cauchy law, so heavy-tailed that the mean winding does not exist; a walk on a grid follows the hyperbolic secant law instead, with tails that fall exponentially. The difference is made entirely by close passes, which a grid forbids. With two points removed the class becomes a word, and some loops wind round neither point and still cannot be shrunk.

topology · Homotopy
Three random loops and the knots they tie. 0₁: 12 crossings; 3₁: 18 crossings; 4₁: 16 crossings.

Which knots a random loop ties

Long random loops are almost always knotted, but knotted as what? Sorting 14,000 closed random polygons by two values of the Alexander polynomial answers it. The trefoil leads at every length, five times as common as the figure-eight at 400 sticks. Each knot's share, divided by the unknotted share, grows like a power of the length, and the trefoil tied twice grows about twice as fast as the trefoil — what a loop carrying independent small tangles would do. Up to 300 sticks the double trefoil turns up exactly as often as two independent trefoils should.

topology · Knots
Three ways to pick a rotation at random. Mean rotation angle: uniform 126.70° (exact 126.48°), uniform Euler angles 127.91°, uniform axis and angle 90.18°. Densities by 5° bin, uniform: 0.00, 0.00, 0.01, 0.01, 0.03, 0.04, 0.04, 0.06, 0.09, 0.09, 0.13, 0.15, 0.16, 0.20, 0.23, 0.25, 0.28, 0.29, 0.34, 0.36, 0.38, 0.41, 0.44, 0.46, 0.47, 0.52, 0.54, 0.55, 0.57, 0.61, 0.60, 0.64, 0.62, 0.61, 0.64, 0.64.

A rotation chosen at random

Turn a solid body to an orientation chosen at random and it has usually been turned a long way: on average 126.5 degrees, and by less than ten degrees only three times in ten thousand. Unit quaternions make the right meaning of 'at random' a picture, and two recipes that look fair fail it in opposite directions.

algebra · Quaternions
A cluster grown by random walkers. Diffusion-limited aggregation, 20000 particles, radius 303.0; particles coloured by arrival in fifths.

A cluster grown by random walkers

Release a particle far away, let it wander until it touches a growing cluster, and freeze it there. Twenty thousand particles later the cluster is a branching tree whose mass grows like the radius to the power 1.7. Every simulation agrees on the number; the only theorem says it is at least 1.5.

dynamics · Fractal dimension
Forty-two squares in a row. p = 366791: partial sums of (n/p) for n ≤ 200: 0, 10, 20, 30, 40, 46, 54, 60, 64, 72, 78, 78, 88, 92, 98, 102, 108, 116, 122, 126, 132; least non-residue 43.

The first number that is not a square

Modulo a prime, half the numbers are perfect squares. Count up from 1 and the first non-square is usually 2 or 3 — but modulo 366,791 the numbers 1 to 42 are all squares. How far the run of squares can last is one of the oldest open questions about primes: the truth is tiny, the proofs are huge, and the Riemann hypothesis would close most of the gap.

number · Quadratic reciprocity
Four fractions staked on one run of tosses. p=0.6, 1000 tosses, 604 heads; final log10 wealth: Kelly 9.449, half Kelly 6.881, twice Kelly 0.409, everything ruined at toss 10.

The best average is the worst bet

A coin lands heads six times in ten and pays even money. Stake everything on every toss and the expected wealth grows by a fifth a toss — and the bettor is ruined at the first tail, which is certain to come. Stake a fifth of wealth each time instead and the average grows far more slowly, while the typical bettor grows faster than with any other fraction. The expectation is maximised by the strategy almost nobody should use.

probability · Expectation
How high an orbit climbs. 1:1 2:2 3:16 7:52 15:160 27:9232 255:13120 447:39364 639:41524 703:250504 1819:1276936 4255:6810136 4591:8153620 9663:27114424 20895:50143264 26623:106358020 31911:121012864 60975:593279152 77671:1570824736 113383:2482111348 138367:2798323360 159487:17202377752 270271:24648077896 665215:52483285312 704511:56991483520 1042431:90239155648 1212415:139646736808 1441407:151629574372 1875711:155904349696 1988859:156914378224 2643183:190459818484 2684647:352617812944 3041127:622717901620 3873535:858555169576 4637979:1318802294932 5656191:2412493616608 6416623:4799996945368 6631675:60342610919632

How high an orbit climbs

The Collatz orbit of 27 climbs to 9,232 before it falls, and below ten million the champion, 6,631,675, climbs to sixty trillion — almost exactly the square of where it started. That is not a coincidence of the two numbers but a law of the whole family: an orbit climbs to x times its start with a chance of about one in x, and the exponent is one because half of three-halves plus half of a half is exactly one. Among N starts the luckiest climbs about N-fold, and so the records grow like the square of the start.

dynamics · Collatz
When to stop tossing a coin. 1:1 2:2 3:3 4:2 5:3 6:2 7:3 8:2 9:3 10:4 11:3 12:4 13:3 14:4 15:3 16:4 17:5 18:4 19:5 20:4 21:5 22:4 23:5 24:4 25:5 26:4 27:5 28:4 29:5 30:6

When to stop tossing a coin

Toss a fair coin as many times as you like and stop whenever you choose; you are paid the proportion of heads so far. Stopping after a first head pays one, so the only question is what to do after a tail. Waiting for the first moment heads lead pays exactly π/4 on average. Waiting for a lead of two pays exactly ln 2. The best possible rule pays about 0.79295, a number known to six decimal places only since 2013 — and it stops when the lead reaches about 0.84 times the square root of the number of tosses, a constant that comes from Brownian motion.

probability · Optimal stopping
Two random loops and the crossings between them. 56 crossings, 25 positive, 31 negative, linking number -3.

Many crossings and a small linking number

Two random loops of a thousand steps, tangled round a common centre, cross each other about a thousand times in any picture of them. The linking number is half the signed count of those crossings — and it is typically about three. The signs cancel in nearby pairs, wherever one loop dips under the other and comes back, and what survives grows roughly as the fourth root of the length. Shut the same loops in a box and the cancellation stops: the crossings grow as n², and the linking number as n.

topology · Linking number
Two thinned harmonic series that never stop growing. every n: 10d 23.603067, 40d 92.680619, 120d 276.887427; no digit 9: 10d 15.109789, 40d 22.589564, 120d 22.920604; as many 7s as 3s: 10d 11.327995, 40d 24.391523, 120d 43.428896; digit sum a prime: 10d 7.156214, 40d 21.096266, 120d 51.331792

A rule that counts lets the sum escape

Strike out every number containing a 9 and the harmonic series converges, to 22.92. Keep only the numbers with as many 7s as 3s and it diverges — slowly, like the square root of the number of digits. Ask for two such balances and it still diverges; ask for three and it converges. The dividing line is Pólya's theorem that a random walk comes home in one and two dimensions and not in three.

analysis · Harmonic series
Two losing games with memory that win together. game A: -1.8000; game B: -1.9390; a fair coin chooses: 1.7434; the cycle A B B: 1.9077; ε=0.003.

Two losing games with a memory

Parrondo's first paradox needed a game that watched the player's capital. This one watches nothing but the last two results: a coin that wins nine times in ten after two losses, one time in four after a loss and a win, seven times in ten after two wins. Alone it loses, and so does a slightly unfair coin; played at random together they win. The walk treats every position alike, and the paradox survives — because it was never about position.

probability · Random walk
What is left in the other box. Banach matchbox remainder distribution for N=50: means p=0.5: 7.0385, p=0.55: 9.9165, p=0.6: 16.1560; at p=0.5 P(0)=0.07959, P(1)=0.07959.

The matches left in the other pocket

A smoker keeps a box of fifty matches in each pocket and picks a pocket at random. When one box is found empty, the other holds about seven, and none and one are exactly equally likely. Favour one pocket by a tenth and the answer is sixteen; give each box five thousand matches and a fair choice leaves seventy-nine while a bias of one in a hundred leaves nearly two hundred — because a fair remainder grows like a square root and any bias makes it grow in proportion, with the change-over at a bias of one over the square root of the box.

probability · Expectation
A family of 16, and the walk that counts it. seed 11: children 2,1,2,2,0,2,1,1,2,0,0,0,0,1,1,0; walk 0,1,1,2,3,2,3,3,3,4,3,2,1,0,0,0,-1

The walk that counts a family

Start with one ancestor, give everyone a random number of children, and ask how big the whole family gets. Visit the family member by member and keep a running total of children minus one: the total is a random walk, and the family is finished at the exact step the walk first drops below zero. A theorem about rotating sequences then gives the size's law in one line, and when each person has on average one child it is Cayley's count of labelled trees, multiplied by e⁻ⁿ/n!.

probability · Random walk

Named alongside it

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

ExpectationMarkov chainInvariantLimitMartingaleProbabilityRecurrenceScalingSimulationStationary distributionVarianceBinomial coefficient

All concepts