Probability question with coins Let's say A keep tossing a fair coin, until he gets 2 consecutive heads, define $X$ to be the number of tosses for this process; B keep tossing another fair coin, until he gets 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.
 A: 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? 
A: 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)$
