Can You Make An Unfair Coin Fair?

The Riddler for November 6, 2020. The Express compares two treadmill runs where pace, not speed, varies linearly, and the Classic counts the biased-coin probabilities that can simulate a fair coin within three flips.

Riddler Express

Santul runs $20$ miles twice. Run 1 holds a constant $9$ minutes per mile. Run 2 starts at $10$ minutes per mile and ends at $8$, with his pace (minutes per mile, not speed) changing linearly in time. Which run is faster, and what are the two times?

The Riddler, FiveThirtyEight, November 6, 2020(original post)

Solution

Run 1 is immediate: $20 \times 9 = 180$ minutes, exactly $3$ hours.

For Run 2, let $T$ be its total time in minutes. Pace varies linearly from $10$ to $8$, so at time $t$ the pace is $10 - 2t/T$ minutes per mile and the speed is its reciprocal, $1/(10 - 2t/T)$ miles per minute. The distance must be $20$ miles: $$\int_0^T \frac{dt}{10 - 2t/T} = 20.$$ Substituting $u = t/T$ gives $T\int_0^1 \frac{du}{10 - 2u} = \frac{T}{2}\big[\ln 10 - \ln 8\big] = \frac{T}{2}\ln\tfrac54 = 20$, so $$T = \frac{40}{\ln(5/4)} \approx 179.26 \text{ minutes} \approx \boxed{2\!:\!59\!:\!15},$$ about $45$ seconds faster than Run 1’s $3\!:\!00\!:\!00$. The pace spends more time near its slow end, but averaging the reciprocal of a linear pace (a logarithm) still edges below the constant $9$-minute pace.

The computation

Encode the constraint: integrate the speed $1/(10 - 2t/T)$ over $[0, T]$, set it to $20$ miles, and solve for $T$.

import math
run1 = 20 * 9                          # 180 minutes
T = 40 / math.log(5 / 4)               # solves (T/2) ln(5/4) = 20
mins, secs = int(T), round((T - int(T)) * 60)
print(run1, round(T, 3), f'{mins}:{secs:02d}')   # 180  179.257  179:15

Run 2 takes $40/\ln(5/4) \approx 179.26$ minutes, edging out Run 1’s $180$.

Riddler Classic

Von Neumann turns a biased coin (heads probability $p$) into a fair one. You want to simulate a fair coin in at most three flips: assign some set of three-flip outcomes to “heads” so their total probability is exactly $\tfrac12$. For how many values of $p$ is this possible?

The Riddler, FiveThirtyEight, November 6, 2020(original post)

Solution

Three flips give eight outcomes, grouped by their number of heads: $p^3$ (one outcome), $p^2(1-p)$ (three), $p(1-p)^2$ (three), $(1-p)^3$ (one). A simulation works when some subset of these outcomes has total probability exactly $\tfrac12$. By symmetry every achievable sum is $$a\,p^3 + b\,p^2(1-p) + c\,p(1-p)^2 + d\,(1-p)^3 = \tfrac12,$$ with $a, d \in \{0,1\}$ and $b, c \in \{0,1,2,3\}$, which is $2 \cdot 4 \cdot 4 \cdot 2 = 64$ candidate equations. Each is a cubic (or lower) in $p$; collecting their roots in $(0,1)$ and removing duplicates leaves $$\boxed{19}$$ distinct values of $p$. They include the obvious $p = \tfrac12$, plus $p = 1/\sqrt2$ and $1 - 1/\sqrt2$ (where $p^2 = \tfrac12$ or $(1-p)^2 = \tfrac12$, achievable already in two flips), and sixteen others. Extending to at most $N$ flips gives the counts $1, 3, 19, 271, 8635, 623533, \ldots$, a sequence only recently catalogued.

The computation

Encode all $64$ subset-sum polynomials, find their roots in $(0,1)$, and cluster numerically equal roots before counting.

import numpy as np
p, q = np.poly1d([1, 0]), np.poly1d([-1, 1])      # p and (1 - p)
roots = []
for a in range(2):
    for b in range(4):
        for c in range(4):
            for d in range(2):
                poly = a*p**3 + b*(p**2*q) + c*(p*q**2) + d*q**3 - 0.5
                for r in np.roots(poly.c):
                    if abs(r.imag) < 1e-9 and 1e-9 < r.real < 1 - 1e-9:
                        roots.append(r.real)
roots.sort()
distinct = [r for i, r in enumerate(roots)
            if i == 0 or r - roots[i-1] > 1e-5]      # cluster near-equal roots
print(len(distinct))                              # 19

Nineteen biased-coin probabilities can simulate a fair coin within three flips.