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?

  • 2
    $\begingroup$ I agree with your logic and answer. $\endgroup$ – JMoravitz Jan 8 at 15:41
  • 1
    $\begingroup$ You can check yourself by computing probability of loosing the game, using the same logic. $\endgroup$ – kludg Jan 8 at 15:50

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

  • $\begingroup$ Thanks for the response! I have one question. In the system of the equations you wrote $p_1 = \frac{1}{2}p_0 + \frac{1}{2}p_2$, which implies (if I get it correctly), that you can move from the zero state to the first state, with the $50\%$ probability. But don't we automatically lose when we have 0 chips? So I think, the formula for $p_1$ should be $p_1 = \frac{1}{2}p_2$. Or am I getting something wrong? $\endgroup$ – Nelver Jan 9 at 9:37
  • $\begingroup$ Yes, this is right, and in presence of $p_0=0$ it is the same as i wrote. My pedant writing was only trying to follow the general pattern, and in the same time suggest that we land from $1$ in one step either in $0$, or in $2$. $\endgroup$ – dan_fulea Jan 9 at 11:50

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.