This is very similar to the question I've just asked, except now the requirement is to gain $4$ chips to win (instead of $3$)
The game is:
You start with one chip. You flip a fair coin. If it throws heads, you gain
one chip. If it throws tails, you lose one chip. If you have zero
chips, you lose the game. If you have four chips, you win. What is the
probability that you will win this game?
I've tried to use the identical reasoning used to solve the problem with three chips, but seems like in this case, it doesn't work.
So the attempt is:
We will denote $H$ as heads and $T$ as tails (i.e $HHH$ means three heads in a row, $HT$ means heads and tails etc)
Let $p$ be the probability that you win the game. If you throw $HHH$ ($\frac{1}{8}$ probability), then you win. If you throw $HT$ ($\frac{1}{4}$ probability), then your probability of winning is $p$ at this stage. If you throw heads $HHT$ ($\frac{1}{8}$ probability), then your probability of winning $\frac{1}{2}p$
Hence the recursion formula is
$$\begin{align}p & = \frac{1}{8} + \frac{1}{4}p+ \frac{1}{8}\frac{1}{2}p \\
&= \frac{1}{8} + \frac{1}{4}p +\frac{1}{16}p \\
&= \frac{1}{8} + \frac{5}{16}p
\end{align}$$
Solving for $p$ gives
$$\frac{11}{16}p = \frac{1}{8} \implies p = \frac{16}{88}$$
Now, to verify the accuracy of the solution above, I've tried to calculate the probability of losing using the same logic, namely:
Let $p$ denote the probability of losing. If you throw $T$ ($\frac{1}{2}$ probability), you lose. If you throw $H$ ($\frac{1}{2}$ probability), the probaility of losing at this stage is $\frac{1}{2}p$. If you throw $HH$($\frac{1}{4}$ probability), the probability of losing is $\frac{1}{4}p$. Setting up the recursion gives
$$\begin{align}p & = \frac{1}{2} + \frac{1}{4}p+ \frac{1}{8}\frac{1}{2}p \\
&= \frac{1}{2} + \frac{1}{4}p +\frac{1}{16}p \\
&= \frac{1}{2} + \frac{5}{16}p
\end{align}$$
Which implies that
$$\frac{11}{16}p = \frac{1}{2} \implies p = \frac{16}{22} = \frac{64}{88}$$
Which means that probabilities of winning and losing the game do not add up to $1$.
So the main question is: Where is the mistake? How to solve it using recursion? (Note that for now, I'm mainly interested in the recursive solution)
And the bonus question: Is there a possibility to generalize? I.e to find the formula that will give us the probability of winning the game, given that we need to gain $n$ chips to win?
Best Answer
Let $p(n)$ be the probability that you win the game when you have $n$ chips in the pocket. Then $p(0)=0$, $\>p(4)=1$. Having $1\leq n\leq3$ chips one makes a further move, and one then has $$p(n)={1\over2}p(n-1)+{1\over2}p(n+1)\qquad(1\leq n\leq3)\ ,$$ so that $$p(n+1)-p(n)=p(n)-p(n-1)\qquad(1\leq n\leq3)\ .$$ These circumstances immediately imply that $p(1)={1\over4}$.