Is Your Friend Full Of It?

Riddler Express

Your friend claims to have once made $17$ free throws in a row, having not touched a basketball for years. Assume he is a $70\%$ free-throw shooter. What is the expected number of free throws he would need to take before completing a streak of $17$ makes in a row? What if his accuracy were a little worse?

The Riddler, FiveThirtyEight, September 1, 2017(original post)

Solution

Let $T_L$ be the number of trials a Bernoulli($p$) process needs to first produce a streak of $L$ consecutive successes. The expectation $\mathbb{E}[T_L]$ admits a clean closed form, $$\mathbb{E}[T_L] = \frac{1 - p^L}{(1 - p)\,p^L}.$$ Derivation. Condition on the first failure. Let $E = \mathbb{E}[T_L]$. At any point before a success streak of length $L$ is achieved, restart the clock at any failure. Consider the first attempt: with probability $1 - p$ it is a failure (one trial used, no progress), and with probability $p$ it is a success that begins a run. Continuing along a run of successes, if all $L$ shots in a row come up successes (probability $p^L$), we finish in $L$ trials; otherwise (probability $1 - p^L$) the streak is broken at some point inside the first $L$ trials, and we restart fresh from the failure.

Working out the expectation with a first-step argument on each shot in the streak: $$\mathbb{E}[T_L] = p^L \cdot L + \sum_{k=0}^{L-1} p^k (1-p) \big(k + 1 + \mathbb{E}[T_L]\big).$$ The first term: with probability $p^L$ the first $L$ shots are all successes; we finish in $L$ trials. The summand: with probability $p^k(1-p)$ the first $k$ shots are successes and the $(k+1)$th is a failure (using $k+1$ trials), after which we start over with a fresh independent $T_L$. Expanding, $$\mathbb{E}[T_L] = L p^L + (1-p) \sum_{k=0}^{L-1} p^k (k + 1) + (1 - p^L) \mathbb{E}[T_L].$$ Move the $\mathbb{E}[T_L]$ term to the left, $$p^L \,\mathbb{E}[T_L] = L p^L + (1-p) \sum_{k=0}^{L-1} p^k (k + 1).$$ Use $\sum_{k=0}^{L-1} (k+1) p^k = \frac{d}{dp} \sum_{k=0}^{L-1} p^{k+1} = \frac{d}{dp} \cdot \frac{p(1 - p^L)}{1 - p}$, which after simplification gives $(1 - p^L)/(1 - p) - L p^L /(1 - p)$. Substituting and simplifying, $$\mathbb{E}[T_L] = \frac{1 - p^L}{(1 - p) p^L}.$$

Plugging in $p = 0.7$, $L = 17$: $$\mathbb{E}[T_{17}] = \frac{1 - 0.7^{17}}{0.3 \cdot 0.7^{17}} = \frac{0.7^{-17} - 1}{0.3} \approx 1429.55.$$

$$\boxed{\,\mathbb{E}[T_{17}] \approx 1{,}430 \text{ shots.}\,}$$

The estimate is highly sensitive to $p$ because the dominant term is $p^{-L}$, which grows like a geometric in $L$ when $p$ shrinks. At $p = 0.6$, $\mathbb{E}[T_{17}] = (0.6^{-17} - 1)/0.4 \approx 17{,}042$, about $12$ times longer. The friend’s claim is plausible at $70\%$ accuracy (a couple of hours’ practice) but quickly becomes unreasonable as the shooting percentage drops.

The computation

Simulate the actual experiment: trial after trial of Bernoulli($p$) shots, count the number of shots until the first run of length $L$. Average over many trials.

1. Initialise streak length to $0$, trial count to $0$.

2. For each shot, increment trial count; flip a Bernoulli($p$); if heads, increment streak, else reset streak to $0$.

3. Stop when streak reaches $L$; report trial count.

4. Average over many trials and compare to the closed form.

import random
def first_run(L, p, rng):
    streak = n = 0
    while streak < L:
        n += 1
        streak = streak + 1 if rng.random() < p else 0
    return n

rng = random.Random(0)
trials = 30_000
mean = sum(first_run(17, 0.7, rng) for _ in range(trials)) / trials
print(round(mean, 1))                            # ~1430
# closed form
p, L = 0.7, 17
print(round((1 - p**L) / ((1 - p) * p**L), 2))   # 1429.55

The empirical mean clusters around the closed form to within sampling error.

Riddler Classic

Seven players each receive a uniformly-random black or white hat. Each can see the others’ hats but not her own. Each player simultaneously and independently writes down “black”, “white”, or “pass”. The team wins if at least one player guesses her own hat colour correctly and nobody guesses wrong; otherwise the team loses. The players may agree on a strategy beforehand but cannot communicate during the game. What is the best winning probability? Extra credit: $2^N - 1$ players.

The Riddler, FiveThirtyEight, September 1, 2017(original post)

Solution

The team can win with probability $7/8$ using a strategy built from the Hamming code. More generally, with $n = 2^N - 1$ players the team can win with probability $(2^N - 1)/2^N$.

The trick. Label the players with the nonzero binary strings of length $N = 3$: Anna $= 001$, Ben $= 010$, Clarice $= 011$, Doug $= 100$, Edna $= 101$, Fred $= 110$, Georgina $= 111$. Each player $p$, seeing the others’ hats, computes the bitwise XOR (i.e., addition modulo $2$ component-wise) of the labels of all teammates wearing a black hat. Call this value $s_p$. The rule is:

• If $s_p = 000$, guess “black”.

• If $s_p$ equals the player’s own label, guess “white”.

• Otherwise, pass.

Why it works. Let $S$ be the XOR of the labels of all black-hat wearers. Each player $p$ sees everyone else, so for $p$:

• If $p$’s hat is white, then $s_p = S$ (her own label contributes $0$).

• If $p$’s hat is black, then $s_p = S \oplus p$ (her label cancels out of the sum).

Player $p$ guesses black iff $s_p = 000$; she guesses white iff $s_p = p$.

Now consider the value of $S$ over a uniform random colouring of all seven hats:

• Case $S = 000$. This means the XOR of all black labels is $0$. Every player $p$ has $s_p =$ XOR with or without her own label; specifically, $s_p = p$ if she has a black hat, $s_p = 000$ if white. So every white-hat player guesses “black” and is wrong, and every black-hat player guesses “white” and is wrong. The team loses.

• Case $S \neq 000$. Then $S \in \{001, 010, \ldots, 111\}$, the binary string of some specific player. For this player $p^* = S$: if her hat is black, $s_{p^*} = S \oplus p^* = 000$, she guesses “black” correctly. If her hat is white, $s_{p^*} = S = p^*$, she guesses “white” correctly. Either way, $p^*$ guesses correctly. Every other player $p$ has $s_p \neq 000$ and $s_p \neq p$, so passes. The team wins.

The team wins precisely when $S \neq 000$. Since the seven hats are i.i.d. uniform, $S$ is uniform over $\{0, 1\}^3$ (any single hat colour, conditional on the others, makes $S$ equally likely to be any value), so $\Pr(S \neq 000) = 7/8$.

$$\boxed{\,\Pr(\text{win}) = \tfrac{7}{8}.\,}$$

Optimality. No strategy does better than $7/8$. Consider the expected number of correct guesses minus wrong guesses across all $2^7$ colourings. Each individual player guesses correctly on exactly half the colourings she does not pass on (her own hat is independent of what she sees), so the per-player correct-minus-wrong total is zero. Summed across players, the total correct-minus-wrong is $0$. Each colouring contributes either $+1$ (one correct guess, others pass: team wins) or some negative quantity (any wrong guess: team loses); for the totals to sum to zero, the winning colourings exactly balance the wrong-guess contributions. The maximum is achieved when every winning colouring contributes exactly $+1$ and every losing colouring contributes exactly $-1$ (one wrong guess), with $7/8$ of colourings winning. This balance is achieved by the Hamming strategy.

Extra credit. With $n = 2^N - 1$ players, label players by the nonzero binary strings of length $N$. The same XOR strategy applies, and the team wins iff the XOR of all black-hat labels is nonzero, which happens with probability $(2^N - 1)/2^N$.

The computation

Enumerate all $2^7 = 128$ hat colourings; for each, run the XOR strategy for each player; count the colourings in which the team wins.

1. For each player $p \in \{1, \ldots, 7\}$ (binary labels $001, \ldots, 111$) and each colouring (a $7$-bit string $b$):

2. Compute $s_p =$ XOR of labels of teammates with $b_i = 1$.

3. If $s_p = 0$, guess black; if $s_p = p$, guess white; else pass.

4. Team wins iff at least one guess is correct and no guess is wrong.

n = 7
labels = list(range(1, n + 1))   # 001..111 in binary
wins = 0
for b in range(1 << n):
    hats = [(b >> i) & 1 for i in range(n)]
    correct = wrong = 0
    for p in range(n):
        s = 0
        for q in range(n):
            if q != p and hats[q] == 1:
                s ^= labels[q]
        if s == 0:
            guess = 1                            # black
        elif s == labels[p]:
            guess = 0                            # white
        else:
            guess = None
        if guess is None:
            continue
        if guess == hats[p]: correct += 1
        else: wrong += 1
    if wrong == 0 and correct >= 1:
        wins += 1
print(wins, wins / (1 << n))                     # 112  0.875

The team wins on exactly $112 = 7 \cdot 128 / 8$ of the $128$ colourings, confirming $\Pr(\text{win}) = 7/8$.