# Probability: tossing an unfair coin

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}}.$

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.

• Which tosses are "meaningless" do you mean? May 28 at 10:12
• 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).
– lulu
May 28 at 10:14
• 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).
– lulu
May 28 at 10:18
• 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.
– lulu
May 28 at 10:21
• 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? May 28 at 11:16