±1-random walk from 5 until 20 or broke

Question

You play a game where a fair coin is flipped. You win 1 if it shows heads and lose 1 if it shows tails. You start with 5 and decide to play until you either have 20 or go broke. What is the probability that you will go broke?

Answer 1

You can use symmetry here - Starting at $5$, it is equally likely to get to $0$ first or to $10$ first. Now, if you get to $10$ first, then it is equally likely to get to $0$ first or to $20$ first.

What does that mean for the probability of getting to $0$ before getting to $20$?

Answer 2

Hint: for $0 \le n \le 20$, let $p_n$ be the probability that you go broke if you start with $n$ points. You have $p_0=1$ and $p_{20}=0$. For $0 < n < 20$ you have $$p_n = \frac{1}{2} p_{n-1} + \frac{1}{2} p_{n+1}.$$ Solve for $p_5$.

Answer 3

It is a fair game, so your expected value at the end has to be $5$ like you started. You must have $\frac 34$ chance to go broke and $\frac 14$ chance to end with $20$.

Answer 4

All answers so far are great but some readers seem to feel they lack an intuitive explanation - and perhaps the maths to back it up.

Consider that you have an equal chance of moving up or down along your two paths. $$P_{u} = P_{d} = \frac{1}{2}$$ And your path lengths up and down are:

$$L_{u} = |20 - 5| = 15 $$ $$L_{d} = |0- 5| = 5 $$ $$L_{u} = 3 L_{d}$$

Now we know we have to end up, whatever the route, having moved a total distance of $L_{u}$ or $L_{d}$.

We know the probability of getting to $0$ plus the probability of getting to $20$ has to be 1 with the same proportionality constant. The probability that you complete one path (ie reach $0$ or $20$) before the other one is completed depends on the pathlength of the competing process (ie the longer it takes for one outcome to occur the better the chances for the alternative). As such:

$$P_{0} \propto L_{u}$$

So, canceling the constant of proportionality, we get the probability of going broke as:

$$\frac{P_{0}}{P_{total}} = \frac{L_{u}}{L_{u}+L_{d}} = \frac{3L_{d}}{4L_{d}}=\frac{3}{4} $$ Where $P_{total} = 1$ so $P_{0} = \frac{3}{4}$