← The birthday surprise: can your class find a match?

experiment.py

Python · 179 lines · Download raw ·

1"""
2The birthday surprise: in a class of k kids, how likely is it that at least
3two share a birthday?
4
5We check it two ways:
6
7 1. Simulation: make one million pretend classes of each size, give every
8 kid a random birthday (365 days, all equally likely, no leap years),
9 and count the classes with a shared birthday.
10 2. Exact maths: 1 - (365/365) * (364/365) * ... * ((365-k+1)/365).
11
12Outputs:
13 results.csv one row per class size: simulated chance, exact chance, difference
14 chance.png chance of a shared birthday vs. class size
15 ten-classes.png ten simulated classes of 23 kids on calendar strips
16
17The last line printed is a JSON summary of the headline numbers.
18
19Run:
20 python3 experiment.py
21"""
22
23import csv
24import json
25import time
26
27import matplotlib
28import numpy as np
29
30matplotlib.use("Agg") # draw to a file, no window needed
31import matplotlib.pyplot as plt
32
33# ---------------------------------------------------------------------------
34# Settings
35# ---------------------------------------------------------------------------
36
37DAYS = 365
38CLASS_SIZES = list(range(2, 81)) # classes of 2 up to 80 kids
39CLASSES_PER_SIZE = 1_000_000 # pretend classes for each size
40BATCH = 100_000 # classes simulated at once (memory limit)
41SEED = 2026
42
43
44# ---------------------------------------------------------------------------
45# Building blocks
46# ---------------------------------------------------------------------------
47
48def exact_chance(k):
49 """Exact chance that at least two of k kids share a birthday.
50
51 Kid 1 can have any birthday, kid 2 must avoid 1 day, kid 3 must avoid 2,
52 and so on. Multiply the 'all different' chances, then take 1 minus that.
53 """
54 all_different = np.prod([(DAYS - i) / DAYS for i in range(k)])
55 return 1.0 - all_different
56
57
58def classes_with_shared_birthday(rng, k, n):
59 """Simulate n classes of k kids and count those with a shared birthday."""
60 shared = 0
61 for start in range(0, n, BATCH):
62 size = min(BATCH, n - start)
63 birthdays = np.sort(rng.integers(0, DAYS, size=(size, k)), axis=1)
64 # after sorting, a shared birthday means two neighbours are equal
65 shared += int((np.diff(birthdays, axis=1) == 0).any(axis=1).sum())
66 return shared
67
68
69def smallest_class_for(chance, rows):
70 """Smallest class size whose exact chance reaches `chance`."""
71 return next(r["class_size"] for r in rows if r["exact"] >= chance)
72
73
74# ---------------------------------------------------------------------------
75# Experiment
76# ---------------------------------------------------------------------------
77
78def run_experiment():
79 rng = np.random.default_rng(SEED)
80 rows = []
81 for k in CLASS_SIZES:
82 simulated = classes_with_shared_birthday(rng, k, CLASSES_PER_SIZE) / CLASSES_PER_SIZE
83 exact = exact_chance(k)
84 rows.append({"class_size": k, "simulated": simulated, "exact": exact, "difference": simulated - exact})
85 return rows
86
87
88# ---------------------------------------------------------------------------
89# Output
90# ---------------------------------------------------------------------------
91
92def save_csv(rows, path="results.csv"):
93 with open(path, "w", newline="") as f:
94 writer = csv.DictWriter(f, fieldnames=rows[0].keys())
95 writer.writeheader()
96 for row in rows:
97 writer.writerow({k: (f"{v:.6g}" if isinstance(v, float) else v) for k, v in row.items()})
98
99
100def save_chance_chart(rows, path="chance.png"):
101 k = np.array([r["class_size"] for r in rows])
102 sim = np.array([r["simulated"] for r in rows])
103 exact = np.array([r["exact"] for r in rows])
104 fig, ax = plt.subplots(figsize=(6.8, 4.2), dpi=160)
105 ax.plot(k, 100 * exact, color="#111827", lw=1.5, label="exact maths")
106 ax.plot(k, 100 * sim, "o", color="#c2410c", ms=3.5, label=f"simulation ({CLASSES_PER_SIZE:,} classes each)")
107 ax.axhline(50, color="#6b7280", ls=":", lw=1)
108 k50 = smallest_class_for(0.5, rows)
109 ax.annotate(f"{k50} kids: just over 50%", xy=(k50, 100 * exact[k == k50][0]), xytext=(k50 + 8, 35),
110 arrowprops=dict(arrowstyle="->", color="#374151"), fontsize=10)
111 ax.set_xlabel("number of kids in the class")
112 ax.set_ylabel("chance two share a birthday (%)")
113 ax.set_ylim(0, 102)
114 ax.grid(True, alpha=0.3)
115 ax.legend(frameon=False, loc="lower right")
116 ax.spines[["top", "right"]].set_visible(False)
117 fig.tight_layout()
118 fig.savefig(path, facecolor="white")
119
120
121def save_ten_classes(path="ten-classes.png", k=23, classes=10):
122 """Ten pretend classes of k kids, each drawn as dots on a year-long strip."""
123 rng = np.random.default_rng(7) # its own generator: does not change results.csv
124 fig, ax = plt.subplots(figsize=(7.4, 4.6), dpi=160)
125 with_pair = 0
126 for row in range(classes):
127 birthdays = rng.integers(0, DAYS, size=k)
128 values, counts = np.unique(birthdays, return_counts=True)
129 shared = set(values[counts > 1])
130 with_pair += bool(shared)
131 y = classes - row
132 ax.hlines(y, 0, DAYS - 1, color="#e5e7eb", lw=5)
133 plain = [d for d in birthdays if d not in shared]
134 ax.plot(plain, [y] * len(plain), "o", color="#2557a7", ms=4)
135 if shared:
136 ax.plot(sorted(shared), [y] * len(shared), "o", color="#c2410c", ms=10, mfc="none", mew=2)
137 ax.text(DAYS + 8, y, "shared!" if shared else "", va="center", fontsize=9, color="#c2410c")
138 months = ["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]
139 starts = np.cumsum([0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30])
140 ax.set_xticks(starts + 15, months)
141 ax.set_yticks(range(1, classes + 1), [f"class {classes - i}" for i in range(classes)])
142 ax.set_xlim(-5, DAYS + 55)
143 ax.spines[["top", "right", "left"]].set_visible(False)
144 ax.set_title(f"{classes} pretend classes of {k} kids: {with_pair} have a shared birthday (orange ring)", fontsize=10)
145 fig.tight_layout()
146 fig.savefig(path, facecolor="white")
147 return with_pair
148
149
150def main():
151 began = time.time()
152 rows = run_experiment()
153 seconds = time.time() - began
154 save_csv(rows)
155 save_chance_chart(rows)
156 classes_with_pair = save_ten_classes()
157
158 print(f"{'kids':>5} {'simulated':>9} {'exact':>9} {'difference':>10}")
159 for r in rows:
160 print(f"{r['class_size']:>5} {r['simulated']:>9.4f} {r['exact']:>9.4f} {r['difference']:>+10.4f}")
161
162 by_k = {r["class_size"]: r for r in rows}
163 print(json.dumps({
164 "classes_per_size": CLASSES_PER_SIZE,
165 "seconds": round(seconds, 1),
166 "kids_for_50pct": smallest_class_for(0.5, rows),
167 "kids_for_99pct": smallest_class_for(0.99, rows),
168 "simulated_23_pct": round(100 * by_k[23]["simulated"], 1),
169 "exact_23_pct": round(100 * by_k[23]["exact"], 1),
170 "simulated_30_pct": round(100 * by_k[30]["simulated"], 1),
171 "simulated_50_pct": round(100 * by_k[50]["simulated"], 1),
172 "simulated_70_pct": round(100 * by_k[70]["simulated"], 2),
173 "largest_gap_pct": round(100 * max(abs(r["difference"]) for r in rows), 2),
174 "pictured_classes_with_pair": classes_with_pair,
175 }))
176
177
178if __name__ == "__main__":
179 main()