GATE IT 2005 | Question: 32

Question

An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is

• A. $3$
• B. $4$
• C. $5$
• D. $6$

Comments

So if you get this "event" thing then its a lot simpler because here we need to take only one Event E instead of 3 event E,E1,E2. now further we know that E = 1/4 [ 2 + 1+E + 2 + 1+ E]  so exp = 3.

---

For better understanding:

E(HH) - No. of tosses to get consecutive heads

E(HH | H) - The expected number of additional<!--TgQPHd|||[]--> flips required to reach HH, given that your last flip was a Head

E(HH | T)- The expected number of additional<!--TgQPHd|||[]--> flips required to reach HH, given that your last flip was a Tail

 

*E(HH) = 1 +Pr(H) E(HH | H) + Pr(T) E(HH | T)   -----Equation 1

(1 for the first toss in which we can get Head or tail, Pr(H) E(HH | H) for if we get head in first toss then expectation of getting Head again, Pr(T) E(HH | T) for if we get Tail in first toss then expectation of getting HH somewhere)

=1+(0.5)E(HH|H)+(0.5)E(HH|T)

 

*E(HH | H)=Pr(H)(1)+Pr(T) [1+E(HH | T)]

(1 for we got head then this toss is winning of HH ,  [1+E(HH | T)] for the waste of toss due to getting tail and then additional flips to ger HH)

E(HH | H)= 1+(0.5)E(HH|T)    ------Equation 2

 

*E(HH | T) = Pr(H)[1+ E(HH | H)] + Pr(T) [1 +E(HH | T)

(0.5)E(HH|T)=1+(0.5)E(HH|H)  -------Equation 3

 

From Equation 3 and 2:

E(HH | H) = 4 and E(HH | T) =6 

Put these values in Equation ! : 

So, E(HH) = 6

 

Same for E(TT) : 6

 

Sample space: HH,TH,HT,TT

Now, Now No. of tosses required to get two same toss: 1/4 * E(HH) + 1/4 * E(TT) = 1/4 * 6 + 1/4 * 6  

= 3 Answer

 

https://youtu.be/--mxW3jDlGk?si=IbOiN0GjH4h9skPz --- Refer to this video for better understanding

 

---

Noise solution

 

 

 

Answer 1

Probability on each branch  $= x = \frac{1}{2}$

2nd toss onwards, each toss layer gives us two success. (i.e. HH event or TT event ) 

$$\begin{align} E &= \sum k.p(k) \\ &= 2.(2x^2) + 3.(2x^3) + 4.(2x^4) + 5.(2x^5) + ... \\ &= 2.\left [ 2x^{2} + 3x^{3} + 4x^{4} + 5x^{5} + .... \right ] \\ &= 2.\left [ \frac{x}{(1-x)^2 } - x \right ] \\ \\ &\text{ putting x = } \frac{1}{2} \ \ \text{ ;}\\ \\ &= 2.\left [ \frac{\frac{1}{2}}{\left(\frac{1}{2}\right )^2} - \frac{1}{2} \right ] \\ &=3 \end{align}$$

---

A very similar QS :

An unbiased coin is tossed repeatedly and outcomes are recorded. What is the expected no of toss to get HT ( one head and one tail consecutively) ?

 

Probability in each branch $=0.5$. I double circled the satisfying toss events.
While observing the diagram I noticed that, from 2nd toss onward our required event starts showing up. Additionally,

 1. in the $\text{2nd}$ toss (or the 3rd level) we have one satisfying case.
 2. in the $\text{3rd}$ toss (or the 4th level) we have two satisfying case.
 3. in the $\text{4th}$ toss (or the 5th level) we have three satisfying case.
 4. in the $\text{5th}$ toss (or the 6th level) we have four satisfying case.
 5. etc.

i.e. in the $\text{kth}$ toss we would have $(k-1)$ satisfying case.
So,

$$\begin{align} E(x) &= \sum_{k=2}^{\infty } k.P(k)\\\ &= \sum_{k=2}^{\infty } k.\left \{ (k-1)*(0.5)^k \right \}\\ &= \sum_{k=2}^{\infty } \left \{ (k^2-k)*(0.5)^k \right \}\\ \end{align}$$

Using geometric series identity : https://en.wikipedia.org/wiki/Geometric_series#Geometric_power_series

$$\begin{align} \sum_{k=2}^{\infty}k(k-1)x^{k-2} = \frac{2}{(1-x)^3}\ \ \text{for } |x| < 1 \\ \end{align}$$

In our case : $x = 0.5$ So,

$$\begin{align} E &= \sum_{k=2}^{\infty}k(k-1)x^{k} = x^2\sum_{k=2}^{\infty}k(k-1)x^{k-2} = x^2.\frac{2}{(1-x)^3} \\ \end{align}$$

putting $x = \frac{1}{2}$   ; we get $E = 4$

---

More example:

For consecutive two heads ; HH

By drawing the tree diagram we can find the following series :

 

$$\begin{align*} E &= \sum{k.P(k) } \\ &=2.(1.x^2) + 3.(1.x^3) + 4.(2.x^4) + 5.(3.x^5)+6.(5.x^6)+7.(8.x^7)+.....\infty\\ \end{align*}$$

Above series is a nice combination of AP , generating function and Fibonacci numbers !!!!

• AP terms can be handled by integration or differentiation
• Fibanacci Generating function is = $\begin{align*} \frac{1}{1-x-x^2} \end{align*}$

 $$\begin{align} &\Rightarrow \frac{E}{x} =2.(1.x^1) + 3.(1.x^2) + 4.(2.x^3) + 5.(3.x^4)+6.(5.x^5)+7.(8.x^6)+.....\infty\\ &\Rightarrow \int \frac{E}{x} .dx = 1.x^2+1.x^3+2.x^4+3.x^5+5.x^6+.....\infty \\ &\Rightarrow \int \frac{E}{x} .dx = x^2.\left ( 1.x^0+1.x^1+2.x^2+3.x^3+5.x^4+.....\infty \right ) \\ &\Rightarrow \int \frac{E}{x} .dx = \frac{x^2}{1-x-x^2} \\ &\Rightarrow \frac{E}{x} = \frac{\mathrm{d}}{\mathrm{d} x}\left [ \frac{x^2}{1-x-x^2} \right ] \\ &\Rightarrow \frac{E}{x} = \frac{2x(1-x-x^2)+(1+2x)x^2}{(1-x-x^2)^2} \\ &\Rightarrow E = x.\left \{ \frac{2x(1-x-x^2)+(1+2x)x^2}{(1-x-x^2)^2} \right \} \\ &\Rightarrow E = \frac{1}{2}.\left \{ \frac{2.\frac{1}{2}(1-\frac{1}{2}-\frac{1}{4})+(1+2.\frac{1}{2}).\frac{1}{4}}{(1-\frac{1}{2}-\frac{1}{4})^2} \right \} \\ &\Rightarrow E = 6 \\ \end{align}$$

Infact 2nd QS on HT can also be done in the above way using integration.

Correct Answer: $A$

Comments

Whoa...that HH variation came in GATE DA 2024

---

@strangelet_ So did you solve it ?

---

@dd, can you see the doubt below for the second case, where we want the sequence as head then tail (this is right?)?
so according to the sequence I tried the following thing 
 

a=1/4(2) it is for H then T 

b=(1+E)*1/4 it is for H then  H, I did 1+E because the first head Is wasted. Still, the second head can be used c= (1+E)*1/2 it is for T because when the tail comes we need to toss 2 times so we can consider restarting here where I am doing this wrong by adding a b c I am getting 5 as an answer but answer Is 4.

Answer 2

Answer is (A)

$E(X)= \sum X_{i} \times P_{i}$

Where X=no of tosses when you get successive HEAD/TAIL(only one is possible at a time though).

$P_{i}$=Probability that you get in $X_{i}$ tosses.

Now see solution:  

You need atleast 2 tosses to get 2 heads/tails. Now see if you throw twice probability to get 2 heads/tails is $\dfrac{1}{2}$ out of $4$ outcomes $[HT,HH,TH,TT].$

Similarly if you get result in $3rd$ toss that means you did not get in $2nd$ toss so favourable cases for this can be $THH$ and $HTT$ only out of total $8$ outcomes. So probability is $\dfrac{2}{8}=\dfrac{1}{2^{2}}.$

To generalize ,you can see that in every case you will have only two favourable cases and $2^{n}$ sample space. So for n th throw probability is $\dfrac{1}{(2^{n-1})}.$

Now coming to $E(X)= 2\times \dfrac{1}{2} + 3\times \dfrac{1}{4} + 4\times \dfrac{1}{8}+\ldots \text{till infinity}.$

See this is combined AP-GP, So multiplying E(X) by $\dfrac{1}{2}$ and subtracting from E(X).

$E(X)=2\times \dfrac{1}{2}+ 3\times {1}{4} +4 \times \dfrac{1}{8}+\ldots$

${0.5}\times E(X)=2\times \dfrac{1}{4} +3\times \dfrac{1}{8}+\ldots$

subtracting, we get $\frac{1}{2} \times E(X)= 1+\frac{1}{4}+\dfrac{1}{8}+\dfrac{1}{16}+\ldots$

${0.5} \times E(X)= 1+ \left(\dfrac{1}{4}\right)\div {\left(1-{0.5}\right)}= 1+\dfrac{1}{2} =\dfrac{3}{2}$             $\left(\frac{a}{1-r}\right)$

     $ E(x)= 3.$  

Comments

As all outcomes are independent of each other. If we failed in two tosses to get our desired result ( in case of TT ,HT ), it is same as we are starting totally new start

Yes your thinking process is right but the mistake you are making is that to continue tossing even after getting tail, as after getting the Tail in the first toss itself you should fresh start, as a result TT, TH cases never happens and doesnt needs to evaluated

 

---

@SUJITH' thanks brother 

 

 

 

 

---

I am falling into a similar trap. In @Honey badger's diagram where he drew TT with 2+E attempts, I also do the same thing because the tosses did take place actually so how can we disregard them and consider a "fresh start"? Do we not consider counting the attempts taken to reach TT or TH? I also observed that in some cases we add E and in some cases we add E-1 to the number of steps. For example in the same diagram for the TH path, the number of steps is written as 2+(E-1) , which makes sense as 2 attempts were wasted to reach TH but if we get one H now, then the we can subtract 1 from E. Clarity on when to add E and when to add E-1 will be helpful

Answer 3

Number of expected toss to get a head (or tail), E(H) = E(T) = 2

let the expected number of tosses to get two successive same outcome is e.

e = 1/2*(1+E(H)) + 1/2*(1+E(T))

e = 1/2*(1+2) + 1/2 *(1+2)

e = 3

 

Therefore correct answer would be (A).

 

Answer is right, but procedure is wrong.

Comments

Could you explain it a bit please !! I can't get your approach !!!

Thank You

---

Let the expected number of coin flips be x.

1. If first flip gives head and second gives tail then we have wasted 1 flip so need to do one more flip 

1/2 * 1/2 * (x+1)

2. If first flip gives head and second gives tail then we are done. (required 2 flips) So.

2(1/2 * 1/2)

3. If first flip gives tail and second head then wastage = 1 flip. (Same as 1st case)

1/2 * 1/2 * (x+1)

4. If both gives tail (same as 2)

2 (1/2*1/2)

so 

x = 2(1/2*1/2) + 1/2 *1/2 * (x+1) + 1/2 *1/2 *(x+1) + 2 * (1/2) * (1/2) 

x= 1 + (x +1 )/ 2

x= 3

---

why are we considering (pair of 2 tosses) flips here and not tosses seperately?

---

Explanation

Answer 4

Let the expected number of coin flips be X.

The case analysis goes as follows:

a. If the first and second flips are HH or TT then we are done. The probability of this event is 2*(1/4) = 1/2

and the total number of flips required is 2.

b.if the first and second flips are TH or HT then we wasted 2 flips. The probability of this event is 2*(1/4) = 1/2

and the total number of flips required is X+2.

Adding, the equation  we get -
X=1/2(2)+1/2(X+2)

solving equation we get X = 3

answer : 3

Comments

@puja

HT or TH is a fail

case HT = prob of H =1/2 and prob of T=1..therefore 1/2...here 2 flips wasted (X+2)

case TH = prob of t =1/2 and prob of H=1..therefore 1/2...here also 2 flips wasted(X+2)

so X = (X+2)*1/2* (X+2) *1/2...but here shouldnt it be (X+2)*1/2  +   (X+2)*1/2 ??

am not sure if my understanding is correct

---

@MIRIYALA JEEVAN KUMA 

 I think that in case of HT or TH , it has wasted 1 flip.  So it should be x+1 but not X+2.

---

How are you getting x=3???? Im getting 4 , where im wrong😣

Answer 5

This is going to be a long one. Let’s start.

Definition – $\bf{X}$ :- This is a random variable which denotes the number of tosses required to get two consecutive tosses with the same outcome.

$P(X=1) = 0$ . This is because we need atleast two tosses to get two consecutive tosses.

$(P(X=2)=$ {$H,H$} or {$T,T$} = $\frac{1}{2}$

Notice that for any sequence of coin tosses, if the last two outcomes are {$T,T$} or {$H,H$} then $\exists$ only one valid sequence for the preceding part of it. Hence for every value of $X$, there are only two valid sequences.

For example if ($X=5$) and the last two outcomes are the same, then the possibilities are : $\color{red}{xxx}TT$ and $\color{red}{xxx}HH$

There is only possibility for $\color{red}{xxx}$ for each of the outcomes, which are $\color{red}{HTH}TT$ and $\color{red}{THT}HH$ respectively. Otherwise, we’d get a smaller sequence with same outcomes which refutes our definition of $X$.

Therefore $P(X=n)=\frac{2}{2^n}=\frac{1}{2^{n-1}}$ …. $\bf{(i)} $ for $ n \geq 2 $

We know, $\bf{E[X]}= \sum_{x} x \times p(x)$

Let us denote $\bf{E[X]}$ by S.

$ S= P(X=1) \times 1 + P(X=2) \times 2+ …… $to $\infty$

$S= 0+ 2 \times \frac{1}{2^1} + 3 \times \frac{1}{2^2} + 4 \times \frac{1}{2^3}… $ to $\infty$ – $\bf(iii)$

$2S= 0+ 2 \times \frac{1}{2^1} \times 2 + 3 \times \frac{1}{2^2} \times 2 + 4 \times \frac{1}{2^3} \times 2… $ to $\infty$ -$(\bf{iv})$

Subtracting $\bf{(iv)}$ from $\bf({iii})$ we have :

$S= 2 + \frac{1}{2}+ (3-2)\frac{1}{2^2}+ (4-3)\frac{1}{2^3}+ \frac{1}{2^4} ….$ to $\infty$

$S= 2 + \frac{\frac{1}{2}}{1-\frac{1}{2}}=2+1=3$

Hence, the expected value $\bf{E[X]}$=3.

Answer 6

This can be solved using recurrence relation as follows:
Let X be the expected value of number of tosses until the outcomes of 2 tosses are same.
We win when outcomes are HH,TT and we lose when outcomes are HT,TH.

 

So Prob(win) = 1/2 and Prob(lose) = 1/2

In the case of winning after first coin is tossed it needs one more toss to win while in the case of lose, after tossing first time we need to toss X more times as we could not win.
This gives us a Recurrence relation as follows:

X = 1/2∗(1+1) + 1/2∗(1+X)
2X = 2+1+X
X = 3