GATE CSE
First time here? Checkout the FAQ!
x
+15 votes
1.3k views

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

  1. 3
  2. 4
  3. 5
  4. 6
asked in Probability by Veteran (19.1k points)   | 1.3k views
3 ?? answer ?
Yes the given answer is 3.
Please explain the solution.

3 Answers

+21 votes
Best answer

Probability on each branch is = 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 is = $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*}$$

Uisng geommetric 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.

answered by Veteran (45.6k points)  
selected by
Nice explanation..:)
Can we do like this??

E be the expected number of tosses and assuming one coin has been tossed it can be anything head or tails.

next coin having same as previous one having 1/2 probability, we have done and needs 2 tosses.if not same that means wasted one toss so we need(E+1) tosses and probability also 1/2.

E=1/2 *(E+1) + 1/2 * (2) =3

correct me!

@Gabbar  to me it looks correct. 

@debashish nice explanation

thanks ! @Gabbar 

Nice explanation . Marvelous Presentation :)

+16 votes

Answer is (A)

E(X)= sigma(Xi * Pi)

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

Pi=Probability that you get in Xi 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 1/2 out of 4 outcomes HT,HH,TH,TT.

Similarlry 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 2/8= 1/square(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 1/(2^(n-1)).

Now coming to E(X)= 2* 1/2 + 3*1/4 + 4*1/8+........till infinity

See this is combined AP-GP, So multiplying E(X) by 1/2 and subtracting from E(X)

E(X)= 2*1/2 + 3*1/4 +4*1/8+............

0.5*E(X)=      2*1/4 +3*1/8+......

subtracting , we get 1/2 *E(X)= 1+1/4+1/8+1/16+.....

0.5 *E(X)= 1+ (1/4)/(1-0.5)= 1+1/2 =3/2               (a/1-r)

      E(x)= 3  

answered by Boss (7.2k points)  
Is there any way to generalize this method for n consecutive outcome of same type ? How to calculate expected number of tosses to get 3 consecutive outcome of same type ?

@suraj generalize 

(2n+1 -2)  

 

@Sandeep

E(X)= 2*1/2 + 3*1/4 +4*1/8+............

0.5*E(X)=      2*1/4 +3*1/8+......

subtracting , we get 1/2 *E(X)= 1+1/4+1/8+1/16+.....

On subtracting am not getting above..help anyone..Sometimes I think that I don't know even subtraction
+3 votes
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.
answered by Loyal (4.9k points)  
edited by
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

 

 

 

 

 



Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,063 answers
63,297 comments
24,169 users