# Probability question with coins

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.

Calculate $Pr(X>Y)$

This problem seems not too difficult but I can't solve it.

Since the rvs are discrete and independent, the way I see it you need to find an expression for $P(X-Y>0)$:

$$\sum_{k=4}^{\infty}P(X=k \cap Y \leq k-1)= \sum_{k=4}^{\infty}P(X=k)P(Y \leq k-1)$$ and since events 'toss $k$ times to get 3 H in a row' are disjoint you immediately have $P(Y \leq k-1) = \sum_{j=3}^{k-1}P(Y=j)$. Can you handle from here?

• No, not really, I think it is a bit advanced level for me. – user010010001 May 16 '14 at 16:37
• write out the distribution of each rv, this will help. – Alex May 16 '14 at 16:56

Note that though the formula is simple, but getting the answer in simple form is tougher.

Let $a_n$ indicate the number of tosses which do not contain HH and $b_n$ indicate the number of tosses which end with HHH and do not contain that sequence anywhere before that.

The values are given by $a_n=a_{n-1}+a_{n-2},\; a_0=1,\; a_1=2$ and $b_n=b_{n-1}+b_{n-2}+b_{n-3},\; b_1=0,\;b_2=0,\;b_3=1$

Then, the probability is given by \begin{align*} \mathbb{P}(X>Y) &= \sum_{n=3}^\infty \, \frac{a_n}{2^n}\cdot \frac{b_n}{2^n} \end{align*}

Since the solution to second recurrence is messy, we must try to obtain a generating function for $a_n\times b_n$. Using a guessing routine from a computer algebra system, we see that it's \begin{align*} G(x) &= -\frac{{\left(x^{3} - 2 \, x^{2} + 3 \, x + 5\right)} x^{3}}{x^{6} - x^{5} + 2 \, x^{4} + 5 \, x^{3} + 4 \, x^{2} + x - 1}\\ \therefore \mathbb{P}(X>Y) &= G\left(\frac{1}{4}\right)\\ &= \frac{361}{1699} \approx 0.212477928193055 \end{align*}

which agrees with a simulation.

Also, the same question has been asked before: Probability that $A$ need more coin tosses to get two consecutive heads than $B$ need to get three consecutive heads , but the answer calculated nicely using recurrence seems to be for $\mathbb{P}(X<Y)$