Can You Find The Luckiest Coin?

Riddler Express

In a duel of random numbers, your generator has been sabotaged to return a uniform value in $[0.1, 0.8]$ instead of $[0, 1]$, while your opponent’s is a clean uniform $[0,1]$. The larger number wins. What is your probability of winning?

Solution

Let your (rigged) number be $X \sim \mathcal{U}[a, b]$ and your opponent’s be $Y \sim \mathcal{U}[0,1]$. You win when $X > Y$. For a fixed value $X = x$ inside $[0,1]$, the opponent’s number is below it with probability exactly $x$, so $$\Pr(\text{win}) = \Pr(X > Y) = \mathbb{E}[X] = \frac{a + b}{2}.$$ With $a = 0.1$ and $b = 0.8$, $$\Pr(\text{win}) = \frac{0.1 + 0.8}{2} = \boxed{0.45}.$$ The sabotage caps you at $0.8$ but also lifts your floor to $0.1$; on balance your average number is $0.45$, just under the even-odds $0.5$, so you are a slight underdog.

The computation

Draw the two numbers many times and count how often yours is larger.

import numpy as np
rng = np.random.default_rng(0)
N = 5_000_000
x, y = rng.uniform(0.1, 0.8, N), rng.uniform(0, 1, N)
print(np.mean(x > y))                          # ~0.45

Riddler Classic

Flip a million fair coins, discard the tails, flip the survivors again, and repeat. If you ever reach exactly one coin, call it the luckiest. What is the probability you ever have exactly one coin (rather than jumping from two-or-more straight to zero)?

Solution

Let $P(N)$ be the probability of eventually reaching exactly one coin starting from $N$. After one round, $N$ coins leave $i$ heads with probability $\binom{N}{i}/2^N$, and then the game continues as if started with $i$ coins. Splitting off the $i = N$ term (all heads, no progress) and solving, $$P(N) = \frac{1}{2^N - 1}\sum_{i=1}^{N-1}\binom{N}{i} P(i), \qquad P(1) = 1.$$ Iterating this upward, $P(N)$ settles very quickly to a limit, so for a million coins $$P(10^6) \approx \boxed{0.7213}.$$ The value does not converge to a single clean constant but wobbles by less than a thousandth as $N$ doubles (a faint log-periodic ripple), hovering around $0.7213$.

The computation

Build $P(1), P(2), \dots$ from the recurrence with exact fractions and read off the large-$N$ value.

from fractions import Fraction as F
from functools import lru_cache
from math import comb
@lru_cache(None)
def P(n):
    if n == 1: return F(1)
    return F(1, 2**n - 1) * sum(comb(n, i) * P(i) for i in range(1, n))
print(float(P(100)))                           # ~0.7213