Expectation
Named by 61 essays across 10 fields — each of them below, with the objects they name alongside it.
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.
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 average settles and the wobble does not
Two theorems are usually met a page apart and sound as though one is a sharper version of the other. They are the same sums looked at through two different magnifying glasses: divide by the number of them and everything collapses to a point, divide by its square root and a shape appears.
When to stop looking
Candidates arrive one at a time in a random order. Each must be accepted or rejected on the spot, with no going back and no way to know what is still to come. The best possible rule is to look at about a third of them and then take the first one that beats everything seen — and it works about a third of the time, however many there are.
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.
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.
How fast the bell arrives
The limit theorem says a standardised sum approaches the bell curve and says nothing about when. The rate is one over the square root of the number of terms, the constant in front is made of the third moment, and both are visible.
The moment everything joins up
Add edges to a set of points one chance at a time and the graph goes from dust to a single piece — not gradually, but over a window that narrows as the point count grows. The last obstacle is almost always a single point with no edge at all, and that is what fixes where the change happens.
Sampling where the answer lives
Monte Carlo error cannot be made to fall faster than the square root, so the only thing left to attack is the constant in front of it. Drawing points where the integrand is large, and dividing by how often they were drawn, leaves the answer alone and can shrink the noise many times over.
The colouring nobody has ever seen
Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.
The rule with no favourites
Over four hundred instances, Jefferson's method gives the largest region a third of a seat more than its exact share and the smallest a third of a seat less. Adams reverses both. Webster's average is a hundredth of a seat, and that is not luck.
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 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.
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.
The moment a giant appears
Raise the chance of an edge slowly and a random graph does nothing for a long time, then in a narrow window acquires a component holding a definite fraction of everything. The fraction is the root of an equation, and the equation says why the transition is where it is.
Two thresholds, not one
A random graph acquires a piece holding most of its points at average degree one, and is still not connected. Connectivity waits until the average degree reaches the logarithm of the size, and what holds it up is the very last isolated point.
Finding a threshold with two moments
Every monotone property of a random graph has a threshold, and locating one is nearly always the same two calculations — count what the property needs, and check the count does not concentrate on rare cases. The triangle is where the method is cleanest.
When the numbers are shown
The secretary rule wins a third of the time and cannot do better, because it is told only who is ahead. Show the actual values and say where they came from, and the same problem is won three times in five — by a standard that falls as the end approaches.
Giving up on the best
The secretary rule treats landing the second-best exactly as badly as landing the worst, which is a strange thing to want. Ask instead for the smallest average rank and the answer is about the fourth-best candidate — whatever the size of the field, and whether it is ten or ten million.
Half of what an oracle takes
Compare an online rule not against the best it could have done but against a rule that has seen every value in advance. One fixed threshold secures half of what the oracle collects, whatever the distributions are — and there is an example on which half is all there is.
The bound is the answer to a search
Chebyshev's inequality is not a clever estimate that happens to be sharp. It is the exact answer to a maximisation over all distributions with a stated mean and variance, and the polynomial that proves nothing beats it is the certificate a search of that kind always produces.
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.
The one that hardly ever comes up
Make the kinds unequally likely and the tidy decomposition into stages fails, because a stage's rate now depends on which kinds turned up rather than on how many. What replaces it is an alternating sum over every subset — and the rarest kind turns out to be nearly the whole answer.
Two patterns, one chance, different waits
HTH and HTT are equally likely in any given window of three tosses. Waiting for HTH takes ten tosses on average and waiting for HTT takes eight, and the difference is not about probability at all — it is about what a failed attempt leaves behind.
Fair bits from an unfair coin
Read a biased coin's flips in pairs, keep 01 as 0 and 10 as 1, and throw away the rest: the output is exactly fair, whatever the bias, and nobody needs to know the bias. The trick wastes most of the coin, the waste can be recycled almost up to the ceiling Shannon's entropy sets — and it fails quietly the moment the flips remember each other.
One coin, counted by runs and by wakings
Beauty is put to sleep and a fair coin is tossed. Heads, she is woken once; tails, twice, with the first waking erased from her memory. Each time she wakes she is asked how likely heads is. One half, say some; one third, say others; and unlike every earlier puzzle of this kind, stating the protocol exactly does not end the argument.
The surface a random gluing makes
Pair the edges of a large polygon at random and glue each pair head to tail. The surface almost always has nearly as many handles as the polygon allows: a thousand edges leave about seven and a half vertices, and the genus is within four of its ceiling of 250. The vertices behave like the cycles of a random permutation, and their average is a harmonic number.
A length counted by the lines that cross it
Throw straight lines at random across a curve and count how often they cross it. The average count, times π times the radius of the target, is the curve's length — for a wiggly closed curve, a spiral or a snowflake alike, with no following of the curve and no derivative anywhere. It is Crofton's formula of 1868, and it measures length the way a map-reader's ruled transparency does.
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 random tree is one part in e leaves
Choose a labelled tree on n points uniformly at random. A point is a leaf exactly when its label never appears in the tree's Prüfer code, so the share of leaves is (1 − 1/n)^(n − 2) — half the points for a tree on four, 36.8% for a large one, the reciprocal of e. The whole degree distribution follows the same way: one plus a Poisson count with mean one.
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.
A coin that lets the first player win
On a fair coin the second player in Penney's game always has a better pattern than the first, and the first can hold them to no worse than two to one. Bend the coin and every overlap is paid for in the letters it uses: the replies change, the first player's share swings between a third and a half, and past a heads chance of 1/∛2 the first player simply names HHH and wins.
Three patterns in a circle
Race three coin patterns at once and the gamblers' accounting still gives each one's chance of arriving first — one fairness equation per pattern. What it does not give is any way to read the three-way result off the two-way ones. HHHT, TTHH and HTTH beat one another in a circle, and HHH loses both its head-to-head races and still finishes ahead of one of the patterns that beat it.
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.
Matching as they arrive
Applicants arrive one at a time, and each must be given a post or turned away on the spot. Any sensible rule matches at least half as many as the best assignment chosen with hindsight, and an adversary arranging the arrivals can hold every fixed rule to exactly half. Shuffle the posts once, at random, and give each arrival its best-ranked free post: the guarantee rises to 1 − 1/e, about 63%, and no rule of any kind can do better.
When every value comes from the same hat
A rule that sees values one at a time and must keep or discard each on the spot can guarantee half of what a prophet collects, and no more, when the values come from different distributions. When they all come from the same one, the guarantee rises to 0.745 — and a single fixed threshold, set so that each value crosses it with chance 1/n, already secures 1 − 1/e. For bounded values the best rule collects nearly everything; only a heavy tail, where one enormous value carries the prize, keeps the gap open.
The rank that remembers every value
Values arrive one at a time, each must be kept or discarded on the spot, and the aim is to keep one whose rank among all of them is low on average. Told only who is leading, the best rule gets 3.87. Shown the values, a rule gets below 2.33 — and how much lower the best possible rule goes is not known, because the rank of what is kept depends on every value seen, and the best rule may need to remember all of them.
Almost none of the roots are real
Pick the coefficients of a polynomial of degree a thousand at random, each one an independent draw from the bell curve, and ask how many of its thousand roots are real. The answer is about five. Mark Kac found in 1943 that the average grows only like (2/π) ln n, and the reason can be read off the real line itself: the real roots crowd towards +1 and −1 and spread evenly on a logarithmic scale of distance from them.
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.
Two auctions that earn the same
In one sealed-bid auction the winner pays its own bid; in the other it pays the second-highest bid. Bidders behave completely differently — in the second they bid what the object is worth to them, in the first they shade their bids down by exactly a fraction — and the seller's revenue is spread differently. Yet the seller expects to collect precisely the same amount, (n − 1)/(n + 1) for n bidders with values spread evenly, and so does an auction in which everybody pays. The equality breaks the moment bidders dislike risk, and it says nothing about how much a reserve price can add.
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.
Every function is a tree with two marks
There are n to the n functions from n points to themselves, and n to the n − 2 trees on those points. André Joyal noticed in 1981 that the missing factor of n² is a choice of two points — a head and a tail — and that a function, read the right way, simply is a tree with a head and a tail. The reading turns Cayley's formula into one line and hands over a fact about random trees from the birthday problem.
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.
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 wait that ends and has no average
Draw a number, then keep drawing until one beats it. Half the time the very next draw does. The wait is certain to end, it is usually short, and its average is infinite — and the chance of still waiting after n draws is exactly 1/(n + 1), whatever the numbers are drawn from, because symmetry is the only thing the calculation uses.
Two-thirds of a step past the line
Add random numbers between nought and one until the total passes one, and it takes e of them on average. Ask the same about passing any t and the answer is an exact finite sum that settles, within a few units, onto the line 2t + 2/3. The slope is one over the average step. The two-thirds is the interesting part: it is what the one step that crosses the line charges for being chosen by its length, and it is set entirely by how much the steps vary.
The longest run has no limit
Toss a fair coin n times and the longest run of heads is about log₂ n. The average settles: it is log₂ n − 0.667 to within a few millionths by a million tosses. The distribution does not. Because the run is a whole number and log₂ n is not, the chance of each value swings round the same cycle once every doubling of n, for ever, and computing it exactly to a million tosses shows the swing as large at the end as at the start.
The longest thread between two random strings
Write down two random strings of a thousand bits each and find the longest sequence that can be read in both, skipping freely. It is about 81% of each, and the exact share — the Chvátal–Sankoff constant — has resisted computation for fifty years. Its fluctuations are a smaller mystery with a sharper edge: the variance is known to be at most n/2, and over every length that can be computed it grows like n to the power 0.7, with nobody able to say what it does after that.
What a missing string of digits leaves behind
Strike from the harmonic series every term whose denominator contains 42 and the rest adds up to 228.45. Strike out 99 instead and it adds up to 253.28. The difference is not about which numbers are lost but about waiting: 99 overlaps itself, so it takes 110 random digits on average to turn up where 42 takes 100, and the sum is almost exactly ln 10 times that wait.
One, plus a quarter, plus a ninth
Give n workers n jobs with every cost drawn at random, average one, and find the cheapest way to pair them. However large n is, the cheapest total averages less than π²/6, and for every n it is exactly 1 + 1/4 + 1/9 + … + 1/n². Parisi guessed the formula in 1998 from n = 1, 2 and 3; thirteen sizes of random tables, solved exactly, land on it within sampling error.
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.
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.
What not knowing the coin costs
Kelly's rule stakes the edge, and the edge is the one thing a bettor never has. Estimate it from twenty tosses and stake the estimate, and a lucky start can turn a favourable coin into certain ruin. Learn it toss by toss instead, with Laplace's rule, and the cost of ignorance shrinks to a factor of about the square root of the number of tosses — because a bettor who learns is exactly a bettor who split the money among every fixed fraction at once.
Some good trades cannot be made
A seller who values a car at s meets a buyer who values it at b, and neither knows the other's number. Whenever b is larger, a sale would make both better off. Myerson and Satterthwaite proved in 1983 that no way of haggling, auctioning or brokering can guarantee it: some sales worth making are always lost. With values spread evenly the best possible procedure trades only when the buyer's value beats the seller's by a quarter, loses five thirty-seconds of the surplus — and is reached by two people who simply name prices and split the difference.
The cheapest tree costs ζ(3)
Join n towns by every possible road, give each road a cost drawn at random between nought and one, and find the cheapest network of n − 1 roads that connects them all. However many towns there are, the bill tends to 1 + 1/8 + 1/27 + 1/64 + … = 1.2020569. The proof watches the cheap roads arrive one at a time and turns the cost into the area under a curve that counts the pieces of a growing random graph.
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.
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.
A stick broken in three
Break a stick at two random points and the three pieces form a triangle one time in four — a fact that can be read off a picture without integrating anything, because the pieces are a point spread evenly over a triangle and the good breaks fill its middle quarter. With more pieces the same picture gives 1 − n/2ⁿ⁻¹, which is also the chance that n random points on a circle avoid every semicircle. But 'break at random' is ambiguous: cut once and then cut the longer piece, and the answer is 2 ln 2 − 1.
Named alongside it
The objects these essays reach for when they reach for this one.
Random walkVarianceConvergence rateConditional probabilityMarkov chainHarmonic seriesSimulationExhaustive searchHeavy tailsIndependenceIrrevocable decisionLaw of large numbers