Probability of getting 5 consecutive heads before 2 consecutive tails

[Master1022]

Homework Statement

Suppose we are flipping a fair coin. What is the probability that we observe a run of 5 consecutive heads before seeing a run of 2 consecutive tails.

Relevant Equations

Probability

Hi,

I was just having a go at this question, and I suppose I have two sub-questions:
1. Does my approach look correct?
2. If my approach is correct, is there a better approach than what I have done?

Original question: Suppose we are flipping a fair coin. What is the probability that we observe a run of 5 consecutive heads before seeing a run of 2 consecutive tails.

My approach:
Let $p_k$ be the probability of seeing 5 consecutive heads, given that we have seen $k$ consecutive heads so far. $k = -1$ means we have seen a tail and $k = -2$ means that we have seen two consecutive tails. Then I basically just set up a system of equations which basically take the form of: $p{k} = P(\text{get a head}) p_{k + 1} + P(\text{get a tail}) p_{0}$

$$p_{-2} = 0$$
$$p_{-1} = \frac{1}{2} p_{-2} + \frac{1}{2} p_{0} = \frac{1}{2} p_{0}$$

$$p_{5} = 1$$
$$p_{4} = \frac{1}{2} p_{5} + \frac{1}{2} p_{0} = \frac{1}{2} + \frac{1}{2} p_0$$
$$p_{3} = \frac{1}{2} p_{4} + \frac{1}{2} p_{0} = \frac{1}{2} p_{0} + \frac{1}{2} \left( \frac{1}{2} + \frac{1}{2} p_0 \right) = \frac{1}{4} + \frac{3}{4} p_{0}$$
$$p_{2} = \frac{1}{2} p_{3} + \frac{1}{2} p_{0} = \frac{1}{2} p_{0} + \frac{1}{2} \left( \frac{1}{4} + \frac{3}{4} p_0 \right) = \frac{1}{8} + \frac{7}{8} p_{0}$$
$$p_{1} = \frac{1}{2} p_{2} + \frac{1}{2} p_{0} = \frac{1}{2} p_{0} + \frac{1}{2} \left( \frac{1}{8} + \frac{7}{8} p_0 \right) = \frac{1}{16} + \frac{15}{16} p_{0}$$
$$p_{0} = \frac{1}{2} p_{-1} + \frac{1}{2} p_{1} = \frac{1}{2} \cdot \frac{1}{2} p_{0} + \frac{1}{2} p_{1} \rightarrow p_{0} = \frac{2}{3} p_{1}$$
which leads to:
$$p_{0} = \frac{2}{3} \left( \frac{1}{16} + \frac{15}{16} p_{0} \right) \rightarrow p_{0} = \frac{1}{9}$$

Does that seem correct? Are there more elegant ways to get to the answer? Perhaps I could use Markov chains, but that is not something I have really come across before to a large extent.

Any help would be greatly appreciated.

Extension: (this is a side note, not part of the main problem) I could see a pattern developing in terms of the equations for $p_4$, $p_3$, $p_2$, etc. which took the form: if we require $N$ consecutive heads in a row, then:
$$p_{k} = \frac{2^{(N - k)} - 1}{2^{(N - k)}} p_{0} + \frac{1}{2^{(N - k)}}$$
for $1 \leq k < N$. Then I may be able to generalize the form for $k < 0$ and then get to a general probability of 'getting N consecutive heads before M consecutive tails', but I will continue to develop this offline and post any updates

 

[anuttarasammyak]

Do you want to calculate probability to get five consecutive heads after two consecutive tails in total seven trials ? If so I think it is rather simple $2^{-7}$.

 

[PeroK]

Do you want to calculate probability to get five consecutive heads after two consecutive tails in total seven trials ? If so I think it is rather simple $2^{-7}$.

... moreover, every specific sequence has an equal probability of $2^{-7}$:

HHHHHTT
HTHTHTH
TTTTTTTT
HTTHTTTT
etc.

There are $2^7$ equally likely outcomes.

 

[Master1022]

Do you want to calculate probability to get five consecutive heads after two consecutive tails in total seven trials ? If so I think it is rather simple $2^{-7}$.

... moreover, every specific sequence has an equal probability of $2^{-7}$:

HHHHHTT
HTHTHTH
TTTTTTTT
HTTHTTTT
etc.

There are $2^7$ equally likely outcomes.

Thanks for the replies @anuttarasammyak and @PeroK . Perhaps I could have worded the question differently, but that is not what I was asking...

Imagine we are playing a game where we are flipping a fair coin. We will win if we see a sequence of 5 heads and we will lose if we see a sequence of tails. What is the probability that we win?

 

[PeroK]

Thanks for the replies @anuttarasammyak and @PeroK . Perhaps I could have worded the question differently, but that is not what I was asking...

Imagine we are playing a game where we are flipping a fair coin. We will win if we see a sequence of 5 heads and we will lose if we see a sequence of tails. What is the probability that we win?

What's your answer?

 

[PeroK]

My answer is that the probability that tails wins is $\frac{31}{34}$. And, I've written a simulation in Python that corroborates this: tails won 911,417 games out of one million.

 

[Master1022]

What's your answer?

I had the answer in the original post as $p_0 = p(\text{seeing 5 heads before 2 tails given that we had seen 0}) = \frac{1}{9}$. However, as I write this, I realized that I should not be going back to $p_0$, but should have $p_{-1}$ instead

 

[PeroK]

I've got a general formula for the probability that tails wins if we need $t$ tails in a row against $h$ heads in a row:
$$p = \frac{2^h - 1}{2^h + 2^t -2}$$
E.g. with $h = 5$ and $t = 2$ gives $$p = \frac{31}{32+4-2} = \frac{31}{34}$$

 

[PeroK]

I had the answer in the original post as $p_0 = p(\text{seeing 5 heads before 2 tails given that we had seen 0}) = \frac{1}{9}$. However, as I write this, I realized that I should not be going back to $p_0$, but should have $p_{-1}$ instead

I got confused by your solution. When you start there is neither a previous head nor tail. But, thereafter, there is always a run of at least one.

What is $p_0$ precisely?

 

[Master1022]

I got confused by your solution. When you start there is neither a previous head nor tail. But, thereafter, there is always a run of at least one.

What is $p_0$ precisely?

Apologies. So $p_0$ was the probability that we win the game (i.e. see 5 consecutive heads and not seeing two tails consecutively). Notationally, the 0 just meant the probability of winning the game, given that we had seen $k$, in this case 0, heads in a row currently.

When I changed my algebra, I got the same answer as you. My equations should have been:

$$p_{-2} = 0$$
$$p_{-1} = \frac{1}{2} p_{-2} + \frac{1}{2} p_{1}$$
$$p_{0} = \frac{1}{2} p_{-1} + \frac{1}{2} p_{1}$$
$$p_{1} = \frac{1}{2} p_{-1} + \frac{1}{2} p_{2}$$
$$p_{2} = \frac{1}{2} p_{-1} + \frac{1}{2} p_{3}$$
$$p_{3} = \frac{1}{2} p_{-1} + \frac{1}{2} p_{4}$$
$$p_{4} = \frac{1}{2} p_{-1} + \frac{1}{2} p_{5}$$
$$p_{5} = 1$$

Solving this leads to $p_0 = \frac{3}{34}$ which is 1 - your answer (and your answer was measuring the complement, so our answers agree!). Was there an easy way that you came about your formula?

 

[anuttarasammyak]

Imagine we are playing a game where we are flipping a fair coin. We will win if we see a sequence of 5 heads and we will lose if we see a sequence of tails. What is the probability that we win?

Let me restate it to confirm my understanding. We will make binary decimals by coin flipping

For examples

.01011111 stop. We win.

.010100 stop. We lose.

.010101010101... no stop. Don't we have to have a finite number of trial sequences N to decide NO CONTEST cases ?

Some obvious cases
N=0,1: No contest
N=2: We lose with probability of $2^{-2}$.
N<5: We do not win.
N=5: We win with probability of $2^{-5}$.

 

[PeroK]

Solving this leads to $p_0 = \frac{3}{34}$ which is 1 - your answer (and your answer was measuring the complement, so our answers agree!). Was there an easy way that you came about your formula?

I looked at the probability $p$ of tails winning, with $H_n$ being the probability that tails wins after a run of $n$ heads and $T_1$ being the probability that tails wins after a tail.
$$H_4 = \frac 1 2 T_1$$ $$H_3 = \frac 1 2 H_4 + \frac 1 2 T_1 = \frac 3 4 T_1$$ $$H_2 = \frac 7 8 T_1$$$$H_1 = \frac{15}{16}T_1$$ Also, we have $$p = \frac 1 2 T_1 + \frac 1 2 H_1 $$ $$T_1 = \frac 1 2 + \frac 1 2 H_1$$Which gives: $$T_1 = \frac{16}{17}, \ H_1 = \frac{15}{17}, \ p = \frac{31}{34}$$
Finally, as above, I was able to generalise this method:

I've got a general formula for the probability that tails wins if we need $t$ tails in a row against $h$ heads in a row:
$$p = \frac{2^h - 1}{2^h + 2^t -2}$$
E.g. with $h = 5$ and $t = 2$ gives $$p = \frac{31}{32+4-2} = \frac{31}{34}$$

 

[Office_Shredder]

Here's a different approach. I'm assuming your goal is to get the heads.

If you flip a heads, you then have a 1/16th chance of winning the game before a tails shows up. 15/16 of the time you flip a tails, you then have a 1/2 chance of losing the game, otherwise you're back to having a single heads.

So if you are currently sitting on one heads, if p is your probability of winning then
$p=\frac{1}{16}+ \frac{15}{16}\frac{1}{2} p$.
Which gives $p=\frac{2}{17}$

At the start of the game you have a 3/4 chance of even getting a heads before you lose the game, so your overall chance of winning is $\frac{3}{4} p=\frac{3}{34}$.

I think this approach generalizes and doesn't require writing out a matrix of state transitions.