34
$\begingroup$

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?

$\endgroup$

closed as off-topic by user21820, anomaly, Parcly Taxel, Did, user223391 May 29 '17 at 1:22

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user21820, anomaly, Parcly Taxel, Did, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    $\begingroup$ en.wikipedia.org/wiki/Gambler%27s_ruin $\endgroup$ – carmichael561 May 24 '17 at 4:20
  • $\begingroup$ 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 $\endgroup$ – Grey Matters May 24 '17 at 4:24
  • 1
    $\begingroup$ Must be a good question; I thought all the answers deserved upvotes. $\endgroup$ – JollyJoker May 24 '17 at 11:53
  • 2
    $\begingroup$ @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. $\endgroup$ – jpmc26 May 24 '17 at 20:04
  • 10
    $\begingroup$ 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)? $\endgroup$ – Did May 27 '17 at 9:17
139
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Two excellent answer with completely different approaches. And both on 67 upvotes! So of course I had to upvote both of them. $\endgroup$ – TonyK May 25 '17 at 14:12
  • 6
    $\begingroup$ I don't understand how an answer that asks the same question is an answer... $\endgroup$ – CramerTV May 25 '17 at 22:46
  • 7
    $\begingroup$ @CramerTV It's a hint, intended to guide the user to the answer without connecting all the dots. $\endgroup$ – jpmc26 May 25 '17 at 23:43
  • 7
    $\begingroup$ In the spirit of "suggesting improvements" I would suggest including the answer in the answer. Things aren't always obvious to everyone. $\endgroup$ – CramerTV May 26 '17 at 0:25
  • 7
    $\begingroup$ 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. $\endgroup$ – Michael Biro May 26 '17 at 14:00
133
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ Very elegant! +1 $\endgroup$ – Fimpellizieri May 24 '17 at 5:05
  • 18
    $\begingroup$ It's not rigorous and not obvious (at least for me). But it IS elegant! $\endgroup$ – lesnik May 24 '17 at 7:05
  • 9
    $\begingroup$ 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 $\endgroup$ – NSZ May 24 '17 at 7:59
  • 4
    $\begingroup$ @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 $\endgroup$ – Alexandre C. May 25 '17 at 11:11
  • 5
    $\begingroup$ 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. $\endgroup$ – Steve Jessop May 25 '17 at 11:32
25
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Teepeemm May 24 '17 at 21:53
  • 4
    $\begingroup$ @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. $\endgroup$ – Vim May 25 '17 at 8:22
  • 2
    $\begingroup$ I don't think solving these equations is intuitive. Having a solution method would help. $\endgroup$ – Starlight May 28 '17 at 2:24
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – FreeElk May 28 '17 at 12:41

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