Simulation
Named by 28 essays across 7 fields — each of them below, with the objects they name alongside it.
Fourteen people within a day
Twenty-three people probably include two with the same birthday. Fourteen probably include two whose birthdays are at most a day apart, and seven, two within a week. The near miss has an exact formula, found by a trick that takes k days away after every birthday and turns the question back into the plain one on a shorter year, and the pattern behind every threshold is a single square root: a window of k days either side makes each pair 2k + 1 times as likely to collide.
A room where nobody is alone
Twenty-three people probably include two who share a birthday. How many are needed before every single person shares a birthday with somebody else in the room? The answer is 3,064 — more than it takes for every day of the year to be somebody's birthday — and the reason is a count of loners, which rises as the room fills, peaks at 134 when the room is the size of the year, and then falls so slowly that the last loner lingers for thousands of arrivals.
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.
One extra person on one side
In a random market of a thousand a side, whoever proposes gets about their seventh choice and whoever receives gets about their hundred-and-fortieth. Add one person to one side and the advantage of proposing all but disappears: the shorter side does well and the longer side badly, whichever side proposes, and most people are left with exactly one stable partner.
Regression is a square completed halfway
A bell in two variables, sliced at a fixed x, is a bell in y — and completing the square in y alone says where it is centred: at ρx, on a line flatter than the ellipse's own axis. That gap is regression to the mean, and the same completion says it runs backwards in time just as well as forwards.
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.
Two chaotic orbits made to agree
Chaos means two copies of a system started a hair apart soon have nothing in common. Couple them — let each take a fraction ε of its next step from the other — and above a definite strength they agree to every digit for ever, while each stays exactly as chaotic as before. The strength needed is read off the same number that measured the chaos: the Lyapunov exponent.
Four lists find a collision sooner
Two lists of random 24-bit strings need about four thousand entries each before some string appears in both — the birthday bound. Ask instead for one string from each of four lists whose exclusive-or is zero, and lists of a few hundred suffice, because merging the lists in pairs manufactures the near-misses a direct search would have to find by luck. David Wagner's algorithm turns the square root into a cube root, and more lists into smaller roots.
Counting a population by its repeats
The birthday problem runs forwards from a known year to the chance of a match. Run it backwards and the matches measure the year: count how many pairs among the draws came out the same, and the number of kinds is about the number of pairs divided by that. It costs the square root of the population rather than a census of it — and when the kinds are unevenly common, what the repeats measure is not how many kinds there are but how many they behave like.
A crowd of clocks that falls into step
Give a thousand oscillators a thousand different natural rhythms and let each be pulled towards the average phase. Below a definite pull nothing happens; above it a cluster forms and grows, and Kuramoto's 1975 calculation says exactly where: at twice the spread of the frequencies, with the order growing as the square root of one minus the threshold over the pull. A simulation lands on that curve to the third decimal.
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.
A ring of clocks settles into a twist
Put identical oscillators round a ring, each pulled only by its neighbours, and start them at random. They always lock — every one ends at the same frequency — but most of the time not in step: the angles wind round the ring a whole number of times and stay wound. The winding number a random start chooses is spread like a bell whose width grows like the square root of the ring, and only coupling to about a third of the ring makes full synchrony certain.
The shape of a cell around a random point
Scatter points at random and give each the region nearer to it than to any other. The cells come in every shape from triangles to twelve-sided polygons, and almost nothing about them is fixed by a formula — except one thing: on a closed surface they have exactly six sides on average, every time, because three cells meet at every corner. Two hundred thousand cells measure the rest: 29.5 per cent hexagons, Lewis's law, and small cells surrounded by large ones.
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.
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.
Holding one still turns the other over
A quantity can rise with an outcome and still predict it downwards once a second quantity is held fixed. Completing the square in two predictors says exactly when: the pair of correlations has to fall in a wedge whose angle is arcsin of the predictors' own correlation. Averaged over every possible correlation matrix the chance is exactly 1/4 − 1/π², about one coefficient in seven; two coefficients never reverse together, and with two dozen predictors almost two in five do.
The ash a random soup leaves
Fill a grid at random, apply Conway's rule — three neighbours give birth, two or three keep a cell alive — and the population collapses from half the cells to about three in a hundred, leaving scattered blocks and blinkers. Five cells in the shape of an R take 1,103 generations to do the same and peak at 319 on the way. The Game of Life is a universal computer, so nothing short of running it can say when a pattern will settle, and the figures run it.
How often the rules find the majority favourite
When one candidate beats every rival head to head, a voting rule ought to elect it. Plurality does about three times in four when every ranking is equally likely, the runoff between the top two 96 times in a hundred, Borda's count 90. Every profile of up to 51 voters is counted exactly, the limit is sampled, and adding candidates pulls plurality down below one half.
How many stable matchings a market has
A market with random preferences on both sides has not one stable matching but many — a few at ten a side, a few dozen at a hundred, about a thousand at a thousand — and all of them are reached from the proposers' best by a chain of rotations. Boris Pittel proved that the average grows like n ln n / e. The averages measured here sit at a third of that at every size a computer can reach.
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.
Where random discs change sign
Scatter discs at random over the plane and their union breaks into pieces with holes in them. Pieces minus holes has an exact average, η e^(−η)(1 − η) per disc area, where η is how many discs cover a point on average, and it changes sign at exactly η = 1, with 63.2% of the plane covered. The discs first join up across the whole plane later, at η ≈ 1.128. The sign change looks like the moment the union connects and is not; and for squares or long rectangles turned at random it comes earlier still, at 4πA/L², which only a disc reaches one.
What a random chord is
Draw a chord of a circle at random. How often is it longer than the side of the inscribed equilateral triangle? Pick two random points on the rim and the answer is 1/3. Pick a radius and a random point on it, and the answer is 1/2. Pick a random midpoint in the disc, and the answer is 1/4. All three calculations are correct, and Bertrand published them in 1889 to warn that the phrase had no meaning. Eighty-four years later Jaynes argued that one answer is right after all.
A chain of majorities leads anywhere
Put voters on a line and the middle one's position beats everything. Put five in a plane and nothing is safe: seven majority votes can walk the group from its own centre to a place every one of them likes less. One small circle, drawn through the lines that split the voters, says exactly how far a single vote can go, and it shrinks as the group grows.
Out before the table says so
Detroit has 49 wins and 27 games left, so it can reach 76, and the leader has 75. On paper it is alive. It is not: the four teams ahead must play 27 games among themselves, and whoever wins them, those four finish with an average above 76. Finding that takes one maximum flow, and it is checked against every possible result of every game.
An orbit stuck to an island
A chaotic orbit in the standard map stretches at 0.44 a step, and then for 19,000 steps it almost stops stretching at all. It has wandered into the fringe of an island of regular motion and been caught. So gaps between visits to a box do not die away exponentially as they would in a uniformly chaotic map; they fall as a power, and an orbit of 400 million steps still has not seen the longest.
Eight points that refuse the cube
Place eight points on a sphere so that the closest pair is as far apart as possible. A cube manages 70.53°. Rotating one face by 45° and pushing the faces together gives 74.86°. A botanist counting pores on pollen grains asked this in 1930, and proofs still stop at fourteen points: one search in five hundred finds the best thirteen, whose failure to reach 60° is why kissing spheres stop at twelve.
A restaurant and a shuffled deck
Each new customer sits at a table with chance proportional to the people there, or starts a new one with weight θ. That one rule gives the kinds of species in a catch and the alleles at a gene. At θ = 1 it is exactly the cycles of a shuffled deck, 62.4% of which lie in the longest, and the same shares describe the largest prime factors of a random number.
Peaks, pits and passes
Take any lumpy closed surface and any direction of height. Peaks plus pits minus passes is 2 on a sphere and 0 on a torus, whatever the lumps, in every direction. Average one vertex's score over all directions and it becomes the corner's angle defect, computed from nothing but comparisons. So Gauss–Bonnet follows from a count of which neighbours lie higher.
Named alongside it
The objects these essays reach for when they reach for this one.
ExpectationRandom walkStabilityThresholdBirthday problemExhaustive searchNormal distributionSynchronisationEigenvalueGrowth ratePeriodic orbitTorus