David Ding: Riddler Classic February 18, 2022

From Gary Yane comes a question that launched a million flips:

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?

Let's look at a simple situation first. Suppose we only have two coins. What would be the probability that we would end up with a lucky coin? Suppose the probability exists, then let's denote it as \(p\). We have four cases after the first toss. Assuming a fair coin with independent tosses, we would arrive at four equally-likely outcomes: {HH, TH, HT, TT}. For the middle two cases with exactly 1H and 1T, we would have a lucky coin. For the last case, we don't have a lucky coin, and finally, for the first case, we repeat the tosses. Therefore, the probability of having a lucky coin can be written as:

\begin{align} p &= \frac{1}{4} p + \frac{1}{2} \\ \frac{3}{4} p &= \frac{1}{2} \\ p &= \left(\frac{1}{2}\right) \left(\frac{4}{3}\right) \\ p &= \frac{2}{3} \approx 0.67 \end{align}

I grouped the middle cases as either 2 heads 1 tail or 2 tails 1 head, both of which have three cases each. Again, the first case of HHH we repeat the process. We technically continue to repeat the process with the 2H1T cases, but we already know what the probability of having a lucky coin is--2/3 from our previous exercise. We get our lucky coin in the 1H2T cases, and finally, as usual, TTT does not yield a lucky coin. Putting everything together, the probability of having a lucky coin with three starting coins is:

\begin{align} p &= \frac{1}{8} p + \left(\frac{3}{8}\right) \left(\frac{2}{3}\right) + \frac{3}{8} \\ \frac{7}{8} p &= \frac{1}{4} + \frac{3}{8}\\ p &= \left(\frac{5}{8}\right) \left(\frac{8}{7}\right) \\ p &= \frac{5}{7} \approx 0.71 \end{align}

The coin toss process is memoryless, i.e. in each step it only matters how many coins remain to be tossed, and not how it got there.

This is why in our three-coin example, once we hit the 2H1T cases, we immediately know what the probability of having a lucky coin would be, as the analysis would continue into our two-coin example.

Extending To 1M Coins

The question becomes: how do we extend into the 1 million coins case? We first write out a recursive equation based on our previous observation. Let \(p(n)\) represent the probability of having a lucky coin while starting with \(n \geq 2\) coins. For example, \(p(2) = \frac{2}{3}\) and \(p(3) = \frac{5}{7}\), we then have, for the general case:

\begin{align} p(n) &= \frac{p(n)}{2^n} + \left(\frac{\binom{n}{n-1}}{2^n}\right) p(n-1) + \left(\frac{\binom{n}{n-2}}{2^n}\right) p(n-2) + \\ & \dots + \left(\frac{\binom{n}{2}}{2^n}\right) p(2) + \frac{n}{2^n} \\ \end{align}

The last term represents flipping \(n\) coins and getting the lucky coin immediately. Please note that \(\binom{n}{1} = n\).

\begin{align} p(n) &= \frac{1}{2^n - 1} \left[n + \sum_{k=2}^{n-1} \binom{n}{k}p(k) \right] \\ \end{align}

We can use recursive computer code to solve the problem. Given the magnitude of the coins, dynamic programming is needed to prevent stack overflows. Using MATLAB, we have:

   
function prob = luckyCoin (coin)
% Probability of having a lucky coin using dynamic programming, assuming
% the coins are fair and independent.

    global coinRes; %#ok

    % base case
    if coin <= 2
        prob = 2/3;
        if isempty(coinRes)
            coinRes(1) = 1;
            coinRes(2) = 2/3;
        end
        return;
    end

    % Take from memorized values
    if length(coinRes) >= coin
        prob = coinRes(coin);
        return;
    end
    
    % Recursion
    sumVal = 0;
    for k = 2:coin-1
       sumVal = sumVal + nchoosek(coin, k)*luckyCoin(k);
    end
    prob = (1/(2^coin - 1))*(coin + sumVal);
    coinRes(coin) = prob;
end

Of course, we still run into the precision problem as \(n\) grows to large values. Therefore, we plot the first few \(n\)'s using our algorithm and see if we observe any aymptotic behavior:

With about 100 coins, we see that the value quickly converges to about 0.7214. I hypothesize that the \(p(n)\)'s in fact do converge to 0.7214. Therefore, the probability that upon tossing 1 million coins yielding one lucky coin is about 72%.

Riddler Classic: February 18, 2022

Approach of the Lucky Coin

Extending To 1M Coins