A gambler has just lost all but one $1 in Vegas and decides to go for a walk. Unfortunately he gets hit by a bus but, having lived mostly a good life aside from the gambling, is shown God’s mercy and lands in heaven. They only have one type of gambling in heaven, it is a simple choice-free game with the following rules:
A coin is tossed. If it comes up tails, you lose $1. If it comes up heads, your entire bankroll is tripled.
The gambler only has the $1 he had on him when he died (turns out you keep your money when you go to heaven). Here is a possible outcome of his playing this game:
- $1 – H -> $3
- $3 – T -> $2
- $2 – H -> $6
- $6 – T -> $5
- $5 – T -> $4
- $4 – T -> $3
- $3 – T -> $2
- $2 – T -> $1
- $1 – T -> $0
And thus he is broke.
The question is this: starting with his $1, what is the probability he will live the rest of eternity broke in heaven? The alternative, presumably, is that he spends eternity doing what he loves most: gambling. Do all paths eventually lead to bankruptcy a la Gambler’s ruin, or is there a nonzero probability of playing forever?
You may leave your ideas in the comments, and I will post a solution in a few days.
Tripling is massive overkill. If you just add two on a positive result, the probability of dying is
p(n) = phi^(-n)
where phi is the golden ratio. This can be derived by solving the simple difference equation
p(n) = p(n-1)/2 + p(n+2)/2
@geoffreyirving, p(n) = 1 is another solution to that difference equation. How do you deal with that?
Domain theory. :)
More specifically, that solution corresponds to the case when running off to infinity is considered dying. Since there exists a valid solution that decays to zero at infinity, that must be the correct solution if we consider running off to infinity living. By contrast, if winning gets $1, p = 1 is the only solution in [0,1].
@geoffreyirving, I had a feeling that something like what you are talking about was going on, which is what attracted me to this problem. Can you recommend where to learn more about this application of domain theory, specifically in the case of probability (or otherwise not-too-distantly connected to this sort of problem)?
“Spectral analysis of Markov chains” are good keywords to start from, I think. If you rewrite the Markov chain in terms of its eigenvectors my intuition is that the countably infinite case isn’t fundamentally more complicated than the finite case where, say, if you reach n = 1000 you win (so that both 0 and 1000 become terminal states in the Markov chain).
From running https://gist.github.com/4076804, it looks like the probability of bankruptcy converges to 0.57477… GHC runs out of memory after the first 20 or so steps though, so this definitely isn’t a good way to solve it. ;-)
Yep, according to https://gist.github.com/4079727, it’s 0.57477536382958938 to machine precision (using the add-two rule as the pessimistic bound).
I’ve been trying to solve this using elementary probability theory and some creativity, but is this approach viable or should I be reading up instead?
Also, give me back my productive afternoon. :(
We called (a variant of) this the “Mana Screw + Krark’s Thumb” problem; here’s a link to a discussion, sadly without much math to back it up.
http://forums.mtgsalvation.com/showthread.php?t=355045
Where’s the promised “solution in a few days”?