"""Chapter 15, advanced layer: numbers used in the text and in Exercise 15.3. Standard library only. Every model here is a teaching construction, not a result from a paper: 1. a two-player zero-sum "debate game" with a judge who sides with the true answer with probability q when the two answers differ; 2. polynomial versus exponential growth; 3. the colour-blind friend and the two balls (an interactive proof, error halves each round); 4. a debate about the number of primes in an interval (after Irving et al. 2018, Sec. 2.2), played out on small numbers; 5. a toy model of obfuscated arguments (the book's own simplification); 6. why stability matters: a long chain of steps versus a majority vote over evidence. """ from math import comb # ---------- 1. the toy debate game ---------- S = ["T", "F"] # defend the true answer / the false answer def alice_wins(a, b, q): """Probability that Alice wins, given both answers and judge accuracy q.""" if a == b: return 0.5 return q if a == "T" else 1 - q def analyse(q): br_bob = {a: min(S, key=lambda b: alice_wins(a, b, q)) for a in S} # Bob minimises Alice's payoff br_alice = {b: max(S, key=lambda a: alice_wins(a, b, q)) for b in S} eq = [(a, b) for a in S for b in S if br_alice[b] == a and br_bob[a] == b] return br_alice, br_bob, eq print("1. toy debate game (Alice's winning probability)") for q in (0.8, 0.4, 0.7, 0.3): table = {(a, b): alice_wins(a, b, q) for a in S for b in S} br_a, br_b, eq = analyse(q) print(f" q={q}: table={table}") print(f" Bob's best response to Alice: {br_b}; Alice's best response to Bob: {br_a}") print(f" pure equilibria: {eq}") # q = 0.5: every cell with different answers is 0.5, so all four profiles are equilibria q = 0.5 eq_half = [(a, b) for a in S for b in S if all(alice_wins(a, b, q) >= alice_wins(x, b, q) for x in S) and all(alice_wins(a, b, q) <= alice_wins(a, y, q) for y in S)] print(f" q=0.5: pure equilibria: {eq_half}") # ---------- 2. polynomial versus exponential ---------- print("\n2. n^2 versus 2^n") for n in (10, 20, 50, 100): print(f" n={n:>3}: n^2={n**2:>6} 2^n={2**n:.3e}") # ---------- 3. the two balls ---------- print("\n3. two balls, colour-blind friend: chance a bluffing prover survives k rounds") for k in (1, 10, 20): print(f" k={k:>2}: (1/2)^{k} = {0.5**k:.3e}") # ---------- 4. the primes debate ---------- def is_prime(n): if n < 2: return False d = 2 while d * d <= n: if n % d == 0: return False d += 1 return True def count(lo, hi): return sum(1 for k in range(lo, hi + 1) if is_prime(k)) def primes_debate(N, claim): """Alice claims there are `claim` primes in [1, N]. She splits every interval in half and keeps the left half honest, pushing the whole error to the right; Bob always challenges the half whose claim is false. Returns the path and the number of checks the judge makes.""" lo, hi, c = 1, N, claim path, checks = [], 0 while lo < hi: mid = (lo + hi) // 2 left_true = count(lo, mid) left_claim = left_true right_claim = c - left_claim checks += 1 # judge checks left_claim + right_claim == c if right_claim != count(mid + 1, hi): path.append(((lo, mid, left_claim), (mid + 1, hi, right_claim), "right")) lo, c = mid + 1, right_claim else: path.append(((lo, mid, left_claim), (mid + 1, hi, right_claim), "left")) hi, c = mid, left_claim checks += 1 # judge checks one number for primality return path, (lo, c, int(is_prime(lo))), checks print("\n4. primes debate") true64 = count(1, 64) print(f" primes in [1,64] = {true64}; [1,32] = {count(1, 32)}; [33,64] = {count(33, 64)}") path, leaf, checks = primes_debate(64, true64 + 1) for (l, r, side) in path: print(f" Alice: [{l[0]},{l[1]}] has {l[2]}, [{r[0]},{r[1]}] has {r[2]} -> Bob challenges {side}") print(f" leaf: number {leaf[0]}, Alice claims {leaf[1]} prime(s), truth {leaf[2]}; judge checks = {checks}") for N in (64, 1024): _, _, ch = primes_debate(N, count(1, N) + 1) print(f" N={N}: judge checks {ch} things instead of testing {N} numbers") # ---------- 5. toy model of obfuscated arguments (the book's simplification) ---------- print("\n5. obfuscation toy model: p_find = (B_h/B)^K, judge accuracy = 1/2 + p_find/2") for B, Bh, K in [(10, 3, 1), (10, 3, 2), (10, 3, 3), (10, 3, 5), (8, 4, 2), (8, 4, 4)]: p = (Bh / B) ** K print(f" B={B:>2} B_h={Bh} K={K}: p_find={p:.4f} judge accuracy={0.5 + p / 2:.4f}") # ---------- 6. stability: a long chain versus a majority vote ---------- print("\n6. stability illustration") for p in (0.999, 0.99): print(f" chain of 100 steps, each right with p={p}: all right = {p**100:.3f}") def majority(n, p): return sum(comb(n, k) * p**k * (1 - p)**(n - k) for k in range(n // 2 + 1, n + 1)) for p in (0.9, 0.85): print(f" majority of 9 independent pieces, each right with p={p}: majority right = {majority(9, p):.4f}") # prover-estimator toy case (Brown-Cohen et al. 2025, arXiv v1): one hidden false subclaim among m # (the paper writes q; the chapter uses m because q is the judge accuracy of part 1); the estimator # gives each subclaim probability 1/m of being false for m in (10,): print(f" m={m}: estimator error at most 1/m = {1/m}, after two obfuscated rounds 1/m^2 = {1/m**2}")