Generator

All 24 arrangements of 4 objects, and the 9 that move every one

A generator in the probability library, called 115 times across 22 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

derange is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

All 24 arrangements of 4 objects, and the 9 that move every one. Every permutation of 4 objects drawn as a grid of cells, with the diagonal — where an object stays where it began — shaded, and the arrangements that avoid it entirely marked.

How many matches a frustrating deal has

How many matches a frustrating deal has. 0:0.016233/0.018316, 1:0.068899/0.073263, 2:0.144164/0.146525, 3:0.198194/0.195367, 4:0.201325/0.195367, 5:0.161112/0.156293, 6:0.105762/0.104196, 7:0.058554/0.059540, 8:0.027898/0.029770, 9:0.011615/0.013231, 10:0.004276/0.005292, 11:0.001406/0.001925, 12:0.000416/0.000642

Thirteen squares of forbidden cells

Thirteen squares of forbidden cells. rook numbers of one square 1, 16, 72, 96, 24; of the board r₁ to r₄ 208, 20904, 1352416, 63317176.

Large terms that cancel to one in sixty

Large terms that cancel to one in sixty. 0:1.000, 1:4.000, 2:7.882, 3:10.20, 4:9.745, 5:7.331, 6:4.521, 7:2.350, 8:1.051, 9:0.4105, 10:0.1417, 11:0.04365, 12:0.01210, 13:0.003035, 14:0.0006932, 15:0.0001448, 16:0.00002776, 17:0.000004904, 18:8.004e-7, 19:1.210e-7, 20:1.698e-8, 21:2.216e-9, 22:2.695e-10, 23:3.056e-11, 24:3.237e-12

More ranks bring it towards e to the minus d

More ranks bring it towards e to the minus d. d=1: m=13 0.367879, m=60 0.367879, e^-d 0.367879; d=2: m=13 0.130038, m=60 0.134203, e^-d 0.135335; d=3: m=13 0.045947, m=60 0.048957, e^-d 0.049787; d=4: m=13 0.016233, m=60 0.017859, e^-d 0.018316

Two hundred thousand deals against the formula

Two hundred thousand deals against the formula. wins 3308/200000 = 0.016540; exact 0.016232727.

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Probability

A card game almost nobody wins

Shuffle a deck and deal it face up, calling ace, two, three, up to king and round again, four times through. If a card ever matches the rank being called, the game is lost, and it is won about one time in sixty-two. The chance is 0.016232727…, exact, because the forbidden pairings form thirteen separate four-by-four squares and inclusion–exclusion turns their rook numbers into a sum — a sum whose terms climb past ten before they cancel to a sixtieth, and which is also the integral of a power of a Laguerre polynomial. The obvious guess, e to the minus four, is eleven per cent too high, and two hundred thousand deals can tell.

Probability

A hundred prisoners and one shuffle

A hundred prisoners each search fifty of a hundred boxes for their own number, one at a time, with no communication once it starts. If any fails, all are executed. Choosing at random gives them a chance of 8 × 10⁻³¹. There is a rule that gives them 31%, and no rule can do better. Every prisoner's individual chance is still one half: what the rule changes is not how often each succeeds but how those successes line up.

Probability

A round table with no couple together

Seat n couples round a table, men and women alternating, so that nobody sits beside their partner. Once the women are placed the men face a board of forbidden cells that bends round a corner — and that corner is the whole difficulty. The forbidden cells form a cycle, a count of non-adjacent points on a cycle finishes the problem, and the chance of a good seating creeps towards e^(−2) far more slowly than the hat problem reaches 1/e.

Probability

A sum stopped early still says something

Inclusion–exclusion corrects an overcount, then the correction's overcount, and so on to the end. Stop after any number of terms and the result is not merely an approximation: after an odd number it is too high and after an even number too low, always. So two or three terms bracket an answer whose full sum is out of reach — as long as the events being counted are rare.

Probability

Add the odds from the end

Watch a sequence of independent events and try to stop exactly on the last one that happens. Add up the odds of the events from the end backwards until the total reaches one, and stop at the first success from there. That rule is the best possible for any probabilities whatever, and the secretary problem is the special case in which the chances are one over the position.

Probability

Arcs that cover a circle

Throw fourteen arcs, each a fifth of a circle, onto the circle at random: together they are nearly three times as long as it, and still a third of the time some stretch is left bare. The chance of covering is an alternating sum over which gaps are too long, found by W. L. Stevens in 1939. Its terms run into the thousands and cancel to almost nothing, and they say that random covering costs a logarithm.

Probability

Every pair side by side, once

Seat an odd number of guests at round tables for as many nights as it takes, the same table sizes every night, so that every two guests sit side by side on exactly one night. For a single table a zigzag turned a notch each night does it for any number of guests. For other table plans the answer is almost always yes — and for six guests at two tables of three, nine at tables of four and five, and eleven at three, three and five, an exhaustive search proves it is no.

Probability

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

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

How many get their own hat

The chance that nobody gets their own hat settles on 1/e. The chance that exactly one person does settles on 1/e too, exactly two on 1/(2e), exactly three on 1/(6e) — the Poisson distribution with mean 1. The reason is a set of averages that come out exactly 1 at every size, and the counts reach the limit so fast that eight hats are within six ten-thousandths of it.

Probability

Nobody gets their own hat

Hand back a pile of hats at random and ask for the chance that not one person gets their own. The answer barely moves as the crowd grows — it is a third and a bit at four people, and a third and a bit at four thousand.

Probability

One number for each arm

Several slot machines pay at unknown rates, and each pull both earns and teaches. The problem seems to tangle every machine with every other, and in the 1940s it was thought hopeless. Then John Gittins found that each machine alone has one number, and the rule is to play the highest. An exact search over 1,187,671 states of two arms gets the same value to six places.

Probability

One swap saves every prisoner

A hundred prisoners following the cycles of a shuffle all survive about 31% of the time. Let a helper look into the room first and swap the contents of two boxes, and they survive every time. With fewer boxes each, more swaps are needed — exactly one per cut a long cycle needs — and the number of swaps a random room demands has an exact distribution.

Probability

The cells a permutation must miss

A derangement is a permutation that misses the diagonal of a square grid. Forbid any other set of cells instead and inclusion–exclusion still counts what is left — driven entirely by one list of numbers, the ways to place non-attacking rooks on the forbidden cells. Boards that look nothing alike can share that list, and rooks on a staircase turn out to count the ways to split a set.

Discrete

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.

Analysis

The constant that counts what does not happen

Nothing grows in a shuffled pack of cards, and nothing grows in a factorial. Yet e sits in the middle of both — as the chance that a shuffle leaves nothing in place, and as the base that makes n! nearly a power.

Probability

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

The thresholds that nest

Allow a second acceptance in the secretary problem and the chance of holding the best rises from about 37 per cent to about 59. The best rule is still a threshold — but one threshold for each number of choices still in hand, the earlier ones starting sooner, and each additional choice buying less than the one before.

Probability

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

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

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

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.

The whole library · What the figures prove