{ "cells": [ { "cell_type": "markdown", "id": "27f146d5", "metadata": {}, "source": [ "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/MeiraDavidson/compute_module1/blob/main/notebooks/lab_07_the_honest_die.ipynb)\n\n", "# Lab 7: The Honest Die\n", "\n", "*From* **A First Taste of Algorithms — and the Machines That Learn** *(The Curious Family Library). A computational lab: run the cells in order. A few labs end with a deliberately broken “Break it” cell — that one is meant to fail, and seeing how is the point.*" ] }, { "cell_type": "markdown", "id": "614458c8", "metadata": {}, "source": [ "*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.*\n", "\n", "## 1. The die\n", "\n", "Python's randomness lives in the `random` module. Four moves, each with its debt paid immediately:" ] }, { "cell_type": "code", "execution_count": null, "id": "ad3a02b4", "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "print(random.randrange(6)) # a fair choice from 0,1,2,3,4,5\n", "print(random.choice([\"heads\", \"tails\"]))\n", "items = [1, 2, 3, 4, 5]\n", "random.shuffle(items) # an honest shuffle, in place\n", "print(items)" ] }, { "cell_type": "markdown", "id": "2c892ced", "metadata": {}, "source": [ "First experiment: a die's expected roll is 3.5 — a number the die never shows. Watch the long run converge on it:" ] }, { "cell_type": "code", "execution_count": null, "id": "ae04d10f", "metadata": {}, "outputs": [], "source": [ "total = 0\n", "for count in [10, 100, 1000, 10000, 100000]:\n", " total = 0\n", " for _ in range(count):\n", " total = total + random.randrange(1, 7)\n", " print(count, \"rolls, average:\", total / count)" ] }, { "cell_type": "markdown", "id": "74b45cb7", "metadata": {}, "source": [ "(`_` 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.\n", "\n", "## 2. The hat-check, simulated\n", "\n", "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:" ] }, { "cell_type": "code", "execution_count": null, "id": "cb1fe0bf", "metadata": {}, "outputs": [], "source": [ "def lucky_people(n):\n", " hats = list(range(n))\n", " random.shuffle(hats)\n", " lucky = 0\n", " for person in range(n):\n", " if hats[person] == person:\n", " lucky = lucky + 1\n", " return lucky\n", "\n", "for n in [3, 10, 100, 1000]:\n", " total = 0\n", " for _ in range(10000):\n", " total = total + lucky_people(n)\n", " print(n, \"people, average lucky:\", total / 10000)" ] }, { "cell_type": "markdown", "id": "e36a65d6", "metadata": {}, "source": [ "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.)\n", "\n", "## 3. The adversary's kill, then the coins' rescue\n", "\n", "Quicksort with the *predictable* rule — first item as pivot — and a comparison counter riding along:" ] }, { "cell_type": "code", "execution_count": null, "id": "9d5ace3a", "metadata": {}, "outputs": [], "source": [ "def quicksort_first(items):\n", " if len(items) <= 1:\n", " return [items, 0]\n", " pivot = items[0]\n", " smaller = []\n", " bigger = []\n", " for x in items[1:]: # items[1:]: everything after the pivot\n", " if x < pivot:\n", " smaller.append(x)\n", " else:\n", " bigger.append(x)\n", " left = quicksort_first(smaller)\n", " right = quicksort_first(bigger)\n", " return [left[0] + [pivot] + right[0], left[1] + right[1] + len(items) - 1]\n", "\n", "shuffled = list(range(200))\n", "random.shuffle(shuffled)\n", "print(\"shuffled input:\", quicksort_first(shuffled)[1], \"comparisons\")" ] }, { "cell_type": "markdown", "id": "7db7ab4b", "metadata": {}, "source": [ "On shuffled input: respectable, n log n-ish. Now be the adversary — you know the rule, so supply the killer:" ] }, { "cell_type": "code", "execution_count": null, "id": "1a30f25e", "metadata": {}, "outputs": [], "source": [ "print(\"sorted input:\", quicksort_first(list(range(200)))[1], \"comparisons\")" ] }, { "cell_type": "markdown", "id": "33200ee3", "metadata": {}, "source": [ "Quadratic: 19,900 = 200·199/2, the full bill, on the most innocent input there is. Then push the adversary's advantage to its conclusion: try `list(range(5000))` and read the error to its last line — Lab 3's old enemy, because the lopsided recursion is n deep. The adversary didn't just slow your algorithm; it *crashed* it, with sorted data.\n", "\n", "The rescue is one line — the pivot by coin:" ] }, { "cell_type": "code", "execution_count": null, "id": "db3a8d0d", "metadata": {}, "outputs": [], "source": [ "def quicksort_random(items):\n", " if len(items) <= 1:\n", " return [items, 0]\n", " pivot = random.choice(items)\n", " smaller = []\n", " bigger = []\n", " for x in items:\n", " if x < pivot:\n", " smaller.append(x)\n", " elif x > pivot:\n", " bigger.append(x) # equal-to-pivot items sit out: they're placed\n", " left = quicksort_random(smaller)\n", " right = quicksort_random(bigger)\n", " return [left[0] + [pivot] + right[0], left[1] + right[1] + len(items) - 1]\n", "\n", "print(quicksort_random(list(range(5000)))[1], \"comparisons on the killer input\")" ] }, { "cell_type": "markdown", "id": "a7ae1c9d", "metadata": {}, "source": [ "The input that crashed the predictable version is now unremarkable. Run that cell five times: five *different* comparison counts, all in the same healthy neighborhood. The cost has become a random quantity — which is exactly why the next section needs a new instrument.\n", "\n", "## 4. The distribution, drawn\n", "\n", "A random cost is not one number; it is a *shape*, and the instrument for shapes is the **histogram**: chop the number line into bins, count how many runs land in each, draw the counts as bars. One new plotting move, `plt.hist`:" ] }, { "cell_type": "code", "execution_count": null, "id": "0d1fff3f", "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "\n", "n = 256\n", "counts = []\n", "for _ in range(2000):\n", " counts.append(quicksort_random(list(range(n)))[1])\n", "\n", "mean = sum(counts) / len(counts)\n", "print(\"mean:\", round(mean, 1), \" smallest:\", min(counts), \" largest:\", max(counts))\n", "\n", "plt.hist(counts, bins=40)\n", "plt.xlabel(\"comparisons (n = 256)\")\n", "plt.ylabel(\"how many of the 2000 runs\")\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "86f37376", "metadata": {}, "source": [ "Read your hill. The mean sits near 2,125 — the deep water's exact 2(n+1)Hₙ − 4n, *not* the asymptotic slogan 2n ln n ≈ 2,839; check both against your printout and note which one your data votes for. Then the question the picture answers and the mean cannot: where is the worst case? It is n(n−1)/2 = 32,640 — find the largest of your 2,000 runs and see how breathtakingly far short of the cliff even your *unluckiest* run fell. Two thousand genuine gambles, and the catastrophe wasn't merely avoided; it was never in the room. That concentration — not the average alone — is what the chapter meant by trusting the gamble.\n", "\n", "## 5. The birthday machine\n", "\n", "The chapter claims 23 people make a shared birthday more likely than not. Exact arithmetic first:" ] }, { "cell_type": "code", "execution_count": null, "id": "d2759596", "metadata": {}, "outputs": [], "source": [ "def p_shared(k):\n", " q = 1.0\n", " for i in range(k):\n", " q = q * (365 - i) / 365\n", " return 1 - q\n", "\n", "for k in [5, 10, 23, 50]:\n", " print(k, \"people:\", round(p_shared(k), 4))" ] }, { "cell_type": "markdown", "id": "662f4bb0", "metadata": {}, "source": [ "There it is: 0.5073 at 23. But this lab's standard is belief through simulation — so build the room:" ] }, { "cell_type": "code", "execution_count": null, "id": "eb1e315e", "metadata": {}, "outputs": [], "source": [ "def room_has_collision(k):\n", " seen = set()\n", " for _ in range(k):\n", " day = random.randrange(365)\n", " if day in seen:\n", " return True\n", " seen.add(day)\n", " return False\n", "\n", "for k in [10, 23, 50]:\n", " hits = 0\n", " for _ in range(10000):\n", " if room_has_collision(k):\n", " hits = hits + 1\n", " print(k, \"people: shared birthday in\", hits, \"of 10000 rooms\")" ] }, { "cell_type": "markdown", "id": "292ca88b", "metadata": {}, "source": [ "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.)\n", "\n", "## Break it\n", "\n", "Predict first. Run second. Explain any gap third.\n", "\n", "**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?\n", "\n", "**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.)\n", "\n", "**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).\n", "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).\n", "Then the surprise: pivot = the **median of three** random picks (draw three with `random.choice`, take the middle one — two `if`s 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.\n", "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.)\n", "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.\n", "\n", "**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.\n", "\n", "\n", "\n", "
" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }