Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially)

9/4?

ReplyDeleteBecause each extra coin, say ith, brings in 1/4 expected heads as i-1 coins will have 1/2 of the sequences ending in H thus 1/2*1/2(prob. of i = H) = 1/4 extra expected H

Thus for 10 coins, (10-1)/4

Please confirm if this is correct

@asad..

ReplyDeleteThis is the answer I wrote. But we were told that the answer is wrong.

I still feel that the answer is correct.Confirm it by running the following java program:

ReplyDelete/*

* To change this template, choose Tools | Templates

* and open the template in the editor.

*/

package javaapplication1;

import java.math.*;

import java.util.*;

/**

*

* @author anshum

*/

public class Main {

/**

* @param args the command line arguments

*/

public static void main(String[] args) {

int numberOfHH = 0;

boolean isLastFlipHead = false;

Random r = new Random();

for(int i = 1;i<10000000;i++)

{

isLastFlipHead = false;

for(int j=0;j<10;j++)

{

double a = r.nextDouble();

if(a<0.5)

isLastFlipHead = false;

else

{

if(isLastFlipHead)

numberOfHH++;

isLastFlipHead = true;

}

}

}

System.out.println( (double)numberOfHH/10000000.0);

// TODO code application logic here

}

}

It gives the answer as 2.25 approx

jaadu rocks!! Thanx for the code.

ReplyDeleteBut I am sure he said that the answer is wrong. :(

Will call someone in a few days and confirm.

i am bad at probability, but that's exactly the solution i just thought of.

ReplyDeleteJust confirmed with people who made the paper and interviewed me :P

ReplyDeleteThe answer 2.25 is correct. The solution I gave was not.

@asad.. Your solution is correct. Thanx

Let the expected number of HH for n tossed is E(n)

So, probability that an n-1 toss experiments, ends in T is 1/2.

So, E(n) = 1/2*E(n-1) + 1/2*( 1/2*(E(n-1)+1) + 1/2*(E(n-1)))

{

The first case when it ends in T.

The second case when it ends in H.

In the second case, if you get an H then, you get 1 more HH.

}

So, E(n) = E(n-1) + 1/4

E(2) we know is 1/4

So, E(n) = (n-1)/4

For n=10, E(10) = 2.25 :)

Thanx to Asad, Jaadu, Ramdas and Avin :)

Sol Using Linearity of Expectations ::

ReplyDeletelet X be the random variable denoting the number of HH's.

Let X_i be the indicator random variable which takes value 1 if H's occur in ith & (i+1)th positions, and 0 otherwise.

Note that each X_i is identically distributed, hence their expected values will be same.

E[X_i]= Pr( X_i = 1 ) = 1/4.

Now, X = X_1 + X_2 + .... + X_(n-1)

By Linearity of Expectation

E[X]=E[X_1]+E[X_2]+ ... +E[X_(n-1)]

E[X] = (n-1) E[X_1].

Hence, E[X] = (n-1)/4.

This can be done very easily.only possible pairs in the result can be HH,HT,TH,TT.And the expected number of occurrences of these must be equal as there is no reason for precedence for one over another.Therefore ans=(n-1)/4.

ReplyDelete