A First Taste of Algorithms · Lab 7: The Honest Die

5. The birthday machine

The chapter claims 23 people make a shared birthday more likely than not. Exact arithmetic first:

def p_shared(k):
    q = 1.0
    for i in range(k):
        q = q * (365 - i) / 365
    return 1 - q

for k in [5, 10, 23, 50]:
    print(k, "people:", round(p_shared(k), 4))

There it is: 0.5073 at 23. But this lab’s standard is belief through simulation — so build the room:

def room_has_collision(k):
    seen = set()
    for _ in range(k):
        day = random.randrange(365)
        if day in seen:
            return True
        seen.add(day)
    return False

for k in [10, 23, 50]:
    hits = 0
    for _ in range(10000):
        if room_has_collision(k):
            hits = hits + 1
    print(k, "people: shared birthday in", hits, "of 10000 rooms")

Ten thousand rooms of 23, and right around 5,073 of them have the coincidence — exact formula and honest die agreeing to three figures. (The seen set doing collision-detection here is a hash table detecting hash collisions — the lab is quietly eating its own cooking.)

Break it

Predict first. Run second. Explain any gap third.

1. The seed. Add random.seed(42) at the top of a cell, run §4’s histogram experiment with only 20 runs, and print the 20 counts. Now rerun the identical cell. Predict before the rerun: same 20 “random” numbers, or different? The result tells you what the word pseudo is doing in “pseudo-random” — state it plainly. Then the consequence, which Problem 3.2 weaponizes: if randomness is reproducible by anyone who knows the seed, what has happened, exactly, to the chapter’s claim that “the coins do not read lists”? When is reproducibility a virtue (think: this book’s figures, science itself) and when is it a vulnerability?

2. The biased die. Build a crooked die: random.choice([1, 2, 3, 4, 5, 6, 6]) — the six appears twice in the list. Predict its expected roll exactly (it’s a weighted average; compute before running), then detect the bias by simulation: how many rolls did you need before the empirical average stood clearly apart from 3.5? A casual glance at twenty rolls would never catch it; state in one sentence what the long run does to small dishonesties. (Casinos, auditors, and particle physicists all live by your sentence.)

3. Rigged dice, both directions. In quicksort_random, replace the honest coin with two rigged ones and measure each against §4’s baseline (400 runs suffice). First the saboteur: pivot = the minimum of five random picks — a die heavily biased toward terrible pivots. Predict the hill’s move, then measure (the chapter’s wisdom says lopsided splits cost; expect the mean up by roughly a quarter and the worst runs worse). Then the surprise: pivot = the median of three random picks (draw three with random.choice, take the middle one — two ifs will do it). Predict first; then watch the hill land left of the honest die’s, around 13% cheaper. Real libraries ship exactly this rig (“median-of-three”); you have just rediscovered why. Now the question both rigs were for: if unfair coins can beat fair ones, what were the fair coins ever for? Answer precisely — what property do the honest die and the median-of-three rig share that pivot = items[0] lacks, and which §3 catastrophe does that property, alone, rule out? (Hint: it is a sentence about the adversary, not about speed. A rigged die the adversary cannot read is still a die.) One curiosity to keep, free of charge: a mild low-bias rig — minimum of just two picks — measurably doesn’t hurt the mean at all; if you have the patience, confirm it, and notice you have reached the edge of what this chapter’s tools explain. The full account needs integrals this book doesn’t assume. Edges are good places to know the location of.

4. Certainty returns. Run the birthday simulation at k = 366. Predict the count out of 10,000 rooms before running — and predict what kind of fact your prediction is. The chapter’s Problem 3.5 distinguishes two species of theorem; after this cell you will have simulated one species and proved the other, and you should be able to say which is which in one sentence each.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses