You started with one chip. You need to get 4 chips to win. What is the probability that you will win?

Question

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?

Answer 1

This answer only addresses what's wrong with your recursion, since the other answers (both in this question and your earlier question) already gave many different ways to set up the right recursions (or use other methods).

The key mistake is what you highlighted. When you throw $HHT$, you now have $2$ chips. For the special case of this problem, $2$ chips is right in the middle between $0$ and $4$ chips, so the winning prob is obviously $\color{red}{\frac12}$ by symmetry. But you had it as $\color{red}{\frac12 p}$ which is wrong. Thus the correct equation is:

$$p = P(HHH) + P(HT) p + P(HHT) \color{red}{\frac12}= \frac18 + \frac14 p + \frac18 \color{red}{\frac12}$$

Answer 2

Let $p_0, p_1, \ldots, p_4$ be the probability of winning if you start with $0, 1, \ldots, 4$ chips, respectively. Of course, $p_0 = 0$ and $p_4 = 1$.

There are a few different ways to approach this question.

Start with $p_2$

This seems to be the approach you're asking for, but it's not the easiest approach.

To calculate $p_2$, consider what happens if the coin is flipped twice. There is a $1/4$ chance of getting $TT$ (instant loss), a $1/4$ chance of getting $HH$ (instant win), and a $1/2$ chance of getting either $HT$ or $TH$ (back to $p_2$). So we have

$$p_2 = \frac14 + \frac12 p_2,$$

which we can solve to find that $p_2 = 1/2$.

Now that we know $p_2$, we can directly calculate $p_1$ as the average of $p_0$ and $p_2$, which is $1/4$.

Examine the sequence

Notice that in the sequence $p_0, p_1, p_2, p_3, p_4$, each element (besides the first and the last) is the average of its two neighbors. This implies that the sequence is an arithmetic progression. Given that $p_0 = 0$ and $p_4 = 1$, we can use any "find a line given two points" method to find that for all $n$, $p_n = n/4$.

Conservation of expected value

I'm an investor and an advantage gambler (which are the same thing, really), so I like to think of things in terms of expected value.

I start the game with $1$ chip, and it's a perfectly fair game; in the long run, I am expected neither to lose nor to win. So if I play the game until it ends, the expected value of the game must be $1$ chip. (More detail is needed to make this argument formal, but it's sound.)

The value if I lose is $0$, and the value if I win is $4$, so the expected value can also be written as $(1 - p_1) \cdot 0 + p_1 \cdot 4$, which simplifies to $4 p_1$.

These two ways of calculating the expected value must agree, meaning that $4 p_1 = 1$, so $p_1 = 1/4$.

In general

The latter two of the above arguments can each be generalized to show that if you start with $a$ chips, and the game ends when you reach either $0$ or $b$ chips, then the probability of winning is $a/b$.

Answer 3

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