A First Taste of Algorithms

Lab 7: The Honest Die

✦ ✦ ✦

Accompanies Chapter 7. One instrument arrives — manufactured randomness — and with it the chapter’s whole case gets tested on your machine: the adversary kills the predictable quicksort in front of you, the coins rescue it, two thousand runs pour into your first histogram, and the birthday paradox is simulated until belief arrives. Throughout, one discipline: predict the average before the die rolls.

1. The die

Python’s randomness lives in the random module. Four moves, each with its debt paid immediately:

import random

print(random.randrange(6))        # a fair choice from 0,1,2,3,4,5
print(random.choice(["heads", "tails"]))
items = [1, 2, 3, 4, 5]
random.shuffle(items)             # an honest shuffle, in place
print(items)

First experiment: a die’s expected roll is 3.5 — a number the die never shows. Watch the long run converge on it:

total = 0
for count in [10, 100, 1000, 10000, 100000]:
    total = 0
    for _ in range(count):
        total = total + random.randrange(1, 7)
    print(count, "rolls, average:", total / count)

(_ is the polite name for a loop variable nobody uses.) Read the column: wobbly at 10, respectable at 1,000, locked on at 100,000. The expectation is not a prophecy about one roll; it is a contract about many — and you have just watched the contract enforce itself. The enforcement has a name, the law of large numbers, and this little loop is the only proof of it most working scientists ever need.

2. The hat-check, simulated

The chapter priced the hat-check at exactly 1 lucky person, for any n, by linearity. Audit the claim — a random return of hats is a shuffle:

def lucky_people(n):
    hats = list(range(n))
    random.shuffle(hats)
    lucky = 0
    for person in range(n):
        if hats[person] == person:
            lucky = lucky + 1
    return lucky

for n in [3, 10, 100, 1000]:
    total = 0
    for _ in range(10000):
        total = total + lucky_people(n)
    print(n, "people, average lucky:", total / 10000)

Four sizes, one answer, hovering at 1.0 — the n-independence that looked too clean on paper, holding in the wild. (Run it twice; the third decimal changes. Hold that thought for §5.)

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