Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In repeated tossing of a fair coin find the probability that $5$ consecutive tails occur before occurrence of $2$ consecutive heads.

My attempt: I tried to find the probability of non-occurrence of two consecutive heads in $n$ throws.

Let $a_{n}$ be the number of possibilities in which $2$ consecutive heads do not occur in $n$ throws.

I managed to find the recursion formula.

$a_{1}=2$

$a_{2}=3$

$a_{n}=a_{n-1}+a_{n-2}$

But I am not able to get a closed form of $a_{n}$.

Once $a_{n}$ gets determined it may be possible then to find probability of occurrence of $5$ consecutive heads

share|cite|improve this question
    
The solutions to your recurrence are basically the Fibonacci seqience, for which there is a closed form that I think will not be helpful. – André Nicolas Jan 19 at 1:19
    
Besides, I don't understand the last sentence- You want the probability of 5 consecutive tails, and I don't see how $a_n$ would lead you you that. – leonbloy Jan 19 at 1:40
    
@leonbloy Well you're doing better than me, I don't understand even the question. It's a unique nonrepeating 7-bit sequence, so the odds of it starting at any particular coin toss seems obviously 1 in 2^7, or 1 in 128. So the odds of it happening in any sequence of tosses is gonna be the same as rolling a 1 on a 128 sided dice, when rolling it (sequence length - 6) times. The minus six because the last 6 coin-tosses cannot start the sequence. So I don't get what's being asked. But then I'm bad at math. – Dewi Morgan Jan 19 at 5:31

A different approach: consider two independent geometric vars $X_1$ ,$X_2$, each of which measures the amount of trials until getting a success, in an experiment with prob. of success $p_1$ (resp $p_2)$

Then $$P(X_1 \le X_2)=p_1 + p_1 q_1 q_2 +p_1 (q_1 q_2)^2+\cdots=\frac{p_1}{1- q_1 q_2} $$

$$P(X_1 < X_2)=p_1 q_2 + p_1 q_2 q_1 q_2 +p_1 q_2 (q_1 q_2)^2+\cdots=\frac{p_1 q_2}{1- q_1 q_2} $$

We can consider each run of tails/heads such experiments, with $p_1=1/2^{5-1}=2^{-4}$, $p_2 =1/2$

Let $E$ be the desired event (run of 5 tails happens before run of 2 heads). Let $T$ be the event that the first coin is a tail. Then

$$P(E)=P(E|T)P(T)+P(E|T^c)P(T^c)=\\ =\frac{p_1}{1- q_1 q_2} \frac{1}{2}+\frac{p_1 q_2}{1- q_1 q_2} \frac{1}{2}=\\=\frac{1}{2} (1+q_2)\frac{p_1}{1- q_1 q_2} =\frac{3}{34} $$

In general

$$P(E)=\frac{2^h-1}{2^t+2^h-2}$$

Seeing that the final formula is so simple, I wonder if there is a simpler derivation.

share|cite|improve this answer
    
Upvoted (+1) after verification. – Marko Riedel Jan 19 at 4:55
    
@leonbloy: Instructive answer! (+1) – Markus Scheuer Jan 19 at 11:38
    
why is $p_{1}=\frac{1}{2^{5-1}}$ and not $\frac{1}{2^5}$. Similarly,should not $p_{2}=\frac{1}{2^2}$ instead of $\frac{1}{2}$ – Pankaj Sinha Feb 1 at 0:43
1  
@PankajSinha Each run of head (tails) has by itself a starting head (tail). That should not be counted. For example, (for $p_2$) the probability that a head run is of length at least 2 is $p_2 = 1/2$ (or one minus the probaiblity that the head run has length $1$) – leonbloy Feb 1 at 1:42
    
Can I say that to obtain a run of $5$ tails it is necessary to obtain $4$ tails whose probability is $\frac{1}{2^{-4}}$ and then for a run of $5$ tails to occur one tail may happen before $4$ consecutive tails occur or after these $4$ consecutive tails occur whose probability will be $\left(\frac{1}{2}+\frac{1}{2}\right)$ – Pankaj Sinha Feb 3 at 2:17

This problem can be solved using Markov chains. Unfortunatley, this approach requires a bunch of tiresome matrix manipulations. I won't work through the details for you, but instead outline of solution.

Define the following states $0$ : the ground state. $t_1$: 1 tail has occurred ... $t_5$: 5 tails have occurred $h_1$: 1 head has occurred $h_2$ : 2 heads have occurred.

Here $t_5$ and $h_2$ are your termination states - i.e your game ends when you reach either state. So basically, you need to the expected time of hitting first $t_5$ versus first hitting $h_2$.

Now, write down the transition probability matrix. It will look something like this: $$Pr[ 0 \rightarrow t_1] = 1/2$$ $$Pr[0 \rightarrow h_1] = 1/2$$ $$Pr[t_i \rightarrow h_1] = 1/2$$ $$Pr[t_i \rightarrow t_{i+1}] = 1/2$$ etc.

Next, solve the expectation relationships as follows.

Define $ \tau_{j,k}$ = time to go from state $j$ to state $k$.

then the expected time to go from the ground state to $t_5$ can be composed into the path taken at the first step, either via $t_1$ or $h_1$... $$ E[ \tau_{0, t_5} ] = 1+E[ \tau_{t_1, t_5} ]1/2 + E[ \tau_{h_1, t_5} ]1/2 $$

similarly the time to go from the 1-tail state $t_1$ to the final state $t_5$ can be broken down by intermediate paths: $$E[ \tau_{t_1, t_5} ]= 1+E[\tau_{t_2, t_5} ]1/2 + E[ \tau_{h_1, t_5}]1/2$$ $$E[ \tau_{t_2, t_5} ]= 1+E[\tau_{t_3, t_5} ]1/2 + E[ \tau_{h_1, t_5}]1/2$$ $$E[ \tau_{t_3, t_5} ]= 1+E[\tau_{t_4, t_5} ]1/2 + E[ \tau_{h_1, t_5}]1/2$$ $$E[ \tau_{t_4, t_5} ]= 1/2 + E[ \tau_{h_1, t_5}]1/2$$

and so on an so forth.

As I said, it's quite tedious, but it'll get you the solution as linear system of equations.

share|cite|improve this answer

Here is a slightly different proof which may be of interest although it is not as elegant as the one by @leonbloy.

Suppose we treat the problem of $t$ tails before $h$ heads.

Encoding this in a generating function with $u$ marking sequences of tails of length at least $t$ and $v$ sequences of heads of length at least $h$ and finally $w$ marking the final occurrence of $h$ heads and introducing

$$G_t(z) = z+z^2+\cdots +z^{t-1}+uz^t\frac{1}{1-z} \quad\text{and}\quad G_h(z) = z+z^2+\cdots +z^{h-1}+vz^h\frac{1}{1-z}$$

we obtain

$$H(z) = (1+G_t(z)) \left(\sum_{k\ge 0} G_h(z)^k G_t(z)^k\right) \left(1+z+\cdots+z^{h-1} + wz^h + z^{h+1}\frac{1}{1-z}\right).$$

Observe that when we remove the three markers $u,v$ and $w$ we obtain

$$Q(z) = \frac{1}{1-z} \left(\sum_{k\ge 0} \frac{z^k}{(1-z)^k} \frac{z^k}{(1-z)^k}\right) \frac{1}{1-z} \\ = \frac{1}{(1-z)^2} \frac{1}{1-z^2/(1-z)^2} = \frac{1}{(1-z)^2-z^2} = \frac{1}{1-2z}$$

which is good news because it means we have enumerated all $2^n$ possible bit strings of length $n.$

Now extracting coefficients we are interested in the series on $w$ which yields

$$H_1(z) = z^h (1+G_t(z)) \left(\sum_{k\ge 0} G_h(z)^k G_t(z)^k\right)$$

The next step is to discard those terms that have $v\ge 1$ (meaning an internal occurrence of $h$ heads) which yields on setting $v=0$

$$H_2(z) = z^h (1+G_t(z)) \left(\sum_{k\ge 0} \left(z\frac{1-z^{h-1}}{1-z}\right)^k G_t(z)^k\right).$$

Finally we need to compute $$H_3(z) = \left. H_2(z)\right|_{u=1} - \left. H_2(z)\right|_{u=0}$$

to remove those terms not containing a run of at least $t$ tails.

This yields

$$H_3(z) = z^h \frac{1}{1-z} \left(\sum_{k\ge 0} \left(z\frac{1-z^{h-1}}{1-z}\right)^k \left(\frac{z}{1-z}\right)^k\right) \\ - z^h \frac{1-z^t}{1-z} \left(\sum_{k\ge 0} \left(z\frac{1-z^{h-1}}{1-z}\right)^k \left(z\frac{1-z^{t-1}}{1-z}\right)^k\right).$$

This finally produces

$$H_3(z) = z^h\frac{1}{1-z} \frac{1}{1-z^2 (1-z^{h-1})/(1-z)^2} \\ - z^h\frac{1-z^t}{1-z} \frac{1}{1- z^2(1-z^{h-1})(1-z^{t-1}))/(1-z)^2} \\ = z^h \frac{1-z}{(1-z)^2-z^2 (1-z^{h-1})} \\ - z^h (1-z^t) \frac{1-z}{(1-z)^2- z^2 (1-z^{h-1})(1-z^{t-1})} \\ = z^h \frac{1-z}{1 - 2z + z^{h+1}} - z^h (1-z^t) \frac{1-z}{1 - 2z + z^{h+1} + z^{t+1} - z^{h+t}}.$$

We obtain the probability by setting $z=1/2$ which yields

$$\frac{1}{2^{h+1}} 2^{h+1} - \frac{1}{2^{h+1}} \left(1-\frac{1}{2^t}\right) \frac{1}{1/2^{h+1}+1/2^{t+1}-1/2^{h+t}} \\ = 1 - \frac{2^t-1}{2^{h+t+1}} \frac{1}{1/2^{h+1}+1/2^{t+1}-1/2^{h+t}} \\ = 1 - (2^t-1) \frac{1}{2^t+2^h-2} = \frac{2^t+2^h-2-(2^t-1)}{2^t+2^h-2} \\ = \frac{2^h-1}{2^t+2^h-2}.$$

share|cite|improve this answer
    
Nice approach! (+1) – Markus Scheuer Jan 19 at 11:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.