Combinatorics: 3 heads in succession in 5 coin tosses, using inclusion exclusion

Question

This is a question from An Introduction to Probability Theory and Its Applications, Vol. 1 Chapter 4, and doing Question 3.

http://www.amazon.com/Introduction-Probability-Theory-Applications-Edition/dp/0471257087

Question: Find the probability that in five tossings a coin falls heads at least three times in succession.

Of course, one can solve this problem by:$P_3 = P_{[3]}+P_{[4]}+P_{[5]}$ where $P_{[i]}$ means getting exactly i heads in succession.

I'm trying to solve this using Inclusion-Exclusion Principle, and I'm stucked.

The way I'm thinking is using:$P_3 = S_3-S_4+S_5$ where $S_3$ means 3 consecutive heads show up in a sequence. This of course will include the 4 heads and 5 heads cases, and that's why there is $-S_4$ and $+S_5$

So my way is: consider 3 consecutive coins are 1 single new coin. Now your total coins are shrinked by 2, i.e. you have 3 in total (with 1 special coin that represents a HHH )

Thus the question becomes $P_1 = S_1-S_2+S_3$ since my 3 consecutive coin is '1' coin.

Therefore $S_1 = \sum{p_i}={3\choose1}\times2^2=12,S_2 = \sum{p_{ij}}={2\choose1}\times2^1=4$ and $S_3 = \sum{p_{ijk}}={1\choose1}\times2^0=1$

This leaves a wrong answer as $P_1 = 12-4+1=9$ while correct answer is 8.

Guess my question is: My approach is probably wrong. How do I use Inclusion-Exclusion to solve this?

Thanks!

Answer 1

Think about the stretch of three consecutive heads, and where it occurs. It occurs in positions 1,2,3, or in positions 2,3,4, or in positions 3,4,5. These three possibilities are not mutually exclusive, which is why you need inclusion-exclusion. Let the above three events be denoted $E_1$, $E_2$, $E_3$. Then you want $$ P(E_1\cup E_2\cup E_3) = [P(E_1) + P(E_2) + P(E_3)] - [P(E_1\cap E_2) + P(E_2\cap E_3) + P(E_1\cap E_3)] + P(E_1\cap E_2\cap E_3). $$ Note that in the first group the probabilities are all the same (they're each equal to $\frac1{2^3}$), but in the second group they are not all equal: $P(E_1\cap E_2)=P(E_2\cap E_3)=\frac1{2^4}$, while $P(E_1\cap E_3)=\frac1{2^5}$. This is because in event $E_1\cap E_2$ and in event $E_2\cap E_3$, you've got four heads in a row, while in the last event you've got five heads in a row. Finally in the event $E_1\cap E_2\cap E_3$ you also have five heads in a row. Adding up, the total is $\frac8{2^5}$.

Answer 2

$P_3 = S_3-S_4$ you don't need to add $S_5$ back again. You subtracted $S_4$ because you double counted the sequences of 4 heads and the sequences of 5 heads. When you subtract $S_4$ you are removing the sequences of 4 heads and the sequences of 5 heads.... and you are done. I understand the motivation to want to add $S_5$ back in. But you have double counted the $S_5$ sequence in the calculation of $S_3$, and it still needs to go.