Can You Snatch Defeat From The Jaws Of Victory?

The Riddler for November 13, 2020. The Express finds the expected take in a runaway Jeopardy! round with one Daily Double, and the Classic computes how often a coin-flip contest reaches near-certain victory and then collapses.

Riddler Express

On Jeopardy! you answer all $30$ clues correctly, working up each column: six $200 clues, then six $400, and so on to six $1,000. One clue, uniformly random among the $30$, is a Daily Double: instead of its face value you double your winnings so far, or wager up to $1,000 if you have less, and you always bet the maximum. What are your expected winnings?

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

Solution

The $30$ clue values sum to $6(200 + 400 + 600 + 800 + 1000) = \$18{,}000$. Condition on which clue is the Daily Double. If it is the $i$-th clue selected, you forfeit that clue’s face value but gain $\max(\text{winnings so far}, 1000)$ instead. So your total is $18{,}000 - \text{face}_i + \max(\text{pre}_i, 1000)$, where $\text{pre}_i$ is the sum of the faces before clue $i$.

Averaging over the $30$ equally likely positions: the non–Daily-Double clues contribute $29 \cdot 18{,}000 = \$522{,}000$ in total across the cases, and the Daily Double bonuses $\max(\text{pre}_i, 1000)$ sum to $\$192{,}000$ (it is worth $1,000 for each of the first six clues, then grows: $1,200, $1,600, $\ldots$, up to $17,000 if it lands last). Hence $$E = \frac{522{,}000 + 192{,}000}{30} = \frac{714{,}000}{30} = \boxed{\$23{,}800}.$$

The computation

Encode the board order and average over the $30$ possible Daily Double positions.

face = [200]*6 + [400]*6 + [600]*6 + [800]*6 + [1000]*6
total = sum(face)                                  # 18000
winnings = [(total - face[i]) + max(sum(face[:i]), 1000) for i in range(30)]
print(sum(winnings) / 30)                          # 23800.0

The expected take is $23,800.

Riddler Classic

The Birds and Felines flip a fair coin $101$ times; the Birds win if heads totals at least $51$. At any moment the Birds’ win probability is determined by the flips that remain. What is the probability that the Birds at some point reach at least a $99\%$ chance of winning and then go on to lose?

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

Solution

Track the game as a walk on states $(W, L)$, the heads and tails so far. From $(W, L)$ the Birds still need $51 - W$ heads among the $101 - W - L$ remaining flips, so their win probability is the binomial tail $$\Pr(\text{win} \mid W, L) = \frac{1}{2^{\,r}}\sum_{k = 51 - W}^{r} \binom{r}{k}, \qquad r = 101 - W - L.$$ Call a (non-terminal) state “safe” when this is at least $0.99$. The walk starts at $(0,0)$ with a $50\%$ chance and moves to $(W+1, L)$ or $(W, L+1)$ with equal probability until a team reaches $51$.

The key simplification: once the walk first enters a safe state $s$, its subsequent chance of losing is exactly $1 - \Pr(\text{win} \mid s) \le 0.01$, independent of how it got there. So propagate the probability mass forward while it has never been safe; whenever mass crosses into a safe state $s$, it contributes (mass)$\,\times\,(1 - \Pr(\text{win}\mid s))$ to the answer. Summing these first-entry contributions gives $$\boxed{\approx 0.21\%}.$$ The blown-lead risk peaks near the end (about $2\%$ of games that finish at $50$–$51$ had been safe at some point), but starting fresh it is only about one in five hundred.

The computation

Encode the win-probability tail and propagate the never-yet-safe mass; accumulate the loss probability at each first entry into the safe region.

from math import comb
from collections import defaultdict

def win_prob(W, L):
    r = 101 - W - L
    need = 51 - W
    if need <= 0: return 1.0           # Birds already have 51 heads
    if L >= 51:   return 0.0           # Birds already lost
    if need > r:  return 0.0
    return sum(comb(r, k) for k in range(need, r + 1)) / 2**r

mass = defaultdict(float); mass[(0, 0)] = 1.0
answer = 0.0
for flips in range(101):
    for W in range(52):
        L = flips - W
        if not (0 <= L <= 51): continue
        m = mass[(W, L)]
        if m == 0 or W == 51 or L == 51: continue
        for nW, nL in ((W + 1, L), (W, L + 1)):
            wp = win_prob(nW, nL)
            if nW < 51 and nL < 51 and wp >= 0.99:   # first entry, safe
                answer += (m / 2) * (1 - wp)
            else:
                mass[(nW, nL)] += m / 2
print(round(answer * 100, 2))          # 0.21  (percent)

The Birds reach near-certain victory and then lose about $0.21\%$ of the time.