Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
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)$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.