# The Problem

You start off with $N$ coins. All coins are fair and land heads with probability $p_f=0.5$, except one weighted coin which lands heads with a weight $p_w$.

When the game starts perform the following steps:

1. Flip each coin in play
2. If no coin flips heads the game ends.
3. Otherwise remove all coins that flipped heads from the game.
4. Flip all the remaining coins.
5. Repeat until no coin flips heads or all coins are removed from the game.

Assuming $n\leq N$ coins have been removed from the game, what is the probability that the weighted coin was removed? i.e. $$P(\text{ Weighted Coin Removed from Play } | \text{ } n \text{ Coins Removed }) = \text{???}$$

# My Approach

Initially my thought was that the game itself isn't really relevant and I can just look at a single trial of the game. We just need to look at the probability of flipping $n$ heads (where one of which is the weighted coin) over the probability of flipping $n$ heads.

For example, let's set $N=3$, $n=2$, $p_f=0.5$, and $p_w=0.1$.

Then the probability of flipping two heads where one of which is the weighted coin is

$$2p_wp_f(1-p_f) = 2(0.1)(0.5)(1-0.5) = 0.05.$$

And the probability of flipping two heads where one of which ISN'T the weighted coin is

$$(1-p_w)p_f^2 = (0.9)(0.5)^2 = 0.225.$$

So I would think the probability of having already removed the weighted coin once two coins are removed is

$$\frac{0.05}{0.05+0.225}\approx 0.182$$

But I wrote a sim that says it should be closer $0.166$, and I'm sure there's something wrong with my approach needs to take into account the game. Not really sure what I'm doing wrong, but I'm pretty sure I need to take into account the possibility of multiple turns of the game somehow.

• Why do you think you can just consider the 2 flipped coins like that? I.e. why do you think you do not need to take into account the possibility of multiple turns? You should make sure you have an answer to this question before trying your approach. – the4seasons Dec 19 '17 at 4:39
• Initially I figured that there are three ways of getting two coins out of the way (two ways of removing 1 weighted coin and 1 fair coin, and one way of removing 2 fair coins). So it would just be a matter of looking at the respective probability of getting to that result. Clearly multiple turns do matter, but I can't wrap my head around how to work it in. – Mason McElroy Dec 19 '17 at 4:47

$N=3, n=2, p_w=0.1$

In brackets are the explicit coin flips, for notation sake, first coin will always be weighted, following coins are fair.

Case 1: No coins flip heads. It does not matter since then 2 coins can't be removed. (TTT)

Case 2: All 3 coins flip heads. It does not matter either since having exactly 2 coins removed is already impossible. (HHH)

Case 3: 2 coins flip heads.
Probability the weighted coin flipped heads = ${2\choose1}(0.1)(0.5)(0.5)=0.05$ (HTH, HHT)
Probability the weighted coin flipped tails = $(1-0.1)(0.5)(0.5)=0.225$ (THH)

Case 4: 1 coin flip heads. Still possible to have 2 coins removed, but also possible to end game without removing 2 coins.
Probability the weighted coin flipped heads = $(0.1)(0.5)(0.5)=0.025$ (HTT)
Probability the weighted coin flipped tails = ${2\choose1}(1-0.1)(0.5)(0.5)=0.45$ (THT, TTH)

Case 4.1: Weighted coin removed.
Probability that 1 fair coin flips heads = ${2\choose1}(0.5)(0.5)=0.5$

Case 4.2: 1 fair coin removed.
Probability the weighted coin flipped heads = $(0.1)(0.5)=0.05$ (HT)
Probability the weighted coin flipped tails = $(1-0.1)(0.5)=0.45$ (TH)

Required probability = $\frac{0.05+0.025*0.5+0.45*0.05}{0.05+0.225+0.025*0.5+0.45*(0.05+0.45)}=\frac{0.085}{0.5125}=34/205=0.16585...$

• Okay, now I see why you need to consider each case differently. I was hoping a simple general solution was possible, but this looks like it's going to be more complex than I expected. I suspect it'll need to be turned into a markov chain. In either case, this should get me going in the right direction. Thanks! – Mason McElroy Dec 19 '17 at 5:38

Your "sudden death" rule 2. is terribly complicating the analysis, and I shall disregard it. Furthermore I'm assuming $N$ fair coins at the start.

The probability that a fair coin is still in the game after $r\geq0$ flips is $2^{-r}$. Therefore the number $N_r$ of fair coins still in the game after $r$ flips is binomially distributed: $$P\bigl[N_r=k\bigr]={N\choose k}\left(2^{-r}\right)^k\left(1-2^{-r}\right)^{N-k}\qquad(0\leq k\leq N)\ .\tag{1}$$ The probability that the weighted coin is still in the game after $r$ flips is $q^r$, where $q:=1-p_w\,$.

Now, if after $r$ flips you observe $m$ surviving coins you either have $m$ fair coins surviving (and the weighted coin is gone), or you have $m-1$ fair coins and the weighted coin surviving. For your question it therefore remains to solve a small problem in conditional probabilities, using the formula $(1)$.

Thank you to user the4seasons for helping me think about this question. After racking my brain on this for about a week now I still haven't found a closed form solution to this problem, but I have worked out a simple procedure for finding the answer by modeling the game as a Discrete Markov Process.

For the case $N=3, n=2, p_w=0.1$, the first step is to construct a transition matrix $T$ like so...

... where each row represents the probability of moving to the next state given the current state. For example, based on the matrix you can infer the probability of going from having 0 weighted coins removed and 1 fair coins removed, to having 0 weighted coins removed and 2 fair coins removed is 0.45.

From there we can observe the probability of being in each state in the process by matrix multiplication: $X_{i+1} = T' X_i$. Each column below represents a state $X_i$.

From here we can just observe the probability of removing two coins vs removing two coins where one is the weighted coin by summing the appropriate rows. Finally, we obtain our answer as $0.085 / (0.085 + 0.4275) \approx 0.1659$.