# 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$?

-
Is this problem asked in a book or similar, or you just made it out? I came out with an idea of solution, but is rather long. –  Mateus Sampaio Oct 21 '13 at 18:55
@MateusSampaio: It is said to be a finance job interview question... –  minimax Oct 21 '13 at 19:20
So my attempt of solution might not be the one desired. –  Mateus Sampaio Oct 21 '13 at 19:32
@MateusSampaio: I guess they probably just want you to try the markov approach, state that one can form a bunch of linear equations. no need to actually solve them... –  minimax Oct 21 '13 at 23:38

Let $A_{m,n}$ be the probability that player $A$ flips two consecutive heads before player $B$ flips three consecutive heads, given that $A$'s (resp. $B$'s) current run of heads has length $m$ (resp. $n$). Then $$A_{m,n}=\frac{1}{4}\left(A_{m+1,n+1} + A_{m+1,0} + A_{0,n+1}+A_{0,0}\right);$$ the boundary conditions are that $A_{m,n}=1$ for $m\ge 2$ and $n < 3$, and $A_{m,n}=0$ for $m \le 2$ and $n\ge 3$. You want to find $A_{0,0}$. The relevant six equations are: $$\begin{eqnarray} A_{0,0} &=& \frac{1}{4}A_{1,1} + \frac{1}{4}A_{1,0} + \frac{1}{4}A_{0,1} + \frac{1}{4}A_{0,0}\\ A_{0,1} &=& \frac{1}{4}A_{1,2} + \frac{1}{4}A_{1,0} + \frac{1}{4}A_{0,2} + \frac{1}{4}A_{0,0} \\ A_{1,0} &=& \frac{1}{2} + \frac{1}{4}A_{0,1} + \frac{1}{4}A_{0,0} \\ A_{1,1} &=& \frac{1}{2} + \frac{1}{4}A_{0,2} + \frac{1}{4}A_{0,0} \\ A_{0,2} &=& \frac{1}{4}A_{1,0} + \frac{1}{4}A_{0,0} \\ A_{1,2} &=& \frac{1}{4} + \frac{1}{4}A_{0,0}, \end{eqnarray}$$ or $$\left(\begin{matrix}3/4 & -1/4 & -1/4 & -1/4 & 0 & 0 \\ -1/4 & 1 & -1/4 & 0 & -1/4 & -1/4 \\ -1/4 & -1/4 & 1 & 0 & 0 & 0 \\ -1/4 & 0 & 0 & 1 & -1/4 & 0 \\ -1/4 & 0 & -1/4 & 0 & 1 & 0 \\ -1/4 & 0 & 0 & 0 & 0 & 1 \end{matrix}\right)\times\left(\begin{matrix} A_{0,0} \\ A_{0,1} \\ A_{1,0} \\ A_{1,1} \\ A_{0,2} \\ A_{1,2} \end{matrix}\right) = \left(\begin{matrix} 0 \\ 0 \\ 1/2 \\ 1/2 \\ 0 \\ 1/4 \end{matrix}\right),$$ assuming no typos. Further assuming no typos entering this into WolframAlpha, the result is $$A_{0,0} = \frac{1257}{1699} \approx 0.7398,$$ which at least looks reasonable.

-
It seems this one admits no easy solution like other coin toss problems. The idea is correct and answer seems reasonable, although I have not checked the details. –  minimax Oct 21 '13 at 21:37
Used Mathematica to check my solution and it gave the same result as yours (in a much more complicated way). It seems it's right. –  Mateus Sampaio Oct 22 '13 at 0:18

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)$$

-