A coin lands on heads at a probability $p\in\left(0,\frac12\right)\cup\left(\frac12,1\right)$ when tossed. We continue to toss the coin until we get head-head-head or head-tail-head in a row. Find the probability of ending at head-head-head.

I assumed that the probability that the last two tosses

  • are head-head but we don't stop is $A_n$.
  • are tail-head but we don't stop is $B_n$.
  • are tail-tail but we don't stop is $C_n$.
  • are head-tail but we don't stop is $D_n$.

We have $n\ge3$, \begin{cases}A_n=pB_{n-1},&(1)\\\\B_n=pC_{n-1},&(2)\\\\C_n=(1-p)C_{n-1}+(1-p)D_{n-1},&(3)\\\\D_n=(1-p)A_{n-1}+(1-p)B_{n-1}.&(4)\end{cases}

I now have a solution, but the method differs from lulu's:

Plug $(1)\to(4)$, $(2)\to(3)$, \begin{cases} D_n=(1-p)B_{n-1}+p(1-p)B_{n-2},\\[1em]\frac1pB_{n+1}=(1-p)D_{n-1}+\frac{1-p}pB_n. \end{cases} Hence, for $n\ge5$, \[B_{n+1}=(1-p)B_n+p(1-p)^2B_{n-2}+p^2(1-p)^2B_{n-3}.\] Now consider \[\sum_{n\ge5}B_{n+1}\!=\!(1-p)\sum_{n\ge5}B_n\!+\!p(1-p)^2\sum_{n\ge5}B_{n-2}\!+\!p^2(1-p)^2\sum_{n\ge5}B_{n-3}.\] Let $s=\sum\limits_{n\ge2}B_n$. Now \begin{align}s\!-\!B_2\!-\!B_3\!-\!B_4\!-\!B_5=\begin{aligned}s(1-p)\!-\!(B_2+B_3+B_4)(1-p)\\\\+sp(1-p)^2\!-\!B_2~p(1-p)^2\!+\!sp^2(1-p)^2.\end{aligned}\tag5\end{align} Since \[B_2=p-p^2,~B_3=p+p^3-2p^2,~B_4=p-2p^2+p^3,\] Solving $(5)$ gives \[\sum_{n\ge2}B_n=s=\frac{1+p^4-p^3-p^3}{p+p^2-p^3}.\] So \[\mathrm P(\text{HHH})=p\sum_{n\ge2}A_n=pA_2+p^2\sum_{n\ge2}B_n=\boxed{\frac{p}{p+1-p^2}}.\]


1 Answer 1


We can do it with states, labeling states according to how much of a useful string we have built. As active states we have the starting state, $S_0$ (in which we aren't in one signficant string or another) and we have the state $S_H$ (where the last meaningful toss was $H$), $S_{HH}$, $S_{HT}$. Note that $S_T,S_{TT}$ are the same as $S_0$ Let $P_X$ be the probability of winning (i.e. ending in $HHH$) if you are in state $S_X$ (so the answer we want is $P_0$).

For example, $P_0=P_H$ since any initial run of $T's$ is irrelevant and we will eventually get to an $H$ (unless $p=0$, in which case there is no end to the game).

Then $$P_0=pP_H+(1-p)P_0\quad P_H=pP_{HH}+(1-p)P_{HT}$$ $$ P_{HT}=p\times 0+(1-p)P_0\quad P_{HH}=p\times 1 +(1-p)P_{HT}$$

All of which implies that $$P_0=\frac p{-p^2+p+1}$$

Note that of course the system degenerates if $p=0$.

Also: I strongly suggest checking the algebra, I did it quickly. As a cheap sanity check, taking $p=1$ gives $P_0=1$ as it should. As another sanity check, this expression runs from $0$ to $1$ as $p$ does.

  • $\begingroup$ Which tosses are "meaningless" do you mean? $\endgroup$
    – youthdoo
    May 28 at 10:12
  • $\begingroup$ Anything that doesn't add to a string. If, say, the string was $TTHHTTH$ we'd be in $S_H$. The point of the states is to record how much of a useful string we have built (if any). $\endgroup$
    – lulu
    May 28 at 10:14
  • $\begingroup$ I note that Wolfram Alpha agrees with my solution (which of course assumes that my recursions are accurate, but at least it checks the solution algebra). $\endgroup$
    – lulu
    May 28 at 10:18
  • 1
    $\begingroup$ The idea here: don't try to look at all the possible strings, that's a mess. In any situation, which hasn't ended yet, there is really only a small number of game states we might find ourselves in. These recur (in the same way the strings recur) and we can get a linear system out of that. $\endgroup$
    – lulu
    May 28 at 10:21
  • $\begingroup$ I felt a bit perplexed again when I recollected this solution, so would you mind explaining a bit more? My question is: why would the equations like $P_0=pP_H+(1-p)P_0$ hold regardless of how many times we have operated? $\endgroup$
    – youthdoo
    May 28 at 11:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .