# Can you find the luckiest coin?

A FiveThirtyEight Riddler puzzle.
mathematics
Riddler
Published

February 18, 2022

## Riddler Express

It’s time for a random number duel! You and I will both use random number generators, which should give you random real numbers between $$0$$ and $$1$$. Whoever’s number is greater wins the duel!

There’s just one problem. I’ve hacked your random number generator. Instead of giving you a random number between $$0$$ and $$1$$, it gives you a random number between $$0.1$$ and $$0.8$$.

What are your chances of winning the duel?

## Solution

The random generator that I have generates numbers according to $$X \sim \mathcal{U}[a,b]$$ where $$0\leq a \leq b\leq1$$ and the random generator that you have (in the general case) generates numbers according to $$Y\sim\mathcal{U}[0,1]$$. We need the probability, $$\mathbb{P}[X< Y]$$. This is given by the area of the trapezium $$EFGH$$ divided by the area of the rectangle $$EFIJ$$. We have $$|EF| = |IJ| = b-a$$, $$|FG|=b$$, $$|EH|=a$$ and $$|EJ|=1$$ in the figure below

$\mathbb{P}[X< Y] = \frac{\frac{1}{2}(b-a)(b+a)}{(b-a)} = \frac{b+a}{2}.$

In our particular case $$a=0.1$$ and $$b=0.8$$, therefore the probability of me winning is $$\textbf{0.45}$$.

### Computational validation

The probability of me winning the duel as per the simulation below is $$\textbf{0.45}$$ which validates the result we got earlier.

from numpy.random import uniform

def prob_win(p1l, p1h, p2l, p2h, runs = 1000000):
total_wins = 0
for _ in range(runs):
x, y = uniform(p1l, p1h), uniform(p2l, p2h)
if x > y:
total_wins += 1

print(prob_win(0.1,0.8,0,1))

## Riddler Classic

I have in my possession 1 million fair coins. Before you ask, these are not legal tender. Among these, I want to find the “luckiest” coin.

I first flip all 1 million coins simultaneously (I’m great at multitasking like that), discarding any coins that come up tails. I flip all the coins that come up heads a second time, and I again discard any of these coins that come up tails. I repeat this process, over and over again. If at any point I am left with one coin, I declare that to be the “luckiest” coin.

But getting to one coin is no sure thing. For example, I might find myself with two coins, flip both of them and have both come up tails. Then I would have zero coins, never having had exactly one coin.

What is the probability that I will — at some point — have exactly one “luckiest” coin?

## Solution

Let $$\mathbb{P}[N]$$ be the probabillity that we will have exactly one “luckiest” coin starting with $$N$$ coins. We have the following recurrence relation:

\begin{align*} \mathbb{P}[N] &= \sum_{i=1}^N \mathbb{P}[i] \frac{N \choose i}{2^N} \\\\ \implies \mathbb{P}[N](1 - \frac{1}{2^N}) &= \sum_{i=1}^{N-1} \mathbb{P}[i] \frac{N \choose i}{2^N} \\\\ \implies \mathbb{P}[N] &= \frac{1}{2^N-1}\sum_{i=1}^{N-1} \mathbb{P}[i] {N \choose i} \\\\ \end{align*}

because the probability of ending up with $$i$$ heads when you flip $$N$$ coins is $$\frac{N \choose i}{2^N}$$ and then it is equivalent to starting the game with $$i$$ coins. When $$N=1$$, $$\mathbb{P}[N]=1$$.

### Computational Solution

From the code below, we get $$\mathbb{P}[100] \approx \textbf{0.7214}$$. Assuming convergence, $$\mathbb{P}[1000000] \approx \textbf{0.7214}$$

from functools import lru_cache
from math import comb

def prob_luckiest_coin(n):
@lru_cache()
def prob(n):
if n == 1:
return 1
else:
total_prob = 0
for i in range(1, n):
total_prob += prob(i)*comb(n,i)
print(prob_luckiest_coin(100))