04You Don't Control the Input, and You Can't See the Future

Page 3 handed you a fraction and a habit — name both halves, then move the one you are allowed to move.

Here are three programs that were written correctly and fell over anyway.

Quicksort, handed a thousand numbers that are already in order, spends 499,500 comparisons where it ordinarily spends 10,986.

A hash table holding five thousand keys in five thousand buckets answers a lookup in about 1.5 probes. Hand it five thousand keys computed by someone who read your hash function, at that same load, and it answers in 2,500.

A search tree built from a sorted list of fifteen keys comes out 14 deep, where 6 is ordinary and 3 is possible.

Three structures, three decades, three separate famous bugs. All three are repaired by the same one move, and everything you need to find it is already in your hands.

01Three disasters, one move — and a third variable nobody has named

Take the tree first, because it is the smallest of the three and the rudest. Insert 1 through 15 in order and every arriving key is larger than everything already there, so it turns right, every time. What you get is a path: fifteen nodes, fourteen edges, and a lookup that walks the lot. (Heights are edges here, not levels.) Shuffle those same fifteen numbers, insert them again, and the tree comes out around 6 deep. Same keys. Same code. So sit the two trees side by side and go hunting for the difference in the keys. Click through all fifteen of them. The widget will refuse to mark anything wrong, because there is nothing wrong to mark.

Failing to find it is the lesson, and the button that admits it out loud is the one marked there is no difference. Press that and the picture changes. A thousand fresh insertion orders on those same fifteen keys, stacked into a histogram of heights: the mass sits at 5 and 6, the mean is 5.84, and holding the bar down for two hundred thousand orders never turns up anything past 13. Two lines are drawn across it. The balanced floor at 3, which is what a perfect fifteen-node tree achieves, and the measured mean beside it. The sorted chain at 14 is not in the right tail of that picture. It is off the right edge, with its probability printed there, because a chain needs every arrival to be the smallest or the largest key still left — that is 2¹⁴ of the 15! possible orders, or about one in eighty million.

Nothing in the keys moved. Nothing in the code moved. The cost moved by a factor of well over two, so something changed, and there is exactly one candidate left: the order the keys arrived in. Arrival order has not been a variable on this course before now. Page 1 made cost a function of how many things you had, page 3 made it a function of what you were allowed to ask about them, and neither left a slot for the sequence they turned up in. A reader who hunts the keys for the difference is not being slow. They are looking in the only two places this course has ever put one.

So take that back to the other two disasters and go find the fixed thing in each. Quicksort's is the pivot rule, and in the version that died it reads take the last element. The hash table's is the hash function — the same twenty lines on every run, on every machine, for every key anybody sends you. The tree's is harder to see, because from the inside it looks like an absence. Nobody wrote a line saying let the arrival order decide the shape. That is precisely what the code does, and it is what got aimed at.

Which means the frame needs one more word before all three of them fit inside it. The thing being aimed at is a rule, and a rule can be a choice you made or a choice you declined to make. Declining is not neutral. It hands the shape of your tree to whoever hands you the keys, and they can read that decision out of your source as easily as they read your pivot rule. Three fixed rules, sitting in three source files, and every one of them is readable.

02Someone reads the rule, and cleverness does not help

Readable is the word that matters, and the person doing the reading is not you. Every worst case in this course so far has been a ceiling — a fact about what the arithmetic permits, not something anyone could walk up to on purpose. A pivot rule is a different kind of object. It sits in a file, in plain language, and the shortest program that hurts you is the one that reads that file and answers it. The inch between rare bad luck and reachable by anyone holding your source is what the rest of this page stands on, so it should not be argued at all. It should simply be handed to you.

Here is a hash function, twenty lines, nothing hidden. Beside it sits a table of 5,000 buckets, and a load factor of exactly 1 that does not move once for the rest of the demonstration. Five thousand random keys spread across it, and a lookup costs 1.49 probes. Then a constructor runs, reading the function on screen as it works, and five thousand crafted keys land in a single bucket. Same table, same load, same twenty lines of code. A lookup now costs 2,500 probes, which is 1,667 times the first reading. The only thing that changed is that somebody read your function before choosing their keys.

The honest reply to that is the one almost everyone reaches for first. Real keys are not crafted, so assume the input is random and analyse the average. That is average-case analysis, and it is not a swindle. It is a true theorem, proved properly, and it is the reason your hash table works on a normal Tuesday. Its full statement carries a clause that usually gets dropped in the telling. If the input is drawn uniformly at random, then the expected cost is such and such — and the theorem is exactly as good as that if.

Now look back at the crafted keys with the clause restored. Nobody drew those keys uniformly at random. Somebody read the function and chose, and the hypothesis the theorem needs was never true for that run at all. So the claim did not become false. It became unusable, which is a different thing and a more uncomfortable one, because an unusable truth still sounds like a defence when you say it out loud. Keep that distinction intact, because most of what this page does later is built on top of it.

The second reflex is stronger, and it is the one this course has spent three pages training. Do not assume anything about the input — be cleverer about the rule. Take the middle element instead of the last one, or the median of three of them. So take the four pivot rules a working programmer actually reaches for, put them behind a selector, and put an attack button next to it. The attacker is not guessing here. It reads whichever rule you have selected, and then builds the permutation that kills that one.

Last element, on input that arrives already ascending: every partition peels off a single element. The run costs 499,500 comparisons — every pair in the array, compared exactly once. First element, same input, same 499,500. Middle needs a constructor that runs the algorithm backwards, answering each comparison so the chosen pivot is always the extreme thing left. It lands on 499,500 too. Median-of-three is the one rule that cannot be driven all the way there. Its pivot is never the smallest or the largest thing left, so every partition has to give up at least one element on each side. The constructor gets it to 250,000. Underneath all four readings the ordinary cost sits at 10,986, and it does not move either. Four clever rules, four kills, and the cleverest of them bought a factor of two against an attacker who was taking a factor of forty-five.

03The fraction, and the one variable nobody touched

So put the two numbers that will not move side by side and divide them. Sort a thousand elements, and the cost someone holding your source file can force is 499,500 comparisons. The cost the same sort actually pays, when nobody is aiming at it, is 10,986. Divide the forced cost by the real one and you get about 45. You are budgeting forty-five times what the work needs. On page 3 you divided what the answer required by what one question returned, and the quotient counted questions. Here both halves are costs, so the quotient is a multiplier, and 1 is perfect. One thing about that second number is worth a pause, because 2n ln n = 13,816 at n = 1000 and that is the shape of the cost rather than the cost itself. The exact count is 2(n+1)H_n − 4n, which evaluates to 10,985.9. The leading term is not the number.

Neither half moves. The forced 499,500 will not come down, because four clever pivot rules just finished proving it: whatever rule you write, someone reads it and rebuilds the input that hurts. The 10,986 will not come down either, because that is what sorting a thousand numbers by comparison costs, and page 3 showed you the floor underneath it. So the fraction is stuck at 45 for as long as they get to choose after you do. Read that last clause again and notice which word carries it: not what they choose, but when. The forced cost was never a fact about your algorithm. It is a fact about the order of play, and the order of play is a variable this course has never once moved.

So move it: take the one choice they were aiming at, and make it after the input has arrived, with a coin they cannot see. In quicksort that is a single line, where pivot = a[hi] becomes pivot = a[rand(lo,hi)], feeding the same partition you already had, and nothing else in the file changes. There is now no sorted input and no killer input, because the ranks the pivots land on no longer depend on the array at all. The attack button from a moment ago is still sitting on screen, and that one line is the entire edit. Press the button again. The meter that stood at 499,500 has stopped answering it.

Now take a reading, because an instrument that never registers a win is decoration. Before the edit, someone who read your file could make you pay 45 times your ordinary cost. After it, the worst they can force out of you, averaged over your own coins, is your ordinary cost. 499,500 over 10,986 was 45. 10,986 over 10,986 is 1. Neither number moved by one comparison. What went away is their ability to choose which of the two you pay, and the price of taking it away was one call to a random-number generator.

Then press run again, on the same sorted array, and something new happens. The meter reads 10,903, then 11,204 on the next press, then 10,850 on the one after that. It will not repeat itself, and no single run of it lands on 10,986. Twenty thousand runs stack into a hill centred on 10,985, with a standard deviation of 641. Most runs land within a few hundred comparisons of the middle, and every reading in the twenty thousand falls between 9,471 and 14,917. The unluckiest of those twenty thousand runs, the worst thing the coin ever did to you, cost 14,917 comparisons. That is 2.99% of the 499,500 an adversary could force before the edit. Your cost has stopped being a number, and what you can promise now is where the spread sits.

04When you cannot shuffle the data — the function, and the stream

That spread came from a coin rolled inside your own sort, and the next disaster will not let you reach the input at all. A hash table's keys are not yours. They arrive from a form, a request header, a file somebody else wrote. You cannot permute them, and you would not be allowed to if you could. So the instruction you have followed twice now looks like it has run out. It has not, and the way to see that is to state the instruction properly: roll a die at the point of the fixed rule. Three cards name the candidates. One of them is the rule that was fixed in this disaster, and it is worth naming before the page names it.

The fixed rule was the hash function, so the hash function is what you draw. Your process picks one at startup, and the 5,000 crafted keys from the earlier attack get replayed against it verbatim. Same table, same m = 5,000 buckets, same α = 1, so nothing about the load has moved. Against the fixed function those keys cost 2,500 probes per lookup. Against a function drawn at startup they cost 1.5 (measured 1.49), and reseeding leaves them there. The keys were computed against a function that no longer exists. To hurt you now, the attacker would have to compute against a function drawn after they submitted. Notice also that this is a different line of code from the pivot fix. The hook promised the same move. It never promised the same line.

The third disaster is worse, because there the input is not even all present. Keys arrive one at a time, from a user, a socket, a log being replayed. You have to place each one in the tree before the next one shows up. There is no moment when the whole array sits in front of you waiting to be permuted. Feed the plain tree the keys 1 to 15 in sorted order and you get the chain 14 deep, one node lower per press, growing in front of you. So ask the same question once more. With the arrival order out of reach, what else is the shape allowed to depend on?

It can depend on the priorities, once you decide the tree has priorities. Give each arriving key a random number at the moment it arrives, and keep the tree ordered two ways at once. By key, left to right, so lookups still work exactly as before. By priority, parent above child, so the shape is decided by the coin. That is a treap, and the rotations that maintain it cost a constant amount per insertion. Watch two panels take the same sorted stream and disagree completely about what to build from it.

Plain tree on 1 to 15 sorted: height 14, every run, no spread at all. Treap on that same sorted stream, 200,000 trials: mean height 5.83, worst ever seen 12. A plain tree handed those keys in random order averages 5.84 — statistically the same tree, which is the whole claim, stated as a measurement rather than a hope. The mechanism deserves a sentence, because none of this is luck. A treap's shape is a function of the priority ranks alone, and building it by decreasing priority reproduces exactly the plain tree for that order. The priorities are drawn uniformly, so that order is uniform whatever order the keys walked in. One honest caveat: this is a result about insertions, and deletions do not preserve it. Nothing about the input moved, and one coin per key was rolled after the key had already arrived. You bought a shuffle you were never allowed to perform.

05The keystone — two claims that carry the same number

Three disasters are fixed and it feels like a good day, so ask what you actually bought. Write the claim you had before the fix beside the claim you have now. Quicksort is fast on average. Randomised quicksort is fast in expectation. Both carry the same shape, and at n = 1000 both carry the same count: about 10,986 comparisons. The second sentence has three extra syllables and not one extra number. If that is the whole difference, you spent a long morning buying a mood.

It is not the whole difference, and the gap is not in the arithmetic. Both are true theorems. What separates them is the thing each one averages over. The average-case claim averages over inputs, drawn uniformly from all the orderings your thousand keys could arrive in. That is a statement about a bag nobody promised to draw from, and the attacker simply did not draw from it. The expectation claim averages over the coins your own code rolled, and it names no distribution over inputs at all. It holds for a sorted array, for a reversed one, and for the array built last week to break you.

The reason is narrower than it sounds, and it lives in one line of the partition you already wrote. The comparison count depends only on the sequence of pivot ranks the coin drew. Draw rank 500 first and the work splits in half; draw rank 1 first and it splits off nothing. The coin draws those ranks uniformly whatever array you were handed, because it draws after the array arrives. So the cost distribution is not merely similar from one input to the next. It is the same distribution.

That is a large claim to take on anyone's word, and fig. 7 will not let you. It prints both sentences, asks what the difference is, and pins your answer in your own handwriting before a single button unlocks. Then it puts you in the attacker's chair against two panels. Panel A holds a fixed pivot rule, and sorted input takes it to 499,500 on your first press — the whole of C(1000,2). Panel B is randomised, and the same inputs cost 10,903, then 11,204, then 10,850. A counter tracks your campaign: after 200 attempts the worst you found is 11,842, against the 499,500 you needed. Then 40,000 sorts of each input at n = 200, drawn on one pair of axes. Sorted input averages 1563.6, random input averages 1562.6, and the formula said 1,563.0 for both.

One thing still drives panel B to its worst case, and the figure hands it to you last. Open the dice box and replace the coin with a rule you choose. Always take the smallest remaining element, and n = 1000 pays the full 499,500 immediately. Guessing the coin was never on offer. Every pivot would have to be extremal, and at n = 1000 that runs below one chance in 10²⁰⁰⁰, though at n = 12 it is 2,048 in 479,001,600 and a search does find it. So the only road left to the worst case ran through the inside of your own program. The worst case stopped being a property of the input and became a property of the coin.

06What the coin does not buy

A property of the coin is still a property, and the worst case has not gone anywhere. You reached it yourself two minutes ago. But look at what that took: you opened the running process and set the dice by hand. Nobody standing outside your program can do that. An attacker holding your source can still read the pivot rule, and reading it now tells them nothing about the ranks that rule will draw. The bad input was never removed. It was moved somewhere the attacker cannot stand.

There is one more input that still hurts, and it is not aimed at your coin at all. It is aimed at a rule you forgot to name, and that rule is what your code does with keys equal to the pivot. Hand a randomised quicksort a thousand identical keys and it pays 499,500 comparisons, which is the full quadratic worst case and forty-five times the 10,986 you were promised. Reseed it and it pays 499,500 again. Twenty runs, twenty identical bars, and the meter never flickers once. Press it yourself before you read why, because the flatness is the whole argument.

The reason is that no key here is less than the pivot and none is greater. Lomuto's test asks whether each key is at most the pivot, and on identical keys the answer is always yes. Everything lands on one side, the subproblem shrinks by exactly one, and the coin has nothing left to decide. So fix the rule rather than the coin. Partition three ways, into less, equal and greater, and the equal block is finished the moment it is formed. One pass, one comparison per element, both recursive sides empty: 999 comparisons, and the sort is over. That is five hundred times cheaper, and it came from an instruction you already had, which was to go and find every rule your code holds fixed.

The coin has a requirement of its own, and nothing on this page has said what it is yet. Nothing can be aimed at a coin is false the moment they can predict the coin. Math.random, rand seeded from the clock, any ordinary non-cryptographic generator: every one of them can be reconstructed from a handful of outputs. Someone who recovers your generator reads your future pivot choices exactly the way they read your pivot rule. A predictable coin is a fixed rule with extra steps.

That is why a real hash table draws its seed from the operating system's entropy source, and never from the clock or the process id. It is the difference between the fix working and the fix merely looking like it works. Everything in this section has been about what a coin will not buy you. It cannot delete the worst case, it cannot name the rules you failed to name, and it cannot survive being predicted. There is one thing it buys outright, though, and that thing is stranger than an average.

Some randomised procedures are built so that one of their two verdicts is never wrong. A primality test that reports composite has found a witness, and a witness is a proof you can check. That verdict is certain, and no run of bad luck can produce it for a prime. Probably prime is the soft side, and you drive its error down by running the test again with fresh coins. Ten runs, a hundred runs, and the soft side's error falls by a factor each time while the hard side stays hard. A coin cannot make every answer certain, but it can make one of the two answers never wrong.

07Universal hashing — a family, and a draw

Certainty like that is built, not hoped for, and the cleanest construction on this page is a hash family. Take h(k) = ((ak + b) mod 17) mod 6, and let a run from 1 to 16 and b from 0 to 16. That is not one hash function. It is 272 of them, and your process draws one of the 272 when it starts. Barring a = 0 is deliberate. Those are the constant functions. (0·k + b) mod 17 is just b whatever key you feed it, so all seventeen keys pile into the single bucket b mod 6. There are seventeen of them, one for each b, and they are exactly what the family leaves out — which is why the count is 272 and not the full grid's 289.

Now fix two keys and ask how many of those 272 functions drop them in the same bucket. The count is 32. It is 32 for the keys 3 and 11, 32 for the keys 0 and 16, and 32 for all 136 pairs you can build from the keys 0 to 16. That is 32/272 = 2/17, or 11.8% of the family, and choosing a different pair does not move it by a single cell. So the honest invitation is the hard one. Pick any two keys you like, read the source before you choose, and go looking for a pair that does worse.

Then read the same grid the other way, one cell at a time. A cell is one real function, the one your process happened to draw at startup, and it has colliding keys in abundance. Under any single cell the seventeen keys land in buckets of size 3, 3, 3, 3, 3 and 2, which is 16 colliding pairs out of 136. Sixteen, for every cell in the grid, and 16/136 is that same 2/17. Set a one-cell family beside it and the counting is identical, except that the attacker now picks the keys after seeing which function you shipped. Their fraction is not 2/17. It is 1.

That is what the draw buys, and it is worth stating in the form you will actually use. Draw h from the family, and the expected number of keys colliding with a given key x is n/m, the load factor α that page 3 already handed you. On the table from earlier, five thousand keys in five thousand buckets, that is α = 1: one other key expected on your chain, and 1.5 probes to walk it. It holds for every x, for every set of keys, and for keys an attacker picked after reading your code. Universal was never a compliment paid to a good function. It names a set and a draw. The property belongs to the grid, and no single cell in it has the property at all.

08The bill — whose dice, and how to count with them

Now notice what that promise cost you to state. The old claim needed no arithmetic at all. Fast on random inputs is something you can say before you have counted anything, because a bag of inputs is doing the work and nobody audits the bag. The new claim has no bag in it. It is a statement about a coin you rolled yourself, and the only way to say what that coin pays is to compute it. You swapped a promise you could state for one you must compute. That is the bill, and it is due now. If you cannot compute it, you have traded a lie for a shrug, and this page opened with a number nobody has yet earned: 10,986 comparisons, against the 499,500 an adversary used to be able to force.

Before any of that arithmetic starts, say whose dice these are. Sometimes they are yours, drawn inside your own code, and sometimes they belong to the world and you are only describing it. The arithmetic is identical either way. What changes is what you are allowed to conclude at the end of it. Roll your own dice and the answer is a promise, good on every input, including the one built to break you. Describe the world's dice and the answer is a description, useful, and exactly as true as the description was. Every count from here on carries a label saying which of the two it is.

Here is a count worth wanting a tool for. You interview a million people in random order and you promote whoever is the best you have seen so far. How many promotions do you hand out? Write a number down before you read on, because the guess is the whole point. Almost everyone writes thousands. The honest answer is about 14. And the direct route to it — a walk over every ordering of a million people — is not a route at all.

The route that works starts by refusing to count the total. Give every occasion a lamp — one per arrival, one per pair, one per whatever it is you are counting — worth 1 when the thing you care about happens there and 0 when it does not. A lamp's average is just the chance it lights, since one times that chance, plus zero times all the rest, is the chance itself. So the expected total is a sum of probabilities, one per lamp, and each of those is small enough to answer on its own. Ten lamps at even odds carry the shape in one line: ten times one half is 5 (ten easy questions, one total). One hard count has become many trivial ones.

You are owed a reason for that, because you have been taught that probability arithmetic needs independence, and lamps like these are rarely independent. Start with the identity. On any single trial the total is the sum of that trial's lamps, which is true by looking rather than by theory. Now average both sides over a hundred thousand trials. Averaging a column of sums is the same as summing the column averages, because addition does not care what order you do it in. Independence is the licence to multiply, the thing that turns the chance of A and B into one chance times the other. Nothing above was multiplied.

Ten lamps sit in the next figure under a switch that wires them together in pairs, and the wiring is an anti-copy: lamp 4 lights exactly when lamp 3 goes dark. Both stay at one half, so the probability column never twitches, and the wired pair now sums to exactly 1 on every single trial. Wire all five pairs and the running average holds at 5 while the spread of the total falls from 1.581 to 0. Watch that happen once and the belief you arrived with comes apart in the right place. Dependence changes how tightly the count clusters, and it never moves where the count sits.

09Records, and the number this page opened with

So take the lamps to those million interviews, because fourteen is not a number you could have reached any other way. Here is the entire argument, and there is no combinatorics anywhere in it. The i-th person to walk in leads the field exactly when they are the largest of the i you have seen so far. Those i people arrived in some order, and every order is as likely as any other. So the chance the largest of them came last is one in i. Add that chance over the whole stream and you get the harmonic staircase, which at a million arrivals sums to 14.39. Run the stream and watch the promotions counter. It fires about three times in the first ten candidates, twice more by the hundredth, twice more again by the thousandth. That is roughly one more promotion every time the stream gets ten times longer, all the way out to a million.

Before you spend that number, say whose dice made it. The interview story is a description, true only if the arrival order really is random, and nobody at the door promised you that. The identical 1/i on a thousand-element array you shuffled yourself is a promise. You wrote that shuffle, and you can run it a hundred thousand times to check it. Same arithmetic, different category — and the hat on the panel says which one you are wearing. Now keep the crank and change the question.

The staircase answered which of the first i arrivals is the largest? Ask instead which of these gets picked first? Take two elements whose ranks in the sorted answer are i and j. Quicksort compares them only if one of those two is the first of the block between them to be chosen as a pivot. Pick anything else in that block and it lands between them, splitting them into different subarrays, and they never meet again. The block holds j−i+1 elements, and each is equally likely to be drawn first. Exactly two of them are ours, so the probability is 2/(j−i+1). Ranks 4 and 9 sit in a block of six, so they get compared 2/6 of the time, which is a third. Neighbouring ranks 4 and 5 sit in a block of two, so they get compared 2/2 of the time. That is always. One of the two has to be the pivot that separates them. Drag the two markers apart along the rank line and watch that fraction thin out as the block between them grows.

Now add it up over every pair, which is the bill this page ran up the moment it printed its opening number. There are n−d+1 pairs at distance d, so the whole count is 2(n−d+1)/d summed over every distance from 2 to n. That collapses to the closed form 2(n+1)H_n − 4n, which you have now derived rather than been handed. At n = 1000, H₁₀₀₀ is 7.4854709. The first term is 2 × 1001 × 7.4854709 = 14,985.91, and 4,000 comes straight off it. That sum is 10,985.9, which is the number this page opened with and the number the simulator prints.

10The instrument — an expected count, and a threshold read off it

One expected count just bought a whole result, and the same expected count also buys thresholds. Write E for how many times some thing happens. When the occurrences are spread thin, the chance it never happens at all is about e^−E. Set E to 1 and the thing happens 63% of the time (1 − e⁻¹ = 0.6321). Set E to ln 2, which is 0.6931, and you are at exactly half. Set E to 3 and you are at 95% (1 − e⁻³ = 0.9502). That is not a folk rule that lands near the answer. It is a dial, and the number you set on it is the percentile you asked for.

The two directions of that reading are not equally strong, and leaving them level would be dishonest. Downward is exact and free. P(X ≥ 1) ≤ E[X] holds for any count, with no assumption at all, because a count that ever reaches 1 contributes at least 1 to its own average. So an expected count of 0.01 is a proof, not a hope: the thing happens at most 1% of the time. An E far below 1 is not weak evidence of absence. It is absence, near enough to ship.

Upward is the direction that can betray you, and it is the one that needs the occurrences spread thin. A large E does not prove the thing happens, because all of the mass can sit in a single rare enormous clump. Take a count that equals 1,000,000 with probability one in a million, and 0 the rest of the time. Its expected value is exactly 1, and it reaches 1 about once in a million tries, not 63%. The smell that should stop you is this: if one occurrence makes many more of them nearly certain, the crank is lying. And notice which way it lies, because it is the unsafe way. The naive count says a collision needs more items than it really does. Size an ID space or a hash width that way and you under-provision.

Three named settings on one curve is a thing to keep under your finger, not in a paragraph. So pick something to count — pairs of people, run starts, empty bins — and drag the parameter until the expected count reads what you chose. The curve for P(at least one) = 1 − e^−E carries your own E as a marker, with ln 2, 1 and 3 pinned permanently. Beside it sits a switch that loads every occurrence into one rare enormous event, and you can watch the upward reading fail while the downward one holds. Everything after this is the same crank turned on a different count. Write the count, set it to one, and read the percentile you want straight off the curve.

11Three turns of the same crank

Turn the crank on pairs first. A room fills up one person at a time. How many have to walk in before there is an even chance that two of them share a birthday? Write the number down, and write down the other one too — the number it takes before somebody shares yours. Almost nobody gets either. These are the world's dice and not yours, so what comes out is a description rather than a promise, but the count is still the count. Each pair is one chance at a match, and each match lands with probability 1/365. With k people there are C(k,2) pairs, so the expected number of matching pairs is k(k−1)/730. Set that to ln 2, which is 0.693, and the crank asks for k(k−1) = 506. That is 23 × 22 exactly, and the true probability at 23 people is 0.5073.

Now set the same count to 1 instead, because the crank has a second reading and that one is honest too. The condition becomes k(k−1) = 730. The pair 27 × 26 gives 702, which falls short, and 28 × 27 gives 756, which clears it. So k = 28, and the true probability there is 0.6545. That is the 63% point, landing exactly where e^(−E) said it would land. An instrument that predicts its own offset is an instrument. A folk rule that happens to come out near 23 is not.

There is still an objection sitting in your chest, and it deserves an answer rather than an overrule. What are the odds that someone shares MY birthday? For that question about 1/365 per person really is the right arithmetic, and the answer is 253 people, because 1 − (364/365)^k reaches a half at k = 252.65. The gut was answering a well-posed question correctly. It was answering a different question. Yours is you against everybody else, which is k chances. The famous one is every pair in the room, which is k(k−1)/2 chances. So run both counters side by side, put the two numbers you wrote down beside them, and watch each counter cross a half at its own moment.

Second turn of the crank, on a count that clumps. A thousand fair flips — the world's dice again, so a description again — and the longest run of heads inside them. Guess the length before you read the next line. Heads only, and pin that convention, because counting either symbol doubles the count and moves the answer by one. A run of length k can begin at 1000 − k + 1 places, each with probability 1/2^k. Turn the dial until the expected count reaches 1: at k = 9 it reads 1.938, and at k = 10 it reads 0.968. The crank answers 10, and it is one too high — the true answer is 9, by mode and by median both. The overshoot is what this turn is for.

Then flip forty thousand times and look. The mode is 9, the median is 9, the mean is 9.31. The crank overshot by one, and it warned you in advance which way it would fail, because the naive count clumps. A single run of 12 contains three different starting positions for a run of 10, so one streak gets counted three times and the tally reports more streaks than exist. That is easier to believe when the three overlapping starts are lit up inside one long run in front of you. Then one press counts maximal runs instead, insisting on a tail immediately after. That halves every count, and it slides the prediction onto the measurement. At k = 9 the halved count is 0.970, and 1 − e^(−0.970) = 0.621 against a measured 0.626. At k = 10 it is 0.484, giving 0.384 against 0.388. Two decimal places, out of a count you wrote in one line. Carry the repaired numbers, not the naive ones: a run of 20 somewhere in a thousand flips is about 1 in 2,100, and a run of 30 is about 1 in 2.2 million. Streaks are not evidence of anything until you have counted the chances.

Third turn, and the fractions inside it are ones you have already climbed. Fifty coupons, one at random in every packet, and you want the whole set. The world's dice once more, and the description is only as true as the claim that the packets really are filled at random. Once you hold i − 1 of them, the next packet is new with probability (50 − i + 1)/50, so that stage costs 50/(51 − i) packets on average. The stages read 50/50, then 50/49, then 50/48, and on down to 50/1. Add them. That is 50 × H₅₀, and H₅₀ = 4.499205, so the total is 225.0 packets, against a simulation that prints 225.1.

The crank's own answer here is b ln b, which is 50 × 3.912 = 195.6, and it missed by 29.4. That miss has a name. H_b = ln b + γ + 1/(2b). So 50 × H₅₀ breaks into 195.60 + 28.86 + 0.50, and γ × 50 = 28.86 is almost the whole gap. The crank found the scale; the exact sum found the number. And those fifty fractions are the records staircase, walked from the far end: 1/1, 1/2, 1/3 climbing one way, and 50/50, 50/49, on to 50/1 climbing back the other. Draw the bars once, flip the label, and drag a marker along the stages. Let the smooth b ln b curve lie over them, with the sliver between shaded and measured. One staircase, read from both ends, and both readings were the same climb.

12The shuffle you were told to write

There is one die on this page you were never made to write yourself. Shuffle the array before you sort it: seven words, and every reader nods straight past them. So go and write it, because here are the four shuffles people actually reach for, and three of them are broken. Nothing on this page so far has suggested that a shuffle is a thing you can get wrong.

The trouble is not that the bug is subtle. It is that no observation of shuffled output ever reveals it. A broken shuffle deals out lists that look exactly as shuffled as a correct one's. These are the only dice on the page that are yours, which is exactly why you are allowed to run them a hundred thousand times and count. So run the test you would have run anyway: deal a three-element array a hundred thousand times and check that every element lands in every position about a third of the time. Random rotation passes that test perfectly, and it is the shuffle that should worry you most. All nine of its element-position counts sit at exactly 1/3, and rotation can only ever produce three of the six orderings. Run the flat histogram yourself in the next figure, then watch the view switch and three bars sit at zero.

Those are not the same claim, and the arithmetic says how far apart they are. Uniform per item is nine numbers for n = 3, one for each element-position pair. A uniform shuffle is six numbers, one for each ordering the array can end up in. Nine constraints satisfied do not deliver the six — rotation is the proof, standing right there. Count whole orderings instead, and the four algorithms separate from each other at once. Fisher-Yates has six execution paths and puts exactly one of them into each ordering. Swap-with-anywhere lands 4, 5, 5, 5, 4 and 4 out of twenty-seven. Rotation lands 1, 0, 0, 1, 1, 0 out of three, and swap-with-strictly-later leaves four orderings empty.

And none of that verdict needed a hundred thousand runs behind it. Swap-with-anywhere draws a fresh random index for each of the three positions (3 × 3 × 3), so it has 27 equally likely execution paths. Those 27 paths have to land in 6 orderings. 27 ÷ 6 = 4.5, and no ordering can be handed half a path, so the bars are stuck being uneven before a single run happens. They come out 4, 5, 5, 5, 4, 4, which is exactly what a hundred thousand runs will measure for you. That is the whole check, and there is no probability anywhere in it. Twenty-seven paths cannot divide evenly into six orderings, and no amount of staring at the output would have said so.

13A search tree is a frozen quicksort recursion tree

That was a count of paths. Here is a count of comparisons, and it says the page's first disaster and its third one are not similar — they are the same object. Take one permutation and hand it to both of them. Quicksort with a first-element pivot takes that permutation's opening value and compares every other element against it. A search tree fed the same permutation makes that opening value the root, and compares every later arrival against it. Both then send the smaller elements one way and the larger elements the other. In the left block, quicksort's next pivot is the first survivor it meets, and that same element is the first key to arrive in the left subtree. Run that down every level and nothing ever diverges. So the two comparison sets are not similar sets. They are the same set, element for element.

That is a claim you should refuse to take on my word, so it gets tested on a permutation you generate yourself. Quicksort partitions on the left, the tree grows on the right, and every comparison flashes in both panels at the same instant. Two counters climb beside them. Before you press step, answer the question the panels are actually asking: will those two numbers ever disagree? One awkward thing has to be said before they run. The demo pivots on the first element, which is the exact rule that got killed on screen earlier with an attack button. It is there because the identity is what is being shown, not because anyone should ship it. At n = 200 the counters settle near 1,563.0 the value of 2(n+1)H_n − 4n there, and whatever number a given permutation produces, both panels print it. Not close. The same integer.

Once the two are one object, every result you already own crosses over for nothing. The pair rule said that ranks i and j get compared with probability 2/(j − i + 1), because exactly two of the j − i + 1 elements between them are the ones you care about. In the tree that same probability is a statement about ancestry: two keys are compared precisely when one of them is an ancestor of the other. Sum it and you have expected depth, with no new argument written. One honest limit belongs here. The expected-height result covers insertions only, and deletions do not preserve it. Randomising the pivot and randomising the arrival order are one act, which is why the treap was never a trick.

14You cannot see the future either

Every fix so far has answered the same complaint: somebody else chose the input. Here is a problem with no attacker anywhere in it. You interview one candidate a day, you can rank everyone you have seen so far, and you must hire or reject on the spot. Nobody is being hostile. You simply cannot see the people who have not walked in yet. There is no fixed rule to randomise here, because the thing you are missing is not a distribution over inputs. It is the future.

So what do you do with a hundred candidates and no foresight? Look at the first k and hire nobody, whatever they are. Then take the first one who beats everything in that window. The window is not wasted, it is calibration, and what you are buying with it is a bar. The arithmetic that prices the bar is the harmonic staircase turning up a third time. You win when the best candidate stands at position i and the best of the first i−1 fell inside your window, which gives P(k) = (k/n)·Σ_i>k 1/(i−1). At n = 100 that peaks at k = 37, where you land the best candidate 37.1% of the time, and n/e = 36.79 sits right beside it. One honest label before you use it: the random arrival order is a description of a world nobody guaranteed you, not a promise you wrote yourself.

A closed form tells you where the peak is and hides the one thing you would actually act on, which is how sharp it is. So drag k from 1 to 99 yourself, with the same ten thousand permutations scored at every setting and the exact curve drawn underneath for the simulated dots to land on. Reject 30 and you succeed 36.5% of the time. Reject 45 and you succeed 36.2%. The peak at 37.1% is barely a peak. Being wrong about k by a fifth of its value — anywhere from 30 to 44 — costs you under one percentage point, and even a third off, at 25 or 49, costs you about two. Which is the sentence no formula says out loud and a slider says in two seconds.

Now a problem where the future costs money instead of candidates. Skis rent for one unit a day, or you buy a pair outright for the price of b = 100 rental days. The season might end tomorrow or run all winter, and nobody will tell you which. There is no distribution here you would trust for a moment, and averaging over imagined seasons is describing a world you cannot audit. So change the other thing. Change what you measure yourself against: a rival who knew the length of the season before it started.

Rent for 99 days, then buy on day 100. If the season ends on any day d at or under 99, you paid d and the rival paid d, so the ratio is 1. If it reaches day 100 or beyond, you paid 99 + 100 = 199 and the rival paid 100, so the ratio is 1.99. That is the worst any season length can do to you, and the proof is one line. You never spend more than 99 + 100, and the rival never spends less than 100 once the season reaches day 100. Then roll this page's own die one last time. Randomise which day you switch, and the worst expected ratio falls from 1.99 to e/(e−1) = 1.582.

Go and set the season length yourself. Hunt for the day count that hurts most, watch the two cost bars fill, then switch the coin on and hunt again. What sits between those bars is this page's fraction in a third grammar: your cost on top, an omniscient rival's underneath, and 1 meaning perfect. The whole game is how far above 1 you can be forced. Sometimes a coin pulls that multiplier down hard, as it just did from 1.99 to 1.582, and sometimes there is nothing useful to roll. The denominator does not care which. When there is no coin worth rolling, you can still name a rival who saw what was coming.

15What a verdict is worth, and the lever you are taking away

One last verdict to price, and this time the verdict comes out of a medical test. A condition affects one person in a million, and the test is right 99 times in 100 in both directions. The world's dice again, so the answer will be a description, and it is only ever as true as those two rates are. It fires for 99 of every 100 people who have the condition, and stays quiet for 99 of every 100 who do not. Your result comes back positive. Before you read on, write down how likely that positive is to be true. A percentage, in your own handwriting. A million people drawn as a field of grey dots, with nothing lit yet, is the place to hold that number while it gets tested.

The trouble with 99% is that it is a rate, and a rate has to be applied to each group separately. One person in that field has the condition, and the test fires for them 99 times in 100. So the expected count of true positives is 0.99. It also fires for one healthy person in every hundred, and there are 999,999 of those. That is 9,999.99 false positives, so call it ten thousand. Ten thousand alarms are going off in that field — and exactly one of them is ringing for a reason. Your chance of being that one is 0.99 divided by 10,000.98, which comes to 1 in 10,102.

Nothing new was needed to get there. You wrote an expected count for one group, wrote another for the other group, and compared them. That is the same crank you turned on pairs, on run-starts and on coupon stages. What it exposes is that accuracy says nothing about how rare the condition is. So accuracy alone cannot tell you what a firing is worth. A verdict is worth the prior it beats — which is why a one-sided verdict is such a good thing to own. When one of the two answers is never wrong, that answer beats any prior you like, and you can act on it the moment you see it.

The same care buys you something concrete in the dictionary your language ships. Feed a modern interpreter a set of keys chosen to collide, and a table that promised constant lookups degrades into a list. That is a real and named class of denial-of-service bug, and the fix is the one this page has been making all along. The hash function is drawn fresh when the process starts, so there is no fixed rule left for an outsider to aim at. The seed comes from the operating system's entropy pool rather than the clock, because a clock is a thing your attacker can read too.

So add page 4's lever to the running list. Page 1 moved the numerator by choosing a cheaper method, and page 2 moved it again by rearranging, sharing, skipping and postponing. Page 3 moved both halves, by asking for less or by widening the channel. Here the forced cost was 499,500 comparisons and the honest cost was 10,986, a ratio of about 45. No amount of cleverness shifted either number. What turned the 45 into a 1 was rolling your own die after the input had arrived. Page 4 is the one page where neither half moves, so what you move is the order of play.