Concept

Expectation

The average of a quantity's values, each weighted by how likely it is. It need not exist at all: for a heavy-tailed quantity the defining sum or integral diverges, and every argument using it fails.

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

Waiting for all 6 kinds. One bar per new kind: the expected number of draws needed to see a kind not yet seen, rising as fewer of them are left, and adding to 14.70 draws in total.

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.

probability · Expectation
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
One set of sums, two scalings, two different limits. The exact distribution of a sum of n independent copies, scaled two ways. Divided by n it collapses onto the mean; divided by the square root of n it holds a fixed width and settles into a shape.

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.

probability · Central limit
5,040 orders, 7 thresholds, one best rule. For each number of candidates passed over, the share of the 5,040 possible arrival orders in which the rule ends up with the best of the 7. The count is exhaustive.

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.

probability · Optimal stopping
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
Averages of a heavy-tailed quantity, which never settle. Running averages of draws from a Cauchy distribution, which jump rather than converge, beside the cumulative distributions of averages of 1, 4 and 16 draws, which lie on top of one another.

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.

probability · Central limit
How fast a sum becomes a bell curve. The largest gap between the distribution of a standardised sum and the bell curve, against the number of terms, on logarithmic axes. Both summands fall along a line of slope about minus a half.

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.

probability · Central limit
The chance of being connected, against the chance of an edge. Curves of the exact probability that a random graph on three to six labelled points is connected, plotted against the probability of each individual edge.

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.

probability · Random graphs
Two unbiased estimates of one integral, and their spread. The sharply peaked integrand with the proposal density that follows it, above a strip plot of 200 estimates from each of two methods; the weighted estimates cluster 4.2 times more tightly about the same value.

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.

probability · Monte Carlo
The expected number of monochromatic sets, and where it drops below one. The logarithm of the expected number of single-coloured 4, 5, 6-point sets in a random two-colouring, plotted against the number of points, with the crossing of one marked for each.

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.

discrete · Ramsey theory
Which regions each rule favours. Average seats above or below exact quota for the largest and the smallest region, under each of the five methods, over 400 generated instances.

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.

applied · Apportionment
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
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
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 moment a giant piece appears. The largest component's share of 900 points plotted against the average degree, with the measured values as dots and the predicted curve behind them. The curve is flat at zero below an average degree of one and rises steeply above it.

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.

probability · Random graphs
One piece, and connected, are different thresholds. Two curves against the average degree for graphs of 400 points: the largest component's share, rising from an average degree of one, and the probability of connectivity, rising only near the logarithm of the point count.

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.

probability · Random graphs
A triangle appears when the count says it should. The measured probability of containing a triangle against the edge chance, on graphs of 200 points, beside the expected number of triangles capped at one.

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.

probability · Random graphs
58.6% at 46 candidates, against 37% without the values. The chance of ending with the best candidate when the values are shown, against the number of candidates, for 10 sizes. It falls towards 0.5802 rather than towards 1/e.

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.

probability · Optimal stopping
About the fourth-best, whatever the size of the field. The smallest expected rank achievable by an online rule, against the number of candidates, for 10 sizes. It rises to 3.8516 at 2500 candidates and its limit is 3.8695.

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.

probability · Optimal stopping
An online rule taking nine tenths of what an oracle takes. The share of the oracle's expected maximum secured by the best single threshold, and by the threshold at the median of the maximum, for 8 field sizes of independent uniform values.

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.

probability · Optimal stopping
The most mass 2 deviations out, with only a mean and a variance. The distribution putting as much probability as possible outside a window 2 standard deviations wide, found by searching every triple of support points, with the quadratic certificate that bounds it drawn over.

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.

probability · Concentration
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
Waiting for all 6 when they are not equally likely. One bar per kind giving the expected wait for that kind on its own, with the rarest much the tallest, and the expected wait for the whole collection printed above them.

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.

probability · Expectation
How long 4 equally likely patterns take to appear. A bar for each of 4 patterns of 3 coin tosses giving the expected number of tosses before it first appears, with the lengths at which each pattern overlaps itself listed.

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.

probability · Expectation
Fair bits from a biased coin. 44 flips of a coin biased 0.7 towards 1, read in 22 pairs. Mixed pairs are kept and give their first bit; matched pairs are discarded. Over a long run the output is 50.2% ones, at 0.210 output bits per flip.

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.

computation · Pseudorandomness
One experiment, measured by runs and by awakenings. Two unit squares for the same coin and the same schedule: the same experiment weighed two ways: by runs, heads keeps half the square; by awakenings, heads is one of 3 equal slices.

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.

probability · Bayes
A random pairing of 24 edges. Chord diagram of one uniformly random pairing of a 24-gon's edges, corners coloured by the vertex they become. a 24-gon with its edges paired at random and glued head to tail: the 24 corners fall into 3 vertices, so the surface has genus 5, against a most possible of 6.

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.

topology · Surface classification
Measuring a closed curve with inlets by throwing lines at it. A curve inside a disc crossed by a sample of random lines with each crossing marked, beside the mean number of crossings and the length it implies against the true length.

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.

analysis · Arc length
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
A random labelled tree on 60 points. A tree drawn in horizontal layers by distance from a root point, with the leaves coloured differently from the internal points.

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.

discrete · Labelled trees
Who does well in a random market, as it grows. A log-log plot of the average rank of partner for the proposing side and the receiving side of random balanced markets against the market's size, with dashed curves for ln n and n over ln n.

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.

applied · Stable matching
How much the first player can guarantee, as the coin's bias moves. A plot of the first player's best guaranteed winning chance in Penney's game against the probability of heads, a third on a fair coin and rising past one half only when the coin is heavily biased.

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.

probability · Expectation
Three patterns that beat one another in a circle: HHHT, TTHH, HTTH. Three coin-toss patterns at the corners of a triangle with arrows showing which beats which in two-way races, and each pattern's chance of winning when all three race.

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.

probability · Expectation
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
A random ranking on the triangular graph, 8 a side. A bipartite graph in which arrival t is joined to places t through 8. One random ranking of the places is used to match greedily; 5 of 8 arrivals are matched.

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.

discrete · Halls theorem
What a rule collects when every value comes from the same distribution. uniform on [0, 1]: best rule 0.995, one threshold 0.635 of E[max] at n = 200; exponential: best rule 0.905, one threshold 0.678 of E[max] at n = 200; Pareto, tail exponent 2: best rule 0.802, one threshold 0.714 of E[max] at n = 200; Pareto, tail exponent 1.2: best rule 0.802, one threshold 0.682 of E[max] at n = 200.

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.

probability · Optimal stopping
The expected rank a threshold rule achieves with the values shown, against what is known. n=1: 1.0000 (c=4.000); n=2: 1.2500 (c=1.000); n=3: 1.4009 (c=1.124); n=5: 1.5868 (c=1.257); n=10: 1.8141 (c=1.416); n=20: 1.9950 (c=1.555); n=50: 2.1557 (c=1.701); n=100: 2.2284 (c=1.781); n=200: 2.2725 (c=1.838); n=400: 2.2983 (c=1.877); n=800: 2.3130 (c=1.902).

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.

probability · Optimal stopping
The roots of random polynomials of degree 30 and 100: few are real. degree 30: 2 real roots at -2.335, -1.074; degree 100: 2 real roots at -0.327, 0.994.

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.

algebra · Polynomial roots
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
What a seller collects under first-price and second-price rules. Histograms of 20000 simulated revenues with 3 uniform bidders: second-price mean 0.4988, variance 0.0497; first-price mean 0.4995, variance 0.0167.

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.

applied · Equilibrium
Every slice of a tilted bell is a bell, centred off the axis. Contour ellipses of a two-variable bell with correlation 0.6, five vertical slices drawn as bells, their centres on the line y = 0.6x, and the ellipses' long axis on the diagonal y = x.

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.

algebra · Completing the square
A function on nine points, and the tree with two marks it becomes. Left: a function on 9 points as arrows, with cycles through 2, 5, 7 and trees hanging into them. Right: the tree Joyal's rule makes from it, a path from head 7 to tail 2 with the same trees hanging below.

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.

discrete · Labelled trees
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
Four lists, merged in pairs, find a cancelling quadruple. A merge tree for four lists of 256 random 24-bit strings: two merges on the low 8 bits, then one on all 24, ending in 1 solution(s).

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.

probability · Birthday problem
One shared birthday, as a measurement of the year. Histogram over 20000 rooms of the estimate T(T − 1)/2 from the first shared birthday, averaging 361 against 365, spread widely.

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.

probability · Birthday problem
Records in a thousand draws, and the lengthening waits between them. A sequence of 1000 uniform draws on a logarithmic position axis, with records at positions 1, 6, 11, 27, 36, 145, 539, 927.

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.

probability · Expectation
Running totals of random steps, stopped as they pass 4. Four staircases of uniform steps stopped on passing 4, taking 11, 8, 8, 10 steps; the exact mean is 8.666604.

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.

probability · Expectation
The longest run of heads at three sizes, never the same shape. n=65536: 12:0.018 13:0.117 14:0.233 15:0.239 16:0.172 17:0.104 18:0.057 19:0.030 20:0.015; n=82273: 13:0.075 14:0.204 15:0.249 16:0.197 17:0.124 18:0.070 19:0.037 20:0.019; n=104408: 13:0.040 14:0.162 15:0.248 16:0.221 17:0.148 18:0.086 19:0.046 20:0.024 21:0.012.

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.

probability · Expectation
Two random strings of bits and the longest thread between them. Two random binary strings of length 36; longest common subsequence 27.

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.

probability · Concentration
Strings that overlap themselves leave more behind. 00: 253.293; 01: 230.283; 02: 230.299; 03: 230.315; 04: 230.330; 05: 230.345; 06: 230.361; 07: 230.376; 08: 230.390; 09: 230.405; 10: 220.887; 11: 244.784; 12: 222.442; 13: 223.049; 14: 223.575; 15: 224.033; 16: 224.438; 17: 224.798; 18: 225.120; 19: 225.410; 20: 225.673; 21: 225.913; 22: 249.163; 23: 226.334; 24: 226.520; 25: 226.692; 26: 226.852; 27: 227.001; 28: 227.140; 29: 227.270; 30: 227.393; 31: 227.508; 32: 227.617; 33: 250.747; 34: 227.817; 35: 227.910; 36: 227.998; 37: 228.081; 38: 228.161; 39: 228.237; 40: 228.310; 41: 228.380; 42: 228.446; 43: 228.510; 44: 251.598; 45: 228.631; 46: 228.688; 47: 228.743; 48: 228.796; 49: 228.847; 50: 228.896; 51: 228.944; 52: 228.990; 53: 229.035; 54: 229.078; 55: 252.146; 56: 229.161; 57: 229.201; 58: 229.239; 59: 229.277; 60: 229.313; 61: 229.348; 62: 229.383; 63: 229.416; 64: 229.449; 65: 229.481; 66: 252.538; 67: 229.543; 68: 229.572; 69: 229.601; 70: 229.630; 71: 229.657; 72: 229.684; 73: 229.711; 74: 229.737; 75: 229.762; 76: 229.787; 77: 252.837; 78: 229.835; 79: 229.859; 80: 229.882; 81: 229.904; 82: 229.927; 83: 229.948; 84: 229.970; 85: 229.991; 86: 230.011; 87: 230.031; 88: 253.077; 89: 230.071; 90: 230.090; 91: 230.109; 92: 230.128; 93: 230.146; 94: 230.164; 95: 230.182; 96: 230.199; 97: 230.216; 98: 230.233; 99: 253.275.

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.

analysis · Harmonic series
Seven workers, seven jobs, one cheapest way. A 7 × 7 table of exponential costs; optimal assignment 1→5, 2→2, 3→4, 4→1, 5→6, 6→7, 7→3 costing 0.7482; expected optimum Σ 1/k² = 1.511797.

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.

applied · Assignment
Cells of points scattered at random. Poisson–Voronoi tessellation of 600 points on a torus; mean sides 6.000000000; side counts 3: 9, 4: 56, 5: 165, 6: 167, 7: 131, 8: 49, 9: 18.

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.

geometry · Voronoi
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
Knowing the coin, learning it, and guessing it once. p=0.6, 2000 tosses; final log10 wealth: hindsight 19.30, knew p 19.25, learned 17.73, plug-in from 20 tosses (15 heads, f=0.50) -25.88.

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.

probability · Expectation
The trades a buyer and seller cannot make. Uniform private values: efficient surplus 1/6; best incentive-compatible, individually rational, budget-balanced mechanism trades iff b − s ≥ 1/4, surplus 9/64 = 27/32 of the efficient.

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.

applied · Fair division
The cheapest tree through forty points. n=40, seed 8: total 1.063675, largest edge 0.0605, ζ(3)=1.2020569.

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.

applied · Assignment
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
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
Where a randomly broken stick can land. De Finetti's triangle of all ways to break a stick into three pieces, with 500 random breaks: the 118 in the shaded middle quarter, where every piece is shorter than half the stick, are the breaks whose pieces form a triangle.

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.

probability · Expectation

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

All concepts