Probability that $A$ need more coin tosses to get two consecutive heads than $B$ need to get three consecutive heads Two people $A$ and $B$ throw fair coins independently. Let $M$ be the number of coin tosses until $A$ gets two consecutive heads. Let $N$ be the number of coin tosses until $B$ gets three consecutive heads. What is the probability that $M>N$?
 A: I can provide answers from three perspectives. The Markov way, the naive way as well as the programming/simulation way.
The Markov way is almost the same with the first answer (he did an excellent job except for some small errors regarding the boundary conditions) so I am basically rephrasing his set-ups. The point here is to find out the transitions between different "states", and the probabilities associated with that states will have corresponding relations. We denote an ordered pair $(m, n)$ the state where A is now having a run of $m$ Heads and B is having a run of $n$ Heads. Next we will toss to see what states A and B will falling in. They can fall in the $(0, 0)$ state if both have a Tail toss, or $(m+1, n+1)$ state if both have Head toss, or $(m+1, 0)$ for a HT toss, and $(0, n+1)$ with a TH toss. Thus we obtained a transition matrix, and the probability associated on those states are related corresponding to those transition probabilities. The equation he built up:
$$
P(m,n)=\biggl(\frac{1}{4}P(m+1, n+1)+P(m+1,0)+P(0,n+1)+P(0,0)\biggr)
$$
says if I start from state $(m,n)$, my probability of success is the sum of probabilities that I move to different states and succeed there. Notice that we also have the corner cases (boundary conditions): if $n\geq3,\,m<2$, then $P(m,n)=1$ because B already encounters HHH; if $m\geq2$, $n\leq3$ then $P(m, n)=0$ because this means A encounters HH no later than B encountering HHH. Combing them together you should be able to obtain a linear system and solve to get the result.
The naive way is rather straightforward. We denote by $X$ the number of tosses for A to get a HH, and $Y$ the number of tosses for B to get a HHH. Then 
$$
P(X>Y) = \mathop{\sum}_{k=1}^{\infty} P(X>k| Y=k)P(Y=k)
$$
Since $X$ and $Y$ are independent, we have
$$
P(X>k|Y=k)=P(X\geq k)=\mathop{\sum}_{m = k+1}^{\infty}P(X = m)
$$
So
$$
P(X>Y) = \mathop{\sum}_kP(Y=k)\mathop{\sum}_{m=k+1}^{\infty}P(X=m)
$$
It suffices to find out the probability distribution of $X$ and $Y$. This can again be solved by the Markov chain method, or conditional expectation. I will take $X$ as an example. We have
$$
p_n = P(X = n) = P(T)\cdot P(X = n-1)+P(HT)\cdot P(X = n-2)=\frac{1}{2}p_{n-1}+\frac{1}{4}p_{n-2}
$$
with $p_1 = P(X = 1)=0,\,p_2 = P(X = 2) = \frac{1}{4}$.
It then suffices to find out $p_n$ and similarly for $q_k = P(Y = k)$.
Finally the above method can be further verified by either accurately computed or simulated using C++ or Python/Matlab/Julia. I won't paste the code here but can provide to whoever interested in it.
PS: Forgot to mention but the result should be $\frac{361}{1699}$, or $0.2124$ by simulation.
A: I guess from my attempt of solution, that we cannot get a simple answer for the question. My idea is the following:
Let $a_n$ and $b_n$ be the probabilities that $A$ does not get two consecutive heads with $n$ tosses, with a sequence of tosses ending in heads and tails, respectively. We then have the following recurrence relations:
$$\left\{ \begin{array} \\a_n=\frac{b_{n-1}}{2} \\ b_n=\frac{a_{n-1}+b_{n-1}}{2}\end{array}\right.$$
Together with $a_1=b_1=1/2$, this can be solved to get $a_n$ and $b_n$. To find the probability $P_A(n)$ of $A$ getting the two consecutive heads in the $n^{th}$ toss, we just do $P_A(n)=\frac{a_{n-1}}{2}$.
By a similar argument, we can get recurrence relations for $B$, and find the probability $P_B(n)$, but the explicit results seem too complicated, from a solution using Mathematica.
Finally, with this in hand, the probability $P$ that $A$ need more tosses than $B$ is given by
$$P=\sum_{j>k}P_A(j)P_B(k)$$
