How Far Would You Go To Rig A Coin Flip?

Riddler Express

Anna and Barry have a fair coin marked heads and tails, and want a game whose outcome gives Anna a target probability of winning. How can they devise games that give Anna a $1$ in $3$ chance, a $1$ in $4$ chance, and a $1$ in $5$ chance?

The Riddler, FiveThirtyEight, November 2, 2018(original post)

Solution

A fair coin gives only dyadic probabilities $k / 2^{n}$ directly. Non-dyadic targets like $1/3$ and $1/5$ have to come from repeating the coin until some event happens: a geometric series can sum to any rational in $(0, 1)$.

Anna wins $1$ in $3$: alternate single flips, Barry first. Barry flips, then Anna flips, then Barry, and so on, and the first head wins. On any given flip the flipper wins with probability $\tfrac{1}{2}$. Let $a$ be Anna’s win probability. Then Barry wins on his very first flip with probability $\tfrac{1}{2}$, and otherwise (also probability $\tfrac{1}{2}$) Anna becomes the next flipper, which by symmetry of the rule is the same game with roles swapped. So $$a \;=\; \tfrac{1}{2} \cdot \bigl(1 - a\bigr) \;\Longrightarrow\; a \;=\; \tfrac{1}{3}.$$

Anna wins $1$ in $4$: Barry flips twice, any head and he wins. Barry takes two flips; he wins on any head, loses only on two consecutive tails. Two tails have probability $\tfrac{1}{4}$, which is Anna’s win probability: $$\Pr(\text{Anna}) \;=\; \tfrac{1}{2} \cdot \tfrac{1}{2} \;=\; \tfrac{1}{4}.$$

Anna wins $1$ in $5$: alternate two-flip turns, Barry first. Barry flips twice, then Anna flips twice, then Barry again, and so on. The first head ends the game. Whoever is taking their turn wins their two flips with probability $\tfrac{3}{4}$ and passes the game on with probability $\tfrac{1}{4}$. So Barry wins with probability $$b \;=\; \tfrac{3}{4} \;+\; \tfrac{1}{4} \cdot \tfrac{1}{4} \cdot b \;\Longrightarrow\; b \;=\; \tfrac{3/4}{15/16} \;=\; \tfrac{4}{5},$$ so Anna wins with probability $1 - \tfrac{4}{5} = \tfrac{1}{5}$.

$$\boxed{\text{Anna's chance is } \tfrac{1}{3}, \ \tfrac{1}{4}, \ \tfrac{1}{5} \text{ from the three games above.}}$$

The pattern generalises. To give Anna a $1$ in $(2k + 1)$ chance, alternate $k$-flip turns starting with Barry, and let the first head decide; then $b = (1 - 2^{-k}) + 2^{-2k} b$, so Anna’s chance is $1 / (2^{k} + 1)$. The case $k = 1$ recovers $1/3$, $k = 2$ recovers $1/5$, and the same shape would give $1/9, 1/17, \ldots$.

The computation

Re-encode each game and run it $10^{6}$ times. The empirical win rates must match $1/3$, $1/4$, $1/5$ to Monte Carlo precision.

1. For the $1/3$ game, repeatedly flip alternating Barry/Anna; first head wins.

2. For the $1/4$ game, Barry flips two; any head wins for Barry.

3. For the $1/5$ game, repeatedly flip two-Barry / two-Anna turns; first head wins.

4. Compare each empirical Anna-win rate to the target.

import random

def game_third():                              # Anna wins 1/3
    turn = "B"
    while True:
        if random.random() < 0.5:
            return "A" if turn == "A" else "B"
        turn = "A" if turn == "B" else "B"

def game_quarter():                            # Anna wins 1/4
    for _ in range(2):
        if random.random() < 0.5:
            return "B"
    return "A"

def game_fifth():                              # Anna wins 1/5
    turn = "B"
    while True:
        for _ in range(2):
            if random.random() < 0.5:
                return turn
        turn = "A" if turn == "B" else "B"

random.seed(0)
TRIALS = 1_000_000
for name, g, target in [("1/3", game_third, 1/3),
                        ("1/4", game_quarter, 1/4),
                        ("1/5", game_fifth, 1/5)]:
    wins = sum(1 for _ in range(TRIALS) if g() == "A")
    print(f"{name}: empirical {wins/TRIALS:.4f}, target {target:.4f}")

The script prints empirical Anna-win rates $\approx 0.333$, $0.250$, $0.200$, matching the boxed answer.

Riddler Classic

All $100$ seats in Riddler Nation’s Senate are decided by a virtual coin flip per seat, Programmers on heads and Theorists on tails. The Programmers control the coin; the Theorists collect every result and can challenge in the Statistical Court (an honest, learned panel of statisticians) at any time, with no statute of limitations. (a) If the coin is fair, what is the probability a given party wins a simple majority? a $60$-seat supermajority? (b) What annual weighting gives the Programmers a $50\%$ chance of a supermajority in a single year? How many such years before the Theorists can prove (with at least $99\%$ confidence) that the coin is biased? (c) If the coin is weighted permanently for $100$ elections, how heavy a weighting escapes a $99\%$ challenge over the whole century? How many supermajorities does that buy? (d) What is the optimal cheating strategy for perpetual escape? (e) Does varying the weight on a seat-by-seat basis within an election help?

The Riddler, FiveThirtyEight, November 2, 2018(original post)

Solution

Each Senate seat is one Bernoulli trial; an election is a sum of $100$ independent trials. With $X \sim \mathrm{Binomial}(100, p)$ counting Programmer seats, $X \ge 51$ is a simple majority and $X \ge 60$ a supermajority.

(a) Fair coin baselines. For $p = 1/2$, $$\Pr(X \ge 51) \;=\; \sum_{k=51}^{100} \binom{100}{k} 2^{-100} \;\approx\; 0.4602,$$ $$\Pr(X \ge 60) \;=\; \sum_{k=60}^{100} \binom{100}{k} 2^{-100} \;\approx\; 0.0284.$$ So a given party wins a simple majority about $\mathbf{46\%}$ of the time and a supermajority about $\mathbf{2.8\%}$ of the time (rounded to $3\%$).

(b) One-year boost to a coin-flip on the supermajority. We need the $p$ with $\Pr(X \ge 60 \mid n = 100, p) = 1/2$. Binomial CDF inversion gives $$p^{\dagger} \;\approx\; \mathbf{0.5947} \;\approx\; 59.5\%.$$ The Theorists test the fairness null $H_{0} \!: p = 1/2$ on the cumulative flip data. After $Y$ years of cheating at $p^{\dagger}$ and $100 - Y$ fair years (say the Programmers cheat once at the start), the total head count has mean $50(100) + 50 Y (2 p^{\dagger} - 1)$ on the bias and a roughly Gaussian sampling distribution under the null with standard deviation $\sqrt{100 \cdot 100/4} = 50$. The fair distribution exceeds the observed total with probability at least $99\%$ when the excess over $50 \cdot 100 = 5000$ is at most $2.326 \cdot 50 = 116.3$. Each cheated year contributes an expected excess of $100(p^{\dagger} - 0.5) = 9.47$, so the Programmers escape detection so long as $Y \cdot 9.47 \lesssim 116$, that is, $Y \le 1$ year (at $Y=2$ the expected excess is already $18.9$, well within the tail under the null with negligible probability of escape). They get away with this aggressive weighting only once.

(c) Permanent weighting for $100$ elections. The Theorists’ challenge looks at the cumulative count over $100 \cdot 100 = 10{,}000$ flips. Under fair flipping, the $99$th percentile of $\mathrm{Binomial}(10{,}000, 1/2)$ is $$q_{99} \;=\; \mathbf{5{,}116},$$ so a permanent weight $p \le 5116/10000 = 0.5116$ keeps the cheating Programmers’ expected total inside the fair $99$th-percentile envelope. At $p^{\ast} = 0.5116$, the expected number of supermajorities over $100$ elections is $$100 \cdot \Pr(X \ge 60 \mid p^{\ast}) \;\approx\; 100 \cdot 0.0472 \;=\; \mathbf{4.72}.$$

(d) Optimal strategy. The optimal strategy lets the Programmers oscillate. Early years they weight heavily and harvest more supermajorities, then dial the weight back so that the running cumulative head count stays below the fair-coin $99\%$ percentile in every year (the court can examine any sub-window). In the limit, the strategy approaches a fair coin asymptotically, but the early years pay out extra supermajorities, beating the constant $51.16\%$ in expected total. The exact optimum is the solution of a constrained scheduling problem $\{p_{1}, \ldots, p_{100}\}$ maximising $\sum_{t} \Pr(X \ge 60 \mid p_{t})$ subject to the running-window $99\%$ constraint, which is solvable numerically and gives the heads-high-early, fair-later schedule.

(e) Per-seat weighting within one election. The total Programmer count is the sum of independent Bernoullis with weights $p_{1}, \ldots, p_{100}$. The Theorists’ running-total test cares only about the mean $\sum p_{i}$, not the spread, so any constraint they impose binds the average. For a fixed average $\bar p$, the variance of the seat count is $\sum p_{i} (1 - p_{i})$, which by Jensen’s inequality is maximised when all $p_{i} = \bar p$ (uniform). Heterogeneous per-seat weights only reduce the variance, which (when $\bar p < 0.6$) shrinks the upper tail and so reduces the supermajority chance. Net: per-seat heterogeneity does not help, and a Programmer who has decided on an average weight is best off applying it uniformly. The seat-by-seat lever is illusory.

The computation

Compute the binomial baselines exactly, invert the $\Pr(X \ge 60) = 0.5$ equation for $p^{\dagger}$, compute $q_{99}$ of $\mathrm{Binomial}(10000, 1/2)$, and evaluate the expected supermajority count under the permanent-weight ceiling.

1. Closed-form binomial tails via math.comb (no sampling needed).

2. Bisection on $p$ in $(0.5, 0.7)$ to find $\Pr(X \ge 60 \mid p) = 0.5$.

3. Compute $q_{99}$ of $\mathrm{Binomial}(10000, 1/2)$ exactly.

4. Plug $p^{\ast} = q_{99}/10000$ back in for expected supermajorities.

from math import comb

def tail(n, p, k):                             # P(X >= k) for Binomial(n,p)
    q = 1 - p
    return sum(comb(n, j) * p**j * q**(n - j) for j in range(k, n + 1))

print(f"Fair: P(>=51 of 100) = {tail(100, 0.5, 51):.4f}")
print(f"Fair: P(>=60 of 100) = {tail(100, 0.5, 60):.6f}")

# Bisection for the one-year cheat weight
lo, hi = 0.5, 0.7
for _ in range(80):
    mid = (lo + hi) / 2
    lo, hi = (mid, hi) if tail(100, mid, 60) < 0.5 else (lo, mid)
print(f"One-year cheat weight (50% of supermajority): {hi:.4f}")

# 99th percentile of Binomial(10000, 0.5): smallest q with P(X<=q) >= 0.99.
# Use Decimal to avoid float underflow on comb(10000,k) * 2**(-10000).
from decimal import Decimal, getcontext
getcontext().prec = 60
n = 10_000
half_n = Decimal(2) ** n
cum = Decimal(0)
target = Decimal("0.99")
for k in range(n + 1):
    cum += Decimal(comb(n, k)) / half_n
    if cum >= target:
        q = k
        print(f"99th percentile of Binomial(10000, 0.5) = {q}")
        break

p_perm = q / n
print(f"Permanent safe weight = {p_perm:.4f}")
print(f"Expected supermajorities in 100 years at p* = "
      f"{100 * tail(100, p_perm, 60):.2f}")

The script prints $0.4602$, $0.0284$, the one-year boost $0.5947$, $q_{99} = 5116$, and an expected $\approx 4.72$ supermajorities at the permanent ceiling, matching every numeric headline.