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.