5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mateus Sampaio Oct 21 '13 at 18:55
  • $\begingroup$ @MateusSampaio: It is said to be a finance job interview question... $\endgroup$ – minimax Oct 21 '13 at 19:20
  • $\begingroup$ So my attempt of solution might not be the one desired. $\endgroup$ – Mateus Sampaio Oct 21 '13 at 19:32
  • $\begingroup$ @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... $\endgroup$ – minimax Oct 21 '13 at 23:38
9
$\begingroup$

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.


Update: As pointed out in a comment, the above calculation finds the probability that $A$ gets two consecutive heads sooner than $B$ gets three consecutive heads; the original problem asks for the opposite. The correct boundary conditions for the original problem are that $A_{m,n}=1$ for $m<2$ and $n\ge 3$ and $A_{m,n}=0$ for $m\ge 2$ and $n\le 3$. The matrix equation becomes $$ \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 \\ 0 \\ 0 \\ 1/2 \\ 1/4 \end{matrix}\right), $$ The result becomes $A_{0,0}=\frac{361}{1699}\approx 0.2125$. The two results add to slightly less than one because there is a nonzero probability that both players hit their goals at the same time... this probability is $81/1699\approx 0.0477$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – minimax Oct 21 '13 at 21:37
  • $\begingroup$ 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. $\endgroup$ – Mateus Sampaio Oct 22 '13 at 0:18
  • $\begingroup$ I think your boundary condition is not correct. In fact we want $M>N$, which means states such as $(0,3)$ and $(1,3)$ should be accepted, and the probability of $M>N$ is 1 while $(2,0)$, $(2,1)$, $(2,2)$ and $(2,3)$ are 0. $\endgroup$ – Xuxu Oct 5 '16 at 0:10
  • 1
    $\begingroup$ @user52919: Of course, you're right. I calculated the probability that A got two heads in a row before B got three heads in a row; the question asked for the probability that A got two heads in a row after B got three heads in a row. I'm updating now. $\endgroup$ – mjqxxxx Oct 5 '16 at 18:23
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I understand everything except the the distributions at the end.To check (PX=n) is the probability that it took n tosses to get 2 heads in a row. Therefore P(X=n-1) is the prob of getting 2 heads after n-1 tosses surely the process finishes at n-1 in that case. Similarly if P(X=n-2) is the probability that you get 2 heads after n-2 tosses again the process should then terminate at n-2? $\endgroup$ – Bazman Nov 8 '17 at 16:45
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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