Random walk
Named by 51 essays across 9 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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!.
Named alongside it
The objects these essays reach for when they reach for this one.
ExpectationMarkov chainInvariantLimitMartingaleProbabilityRecurrenceScalingSimulationStationary distributionVarianceBinomial coefficient