Probability: tossing an unfair coin

Question

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}}.\]

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.