# One of two independent flip sequences reaches two heads simultaneously. What is the distribution of others tosses.

Two people start flipping fair coins. We wait for one of them to reach two heads in a row. When that happens, we look at the last two tosses of the other guy. The other guy might have HH, HT, TH and TT. Naively, we might think all of these four are equally likely. However, that would mean there is a 25% chance the two sequences would reach two heads simultaneously. Now that seems high and as a matter of fact is. If you look at the code here (method named get_loser_state_prob at the very end) -

https://github.com/ryu577/stochproc/blob/master/stochproc/competitivecointoss/simulation.py

you will see the distribution actually looks like this -

HH: 0.12 HT: 0.24 TH: 0.32 TT: 0.32

It's completely unintuitive to me why HT and TH should have different probabilities and the distribution in general is something I can't wrap my mind around. Can someone explain why we should expect -

1) HH should be the lowest

2) HT should be lower than TH

3) TH and TT should be roughly the same (since it's simulation, can't tell if they are exactly the same but certainly very close).

• The phrase "25% chance the two sequences would reach two heads simultaneously" is poorly defined. What you're describing is the chance that given that one of them reaches HH, the other one has as well. That is a very different thing altogether. – Monty Harder Oct 1 '18 at 20:04
• I said you would only think that if you are naïve :) – Rohit Pandey Oct 1 '18 at 21:37

## 4 Answers

In this answer a way to find the probabilities.

Let $$p$$ denote the probability at start position, let $$q$$ denote the probability under condition that in the first round a tail and a head are thrown and let $$r$$ denote the probability under condition that in the first round two heads are thrown.

If it concerns the probability on HH then:

• $$p=\frac14p+\frac12q+\frac14r$$
• $$q=\frac14p+\frac14q$$
• $$r=\frac14+\frac14p$$

Solving this we find $$p_{HH}=p=0.12$$.

If it concerns the probability on TH then:

• $$p=\frac14p+\frac12q+\frac14r$$
• $$q=\frac14+\frac14p+\frac14q$$
• $$r=\frac14p$$

Solving this we find $$p_{TH}=p=0.32$$.

If it concerns the probability on HT then:

• $$p=\frac14p+\frac12q+\frac14r$$
• $$q=\frac14p+\frac14q$$
• $$r=\frac12+\frac14p$$

Solving this we find $$p_{HT}=p=0.24$$.

If it concerns the probability on TT then:

• $$p=\frac14p+\frac12q+\frac14r$$
• $$q=\frac14+\frac14p+\frac14q$$
• $$r=\frac14p$$

Solving this we find $$p_{TT}=p=0.32$$.

Edit:

Let me expand on the first case. There $$3$$ states to be discerned: $$S_0,S_1,S_2$$ where the index denotes the number of heads that where thrown in the former round. At the start we are in position in $$S_0$$.

$$p$$ denotes the probability of the other guy ending with HH if we start in $$S_0$$, $$q$$ denotes the probability of the other guy ending with HH if we start in $$S_1$$ and $$r$$ denotes the probability of the other guy ending with HH if we start in $$S_2$$.

Starting from $$S_0$$ the probability to arrive in $$S_0$$ again (i.e. both throw tails) equals $$\frac14$$. The probalility to arrive in $$S_1$$ is $$\frac12$$ (one of them throws tails and the other throws heads). The probability to arrive in $$S_2$$ is $$\frac14$$ (both throw heads).

That gives us the equality:$$p=\frac14p+\frac12q+\frac14r$$

Starting from $$S_1$$ on a similar way there is probability $$\frac14$$ to return to $$S_0$$ and also probability $$\frac14$$ to stay in $$S_1$$. Next to that there is the probability of $$\frac12$$ that the game ends in such a way that not both end with HH.

That gives us the equality:$$q=\frac14p+\frac14q+\frac120=\frac14p+\frac14q$$

Starting from $$S_2$$ on a similar way there is probability $$\frac14$$ to return to $$S_0$$. Also there is a probability $$\frac14$$ that the game ends in such a way that both end with HH. Also there is a probability $$\frac12$$ that the game ends in such a way that not both end with HH.

That gives us the equality:$$r=\frac14p+\frac141+\frac120=\frac14p+\frac14$$

• I'm a little confused by where your equations come from - can you expand on that a bit? – Chris Oct 1 '18 at 12:30
• @Chris I have edited something to explain. – drhab Oct 1 '18 at 14:02
• Thank you so much! Its all a lot clearer to me now! :) – Chris Oct 1 '18 at 14:35
• You are very welcome. – drhab Oct 1 '18 at 17:41

Short inexact answer for intuition.

Let's say A got HH on throws $$n$$ and $$n+1$$. We know that player B didn't get HH on throws $$n-1$$ and $$n$$. This makes it a bit less likely that player B got H on throw $$n$$. So this explains why HH and HT are lower than TH and TT.

But what about HH vs. HT? To gain intuition, consider just both players tossing their coin twice, without any extra conditions. What is the probability that (a) both get HH, or (b) one gets HH and one gets HT? The answer to (a) is $$1/2^4$$ because there are 4 tosses that have to give a specific result. But the answer to (b) is actually twice that because there are two possible outcomes that give this result, as we didn't specify who gets a HH!

• But this suggests that the probabilities will be multiples of 1/16, which the accepted answer did not find. – Teepeemm Oct 1 '18 at 21:03
• @Teepeemm It was not my intention to suggest that. I started by saying this is "inexact" (meaning that the answer should not be treated as a literal answer to the question), the second paragraph doesn't say any numbers but just merely explains part of the phenomenon, and the third paragraph starts with "To gain intuition" followed by saying that we're not considering the original problem. Do you have any suggestions how I would make it clearer? – JiK Oct 1 '18 at 21:21
• Thanks you, great answer! – Rohit Pandey Oct 1 '18 at 21:50
• One question - the second part of your answer (HH vs HT) seems to suggest that even if we count randomly, P(HT) should be higher than P(HH). But, if you take two tosses at random, they are both 25%. Am I missing something there? – Rohit Pandey Oct 2 '18 at 18:37
• @RohitPandey If we both toss a coin twice, HH and HH can happen in only one way: all coins land heads ($p=1/16$). HH and HT can happen two ways: either I get HH and you get HT ($p=1/16$) or I get HT and you get HH ($p=1/16$). – JiK Oct 2 '18 at 19:59

So I actually double checked this because it seemed strange to me as well, but it is indeed true.

    result <- c()

for(iter in 1:10000){
temp <- TRUE
x1 <- rep(0,2)
x2 <- rep(0,2)
while(temp){
x1 <- x1; x2 <- x2
x1 <- rbinom(1,1,0.5); x2 <- rbinom(1,1,0.5)

if(sum(x1)==2){
result <- c(result,sum(x2))
temp <- FALSE
}else if(sum(x2)==2){
result <- c(result,sum(x1))
temp <- FALSE
}
}
}

> sum(result==2)/length(result)
 0.1164  ## Probs of HH
> sum(result==1)/length(result)
 0.565  ## Probs of HT or TH
> sum(result==0)/length(result)
 0.3186 ## Probs of TT


I think the basic reason for the asymmetry is because the fact the game ends on this round (as opposed to the previous round) means that both players had gotten at least one tails in the previous two rounds prior to the final round (otherwise the game would have ended the previous round).

This means that each player has a higher probability of getting two tails in the final round, since his last two throws prior to the final round must be one of $$HT, TH, TT$$ and cannot be $$HH$$.

Let $$X$$ be the last two throws of the loser before the final round, $$Y$$ be his final throw, and $$Z$$ his last two throws after the final round.

Then

$$P(Z = HH) = P(X = TH, Y=H)$$

Since no other combination gives him two heads at the end. But now consider the probability his last two throws are tails

$$P(Z = TT) = P(X=TT, Y=T) + P(X = HT,Y=T)$$

Similarly

$$P(Z = HT) = P(X=TH, Y=T)$$

$$P(Z = TH) = P(X=HT, Y=H) + P(X=TT,Y=H)$$

Hence there's a clear asymmetry between the probabilities of the final throw caused by the fact he must have at least one tails prior to the final throw.

Notice how the simulation show $$P(TH) > P(HT)$$, and the above has two summands for $$TH$$ but only one for $$HT$$!

The answers here are great and provide good intuition. I have another rough way to visualize one aspect of this phenomenon, so thought I'd share. We have four states (HH, HT, TH, TT). What does the transition matrix between them look like (maintaining order)?

$$\left( \begin{array}{cccc} .5 & .5 & 0 & 0\\ 0 & 0 & .5 & .5\\ .5 & .5 & 0 & 0\\ 0 & 0 & .5 & .5 \end{array} \right)$$

Notice how all the columns have exactly two .5's in them.

However, here we're saying that the losing sequence hasn't reached HH yet. If we think of HH as an absorbing state, this matrix looks like -

$$\left( \begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 0 & .5 & .5\\ .5 & .5 & 0 & 0\\ 0 & 0 & .5 & .5 \end{array} \right)$$ The first thing you notice is that the column corresponding to HT suffers. It now has one .5 instead of two of them.

And as others have pointed out, this is because only TH now can lead to HT (HH used to also lead to it, but we excluded it). While for TH and TT, there are still two states that can lead to them.

This is some intuition as to why HT is lower than the others. It also hints at why TH and TT have the same probabilities (though making a strict assertion based on this would be a stretch).