Consecutive Heads
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)
f(0,0) = 1/4[f(1,1) + f(0,1) + f(1,0) + f(0,0)]
f(1,1) = 1/4[f(0,2) + f(0,0)]
f(1,0) = 1/4[f(0,1) + f(0,0)]
f(0,1) = 1/4[f(1,2) + f(1,0) + f(0,2) + f(0,0)]
f(0,2) = 1/4[1 + f(1,0) + 1 + f(0,0)]
f(1,2) = 1/4[1 + f(0,0)]
Solving f(0,0) = 361/1699
\m/ \m/ Finally
2) For the second part, let the answer be x
x = 1/2*(1+x) + 1/4*(2+x) + 1/4*2 {i.e T + HT + HH}
So, x = 6
3) For the third part, let the answer be y
y = 1/2(1+y) + 1/4(2+y) + 1/8(3+y) + 1/8(3) {i.e. T + HT + HHT + HHH}
y/8 = 7/4
y = 14
Answer :)
Update (Nov 16, 2010): Solution to Part 1 added by me.
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)
f(0,0) = 1/4[f(1,1) + f(0,1) + f(1,0) + f(0,0)]
f(1,1) = 1/4[f(0,2) + f(0,0)]
f(1,0) = 1/4[f(0,1) + f(0,0)]
f(0,1) = 1/4[f(1,2) + f(1,0) + f(0,2) + f(0,0)]
f(0,2) = 1/4[1 + f(1,0) + 1 + f(0,0)]
f(1,2) = 1/4[1 + f(0,0)]
Solving f(0,0) = 361/1699
\m/ \m/ Finally
2) For the second part, let the answer be x
x = 1/2*(1+x) + 1/4*(2+x) + 1/4*2 {i.e T + HT + HH}
So, x = 6
3) For the third part, let the answer be y
y = 1/2(1+y) + 1/4(2+y) + 1/8(3+y) + 1/8(3) {i.e. T + HT + HHT + HHH}
y/8 = 7/4
y = 14
Answer :)
Update (Nov 16, 2010): Solution to Part 1 added by me.
I think Pratik you have not done the 1st part correctly. the recursion
ReplyDeletex(n)=1/2*x(n-1)+1/4*x(n-2) is not correct I think
I think Pratik the recursive relation for x(n) is not correct at all.
ReplyDelete@Pulkit..
ReplyDeleteI verified it. I think its correct.. Can you point out the mistake..
Since I made this solution, there is every possibility of a mistake. Can you show why I am wrong?
Interestingly for n consecutive heads, the expectation value is 2^(n+1) - 2. Might there be an even more elegant solution? :)
ReplyDelete@tejasvph...
ReplyDeletenice generalization.. Using the method to solve 2 and 3 part for a general n, we see that z = 2^(n+1) - 2...
thanx..
I am not really a math buff, but aren't (2,0) (2,1) (2,2) accepted states and (0,3) (1,3) (2,3) failure states?!
ReplyDeleteEither I do not get what you wrote down or you have it all mixed up in there?
:) Dude, Nothing is mixed up. You need to spend some time to understand this.
ReplyDelete"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"
X>Y succeeds when A reaches 2 "only after" B reaches 3 (as X and Y are number of tosses). So, (0,3) and (1,3) are accepted states and (2,0) (2,1) (2,2) (2,3) are failure states.
as per above discussion, for any arbitrary n, expected no. of trials to get n consecutve heads is a finite number.
ReplyDeletesurprisingly expected no. of trials to get heads =tails i.e. HT,TH,HHTHTT etc. is infinite. the same is true if we want no. of heads - no. of tails =n, for any n.
proof for the case H-T=1:
suppose n1 is expected no. of trials to get H-T=1. then
n1=1/2*1+1/2*(1+n1+n1)
i.e. n1=1+n1. so n1 is infinite.
above equaion is true becoz for the case we get H on first trial, we get term 1/2*1. If we get T on first trial, then note that H-T= -1 after first trial. So incrementally, in later trials, twice we must have H-T=1. thus we get term 1/2*(1+n1+n1).
Your calculation seems correct.
ReplyDeleteI have another solution for proving that expected number of tosses for equal number of heads and tails is infinite.
Also, intuitively, why is that surprising to you? In the state diagram for n heads, we have n+1 states, but in state diagram of heads=tails, we have infinite states. So, expected value in the second case was "expected" to be larger. Right?
The above method can be optimized to work in space complexity O(1). void productArray(int arr[], int n)
ReplyDelete{
int i, temp = 1;
/* Allocate memory for the product array */
int *prod = (int *)malloc(sizeof(int)*n);
/* Initialize the product array as 1 */
memset(prod,1,n);
/* In this loop, temp variable contains product of
elements on left side excluding arr[i] */
for(i=0; i=0; i--)
{
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i=0; i<n; i++)
printf("%d ", prod[i]);
return;
}
@Vipul:
ReplyDeleteint *prod = (int *)malloc(sizeof(int)*n);
Doesn't this mean O(n) space complexity?
Also, be careful with your memset(prod,1,n);
It may not work in the way you think ;) Actually this would fill your array with 16843009, using gcc compiler.
@SeineRiver
ReplyDeleteWe will always need prod array to return product array. See not other temp array was used.
If you don't want to see prod array getting malloced in the method, one can pass prod arry in method.
Hi Pratik, I am doubtful about your solution to the first question. I monte carloed it and get
ReplyDeleteP(X>Y) = 0.2720 +- 0.001
while your answer is
361/1699 = 0.2125
This is the simple matlab code for verification.
clear;
X = zeros(1,2);
Y = zeros(1,3);
truecases = 0;
mcnum = 1e6;
for mc = 1:mcnum,
for t = 1: 1e4,
X(1) = X(2);
Y(1) = Y(2); Y(2) = Y(3);
X(2) = rand(1)>0.5;
Y(3) = rand(1)>0.5;
if (~all(X)) && ( all(Y) ),
truecases = truecases+1;
break;
elseif all(X),
break;
end
end
end
truecases / mcnum
Hello Pratik, I have obsessed with your question 1 for a whole day. I think I got the answer: 3/11.
ReplyDeleteMy solution is inspired by my matlab code I posted yesterday. As you noticed I used two queues: X (2 bits), and Y (3 bits). The key thing is we do not need to think of the sampling history as a whole array, but only the most recent 2 or 3 bits. Because if there is anything of HH for X or HHH for Y, the experiment will stop earlier and we would not have the chance of keeping doing the experiment after that. At each time, we simply take a snapshot of the two queues and determine it the experiment can be stopped now.
Therefore we can use the equivalent problem:
There are two bowls. Bowl 1 (corresponding to X) has 4 balls (2^2, 3 black, 1 red) in it. Bowl 2 has 8 balls(2^3, 7 black, 1red) in it. Person A and B draws balls independently from the balls and see who draws the red ball first.
The solution is
\sum_{i^1}^{\infty} \frac{1}{8} (\frac{7}{8})^{i-1}(\frac{3}{4})^i
= 3/11 \approx 0.2727
(By the way, the error bond in my post yesterday is actually larger)
Clearly think my statement here is not rigorous, specifically because of my independent assumption of the queues' snapshots. However, intuitively it isn't a problem because all events for the queue is equally likely.
How do you think?
Hello HanChen, Thanks for your comment! Your solution is not correct, precisely because of the assumption that queues' snapshots are independent.
ReplyDeleteIf the problem were restated as:
A tosses a fair coin twice and B tosses a fair coin thrice. If A gets both heads, he wins. If B gets all three heads, he wins. Else, both play again. What is the expected number of plays? Then, your assumption is correct.
But in our case, its not true.
A queue snapshot is really dependent on the previous queue snapshot.
This is clearly evident from the state diagram solution.
You should actually run the monte carlo code again, with the correct problem statement and let us know.
Thanks. Hope that helps!
Hello Pratik, thank you for the reply. So I double checked my solution. I still believe the answer is 3/11
ReplyDeleteAlthough my independent assumption is definitely not true, every snapshot event is equally likely, making the equivalent problem holds. Also, the snapshot does NOT depend on the history. Because if the HH (or HHH) happened, it is already happened.
Also I rerun the code and the solution almost surely lies in [0.270 - 0.275]
If you still don't believe me, you may run the code or tell me where I am wrong in the code :)
"every snapshot event is equally likely, making the equivalent problem holds." - prove it!
ReplyDelete"Also, the snapshot does NOT depend on the history. Because if the HH (or HHH) happened, it is already happened." - Can you go to (TT, TTT) after (TH, TTT) in one step?
I disagree with the comment posted by chera . In my opinion the recursive equation to solve this would be :F(n) = F(n-1) + 1/2(1) + 1/2(1+F(n+1))
ReplyDeletewhere F(n) represents expected number of toss to get n more heads than tails.
I am uncomfortable with the notion of adding "n1+n1" , because the the expected function need not be linear , getting two more heads (after a tail) does not mean getting one more head twice
or f(n+1) != f(n) + f(1) or f(1) + f(n)
I have not solved the recursion though
My bad , In fact it turns out to be that n1+n1 (by chera) is indeed valid and can be substituted back into the recursion to prove n1 is infinite
ReplyDeleteIn your solution to the 1st part, 2nd recursion is as follows:
ReplyDeletef(1,1) = 1/4[f(0,2) + f(0,0)]
Isn't this incorrect? How can you go from f(0,2) to f(1,1) in a single step?
Shouldn't the correct expression for f(1,1) be: f(1,1) = 1/4[f(0,0)], as you can only be on a (1,1) state if you were previously on (0,0) state and both A&B got heads?
I have exactly the same doubt with the solution
DeleteI have exactly the same cincern
DeletePratik .. can you give a detailed explaination for all the 3 sub questions?
ReplyDeleteThis questions can be formulated as markov chain. Then using the state equations and expectation equations for each transition.
ReplyDelete1. Is very detailed and elegant in Pratik's solution.
2. Can be solved as a solution of the following linear equations:
\mu_{start} = 1 + \frac{1}{2}(\mu_{start} + \mu_{H})
\mu_{H} = 1 + \frac{1}{2}(\mu_{start} + \mu_{HH})
\mu_{HH} = 0 (absorption state)
Solving the above equations we get \mu_{start} = 6
3. Similarly the equations for the third are:
\mu_{start} = 1 + \frac{1}{2}(\mu_{H} + \mu_{start})
\mu_{H} = 1 + \frac{1}{2}(\mu_{start} + \mu_{HH})
\mu_{HH} = 1 + \frac{1}{2}(\mu_start + \mu_{HHH})
\mu_{HHH} = 0 (absorption state)
Therefore \mu_{start} = 14.