Given that you started with one chip, what is the probability that you will win this game?

Question

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 three chips, you win. What is the probability that you will win this game?

My attempt is:

Let $p$ be the probability that you win. If you throw two heads in a row ($\frac{1}{4}$ probability of this happening), then you win the game. If you throw heads and then tails ($\frac{1}{4}$ probability of this happening), then you start over (and hence probability of you winning the game is $p$ at this point). So setting up the recursion gives

$$p = \frac{1}{4} + \frac{1}{4}p \implies \frac{3}{4}p = \frac{1}{4} \implies p = \frac{1}{3}$$

Is it correct?

Answer 1

Here is a more pedant answer...

The game has a model given by the following Markov chain with states $0, 1, 2, 3$ (naturally associated to the number of coins we have in the hand):

       1/2        1/2        1/2
     <----      <----      <---- 
 [0]       [1]        [2]        [3]
 LOSE     START                  WIN
      ---->      ---->      ---->
       1/2        1/2        1/2

and we make the states $0$, $3$ absorbant, to have a chain. (So once in $0$ we remain in $0$, once in $3$ we remain in $3$.)

Let $p_k$ be the probability to reach $3$ before $0$, when being in the state $k$.

Of course, $p_0=0$, and $p_3=1$. Then we have the following linear system of equations: $$ \left\{ \begin{aligned} p_0 &=0\ ,\\ p_1 &= \frac 12p_0+\frac 12p_2\ ,\\ p_2 &= \frac 12p_1+\frac 12p_3\ ,\\ p_3 &= 1\ . \end{aligned} \right. $$ The solution is $\boxed{\ p_1=1/3\ }$ and $p_2=2/3$.

Answer 2

This is call the Gambler's Ruin problem, and there is a very neat, and somewhat technically advanced solution via martingales. Without going into technical details, the main ideas are:

• Each flip is fair, so the entire game is fair. You start with $1$ chip, your expected value is still $1$ chip after every flip, and your expected value is still $1$ chip at "game end".

• There is a technical detail concerning how to define game end (called the stopping rule), but trust me that the detail works in your case, where the game ends when you have $0$ or $3$ chips.

• Since your expected value at game end must be $1$ chip, we have:

$$P(\text{end at $0$ chip}) \times 0 + P(\text{end at $3$ chips}) \times 3 = 1$$

which immediately gives $P(\text{end at $3$ chips}) = \frac13$. The neat thing is that this solution works for other boundaries (i.e. other definitions of "game end"). E.g. if your game starts at $1$ chip and ends at $-5$ or $+11$ chips, then $P(\text{end at $11$ chips}) = {6 \over 16} = \frac38$. Obviously you could have gotten the same answer with a Markov Chain / set of recurrences, but this is much faster.

Some more details here and here -- and I could have sworn I have seen some online course notes for exactly this treatment.