# ±1-random walk from 5 until 20 or broke [closed]

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?

• en.wikipedia.org/wiki/Gambler%27s_ruin Commented May 24, 2017 at 4:20
• Just for sake of showing a different way to approach the problem, here's a video on solving the Gambler's Ruin via Markov Chains: youtube.com/watch?v=afIhgiHVnj0 Commented May 24, 2017 at 4:24
• Must be a good question; I thought all the answers deserved upvotes. Commented May 24, 2017 at 11:53
• @PeterGreen In the strictest possible sense of all common usage, it means $\le 0$. But the gambler stops as soon as the condition is fulfilled. Since the gambler's pot starts at 5 and changes only in increments of 1, this means that the gambler can never go below zero in this particular problem. Commented May 24, 2017 at 20:04
• Why the massive upvotes for a question with no context, whose answer is all over the internet (not to mention, the horror, lectures on the subject)?
– Did
Commented May 27, 2017 at 9:17

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

• Two excellent answer with completely different approaches. And both on 67 upvotes! So of course I had to upvote both of them. Commented May 25, 2017 at 14:12
• I don't understand how an answer that asks the same question is an answer... Commented May 25, 2017 at 22:46
• @CramerTV It's a hint, intended to guide the user to the answer without connecting all the dots. Commented May 25, 2017 at 23:43
• In the spirit of "suggesting improvements" I would suggest including the answer in the answer. Things aren't always obvious to everyone. Commented May 26, 2017 at 0:25
• I generally try to avoid giving the answer right away, especially on a problem that could be a class assignment. Hints usually suffice and if not, you could always just ask in the comments. Commented May 26, 2017 at 14:00

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

• Very elegant! +1 Commented May 24, 2017 at 5:05
• It's not rigorous and not obvious (at least for me). But it IS elegant! Commented May 24, 2017 at 7:05
• More formally this is the Optional stopping theorem (en.wikipedia.org/wiki/Optional_stopping_theorem), which states that the expected value of a martingale, and hence a fair bet, is equal to the starting value. What you said is exactly the intuition behind the theorem. Good job
– NSZ
Commented May 24, 2017 at 7:59
• @lesnik: It is actually rigorous (and completely standard): fair game means that the gain process is a martingale, and when stopped at the stopping condition of the original post, is still a martingale by optional stopping (there is some boundedness to be checked). Therefore, the expected value of the stopped process at infinity must be 5, hence the claim Commented May 25, 2017 at 11:11
• I think it's even easier than that to make it rigorous (or make the rigorousness explicit: potato potahto). To prove that the expected value at the end is the same as the start, observe that since each toss is a "fair game" the inductive step is completely trivial: each toss in turn adds 0 to the expected value and hence does not change it. We don't need any machinery other than a proper definition of a fair game and knowing how expected values work. We might want to prove as well that the probability of never stopping is zero, which I guess is what Alexandre calls the boundedness. Commented May 25, 2017 at 11:32

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

• Yes, but you now have 21 equations for 21 unknowns. The amount of symmetry in the equations helps solve those equations, but possibly not for someone who needed to ask the question in the first place. Commented May 24, 2017 at 21:53
• @Teepeemm actually we can find the general term of the sequence using some linear algebra techniques or eigenvalue methods. So we do not have to solve 20 questions at all.
– Vim
Commented May 25, 2017 at 8:22
• I don't think solving these equations is intuitive. Having a solution method would help. Commented May 28, 2017 at 2:24

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

• @Teepeemm You're right! I had implemented that but my wording was terribly misleading. Thanks for pointing it out. I've added a bit of an explanation in case the statement wasn't clear. Commented May 28, 2017 at 12:41