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

gamblingprobabilityrecursion

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?

Best Answer

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

Related Question