Concept

Random permutation

An ordering of a list chosen so that every one of the possible orderings is equally likely. Shuffling a pack of cards thoroughly produces one, and many guarantees about algorithms hold on average over such an ordering rather than for every order.

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

400 random points and their longest rising chain, 34 long. 400 uniform random points in a unit square with the longest chain increasing in both coordinates marked: 34 points, against 2√n = 40.0.

The longest climb of a shuffle

Erdős and Szekeres guarantee that any n distinct numbers hold a climb or a fall of √n, and there are orders that allow nothing more. Shuffle a deck at random instead and the longest climb is almost exactly 2√n — with fluctuations of size n to the power one-sixth, distributed exactly as the largest eigenvalue of a large random matrix.

discrete · Ramsey theory
The same rule in the adversary's order and in a random order. Two copies of the 8-a-side triangular graph matched greedily with the worst ranking: 4 matched in the adversary's order, 5 in a random order (average 5.30).

Matching when the arrivals are shuffled

An adversary who chooses the order in which applicants arrive can hold any fixed matching rule to half the best. Take the order away and let it be random, and the plainest rule of all — give each arrival its first free place in a fixed list — rises to 1 − 1/e, because shuffling the arrivals turns out to be exactly the trick RANKING plays with the places, seen from the other side. Shuffle both and the guarantee rises again, to somewhere between 0.696 and 0.727, and where in that interval it lies is not known.

discrete · Halls theorem
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
Fifty-two cards, swapped the naive way. Naive shuffle, n=52: max ratio 1.3522 at card 2 → place 1; min ratio 0.7429.

A perfect coin and a biased shuffle

Give a program a perfect source of random numbers and ask it to shuffle a deck by swapping each card with a card chosen from anywhere in the deck. The result is biased, provably and for every deck of three or more cards: there are nⁿ equally likely runs and n! orders, and the first number is never a multiple of the second. In a deck of 52 some card-and-place pairs come up a third more often than they should. Swapping only with cards not yet placed fixes it; swapping only with later cards makes nothing but single cycles.

computation · Pseudorandomness
Every order of nine cards, and the ones a seed can reach. 16-bit LCG, 65,536 seeds, Fisher–Yates on 9 cards (high bits): 62616 of 362880 orders reached.

A seed is a deck

A shuffle that is perfectly correct, driven by a generator that passes every statistical test, can still deal almost none of the possible decks. A shuffle program is a function from the generator's starting state to an ordering of the cards, so it can never produce more orderings than the generator has states: a 32-bit seed reaches one deck in about 10⁵⁸. On nine cards and a 16-bit generator every case can be checked — 62,616 of the 362,880 orders are ever dealt — and on a full deck, six cards on the table are enough to name the seed and every card still to come.

computation · Pseudorandomness
The longest rising chain in a random cloud, by dimension. Mean longest chain divided by n^(1/d) for d = 2, 3, 4, 5 and n = 250, 500, 1000, 2000, 4000, 8000: d=2: 1.768, 1.804, 1.836, 1.863, 1.895, 1.919; d=3: 1.846, 1.928, 1.981, 2.022, 2.091, 2.125; d=4: 1.773, 1.884, 1.934, 2.026, 2.062, 2.141; d=5: 1.694, 1.762, 1.812, 1.913, 2.037, 2.030.

The longest climb in a cube

Among n random points in a square, the longest chain rising to the right has about 2√n points, a fact with a famous proof. Put the points in a cube and ask for a chain rising in all three directions, and its length is about c·n^(1/3) for a constant nobody knows. Béla Bollobás and Peter Winkler proved that the constants for every dimension stay below e and creep up to it. The upper bound is a single count of chains, and simulation shows how far below it the real chains fall.

discrete · Ramsey theory
Boxes as a permutation. A random permutation of 24 with cycle lengths 11, 7, 5, 1; longest 11.

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 · Inclusion exclusion
One swap splits the long cycle. A shuffle of 100 boxes whose longest cycle has 61 boxes, drawn as a ring; swapping the contents of two boxes 30 steps apart splits it into cycles of 30 and 31, so every cycle has at most 50 and all prisoners succeed.

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 · Inclusion exclusion

Named alongside it

The objects these essays reach for when they reach for this one.

PermutationCycleExhaustive searchHarmonic seriesLongest increasing subsequenceUniform distributionBipartite graphBirthday problemCompetitive ratioCycle decompositionDivisibilityExpectation

All concepts