6 ms·

Gambler’s Ruin Problem [pdf]

61 points by lawrenceyan 4y ago

Projectiboga 4y ago
Classic recursive or iterative problem that an undergraduate Statistics major needs to be able to derive directly not using formulas. Its wild how the chance of going broke is your money in bet units above both sides money at 50/50 and the odds go dramatically worse with any house edge.
- andirk 4y ago
  Is it because one can get ruined by hitting 0 but a "win" is subjective because there's no absolute upper bound? If one could go in to negative at 50/50 odds, then the game will dance around that $1 starting point forever?
  - hackerlight 4y ago
    If there's no absorbing states and it's the cumulative sum of infinite coin flip (-1, 1), it'll visit every integer an infinite number of times with probability 1 a.s..
    - andirk 4y ago
      So in real-world, the gambler would owe all the money in the world at some point. But also win all the money in the world at another point! And then cash out and he wins? Sounds beatable.
      - hackerlight 4y ago
        The gambler will owe all the money (and then some) with probability 1 a.s., but it's not guaranteed to happen because a.s. implies it's not a certainty.
- im3w1l 4y ago
  > Its wild how the chance of going broke is your money in bet units above both sides money at 50/50 It's actually quite simple. In a fair game you expect to leave with as much money as you started with. initial money = expected final money = p * all money
  - krackers 4y ago
    To be clear, the reason why expected final money is `p * all money` is because the only "absorbing states" are the win state and lose all money state, so it's `p * max money + (1 - p) * 0`, right? Also, it's not quite clear to me why in this case initial money = expected final money. For the related game where you go double-or-nothing on each bet, it's evident this holds since the expected value of your next turn is the same as your current (I believe it's called martingale property), but that doesn't hold for the game in the article where you win +1 or -1 unit each bet, since if you e.g. have 4 units and the win state is 5 units, you're more likely to win than lose. Edit: nevermind, I think it is a martingale since if you're at 4 units the expected value of the next state is 0.5*5 + 0.5*3 = 4. I guess my confusion stemmed from the fact that even though the long-term expected value is unchanged, you can still have good odds of winning (which is balanced by a small chance of a catastrophic loss), e.g. 4 = 0 * 1/5 + 5 * 4/5.
alpark3 4y ago
Studying for quant interviews lol
exolymph 4y ago
I am not math enough to begin to understand this paper but nonetheless I was instantly reminded of the Kelly criterion, which is super nifty: https://en.wikipedia.org/wiki/Kelly_criterion https://en.wikipedia.org/wiki/Kelly_criterion
- hansvm 4y ago
  The main difference is that Kelly has a multiplicative assumption and the paper has an additive assumption. The Kelly criterion is often computed as a proportion of the initial bankroll, whereas this paper handles non-zero chances of losing a _fixed_, positive amount of money (i.e., a varying proportion of your bankroll, and that proportion increases precisely when you would least want it to -- when you're doing poorly).
caiomassan 4y ago
the URL sends me to a object not found page
nramanand 4y ago
I studied Gambler's Ruin while taking probability as an undergrad (and studying to land a quanty job after college). For folks who enjoy these types of puzzles, another similar exercise that I spent an entire afternoon trying to solve was the following: You have 52 playing cards (26 red, 26 black). You draw cards one by one. A red card pays you a dollar. A black one fines you a dollar. You can stop any time you want. Cards are not returned to the deck after being drawn. What is the optimal stopping rule in terms of maximizing expected payoff? (source: http://puzzles.nigelcoldwell.co.uk/fourteen.htm http://puzzles.nigelcoldwell.co.uk/fourteen.htm)
- Dalewyn 4y ago
  From some quick "just several minutes" beer-laden kit bashing in my brain: 1. Draw 26 cards. 2a. Equal to or greater than $26? Stop. 2b. Less than $26? Draw 13 more cards. 3a. Equal to or greater than $1? Stop. 3b. Equal to or less than $0? Keep drawing until equal to $0, then stop. I'm assuming I want to always stop at a non-negative value, else I'd pay the house on the way out. If ending with a negative value has no consequences beyond the game itself, then just stop at 2b after drawing.
  - nramanand 4y ago
    Not sure I followed what you meant by >= $26 in 2a. The max profit one can make is $26, by drawing 26 red cards in a row, never more. You are correct though that you'd never want to stop on a negative number, as you always can execute 3b
    - chrchang523 4y ago
      For the same reason, you’d never intentionally stop at $0 (unless the deck is exhausted). You can always get back to $0 by drawing the rest of the deck, and there’s a 50% chance of going up a dollar on the next card.
      - Filligree 4y ago
        If your sum is currently positive, then the chance of going up a dollar is below 50%.
stevespang 4y ago
ffhhj 4y ago
Reminds me of the St. Petersburg paradox [0], which was one of the first problems I simulated in Python to learn the language. Pretty cool exercise. [0]: https://en.wikipedia.org/wiki/St._Petersburg_paradox https://en.wikipedia.org/wiki/St._Petersburg_paradox
LifeIsBio 4y ago
I recently came across the concept of Gambler’s Ruin in Taleb’s “Skin in the Game”. It’s… definitely written in Taleb’s style, but I’ve noticed myself relating all sorts of things back to the book recent. Worthwhile, overall. https://en.m.wikipedia.org/wiki/Skin_in_the_Game_(book) https://en.m.wikipedia.org/wiki/Skin_in_the_Game_(book)
CTDOCodebases 4y ago
This is relevant for trading and the reason why people adopt the 1% risk rule.
- max_ 4y ago
  What's the 1% risk rule?
  - CTDOCodebases 4y ago
    Never risk more than 1% of your capital. At any one time your position(s) size can be 100% of your capital but the most you can loose from the trade(s) is 1% of your capital. So after winning a trade(s) you increase the amount you are risking and after loosing you decrease the amount you are risking.
greenkiweez 4y ago
Studying CS a while ago, we had a very practical statistics and now I'm struggling to understand more theoretical proof-based papers like this one. Is there a good statistics/probability book out there to brush up on my statistics and understand papers like this better?
vital303 4y ago
Here is another solution. Assume a head multiplies your money by `r = q/p', and a tail divides by `r'. This bet is fair (the expected value of a dollar is a dollar: `p r + q 1/r = q + p = 1'). Start with a dollar, after several tosses you have `r^(head-tail difference)' dollars. The game ends if head-tail difference is `N - i' (with probability `x') or if head-tail difference is `-i' (probability is `1 - x'). The expected value is still a dollar: 1 = x r^(N - i) + (1 - x) (1/r)^i Solve this equation for x.

61 points by lawrenceyan 4y ago

Classic recursive or iterative problem that an undergraduate Statistics major needs to be able to derive directly not using formulas. Its wild how the chance of going broke is your money in bet units above both sides money at 50/50 and the odds go dramatically worse with any house edge.

andirk 4y ago
Is it because one can get ruined by hitting 0 but a "win" is subjective because there's no absolute upper bound? If one could go in to negative at 50/50 odds, then the game will dance around that $1 starting point forever?
- hackerlight 4y ago
  If there's no absorbing states and it's the cumulative sum of infinite coin flip (-1, 1), it'll visit every integer an infinite number of times with probability 1 a.s..
  - andirk 4y ago
    So in real-world, the gambler would owe all the money in the world at some point. But also win all the money in the world at another point! And then cash out and he wins? Sounds beatable.
    - hackerlight 4y ago
      The gambler will owe all the money (and then some) with probability 1 a.s., but it's not guaranteed to happen because a.s. implies it's not a certainty.
im3w1l 4y ago
> Its wild how the chance of going broke is your money in bet units above both sides money at 50/50 It's actually quite simple. In a fair game you expect to leave with as much money as you started with. initial money = expected final money = p * all money
- krackers 4y ago
  To be clear, the reason why expected final money is `p * all money` is because the only "absorbing states" are the win state and lose all money state, so it's `p * max money + (1 - p) * 0`, right? Also, it's not quite clear to me why in this case initial money = expected final money. For the related game where you go double-or-nothing on each bet, it's evident this holds since the expected value of your next turn is the same as your current (I believe it's called martingale property), but that doesn't hold for the game in the article where you win +1 or -1 unit each bet, since if you e.g. have 4 units and the win state is 5 units, you're more likely to win than lose. Edit: nevermind, I think it is a martingale since if you're at 4 units the expected value of the next state is 0.5*5 + 0.5*3 = 4. I guess my confusion stemmed from the fact that even though the long-term expected value is unchanged, you can still have good odds of winning (which is balanced by a small chance of a catastrophic loss), e.g. 4 = 0 * 1/5 + 5 * 4/5.

alpark3 4y ago

Studying for quant interviews lol

exolymph 4y ago

I am not math enough to begin to understand this paper but nonetheless I was instantly reminded of the Kelly criterion, which is super nifty: https://en.wikipedia.org/wiki/Kelly_criterion https://en.wikipedia.org/wiki/Kelly_criterion

hansvm 4y ago
The main difference is that Kelly has a multiplicative assumption and the paper has an additive assumption. The Kelly criterion is often computed as a proportion of the initial bankroll, whereas this paper handles non-zero chances of losing a _fixed_, positive amount of money (i.e., a varying proportion of your bankroll, and that proportion increases precisely when you would least want it to -- when you're doing poorly).

caiomassan 4y ago

the URL sends me to a object not found page

nramanand 4y ago

I studied Gambler's Ruin while taking probability as an undergrad (and studying to land a quanty job after college). For folks who enjoy these types of puzzles, another similar exercise that I spent an entire afternoon trying to solve was the following: You have 52 playing cards (26 red, 26 black). You draw cards one by one. A red card pays you a dollar. A black one fines you a dollar. You can stop any time you want. Cards are not returned to the deck after being drawn. What is the optimal stopping rule in terms of maximizing expected payoff? (source: http://puzzles.nigelcoldwell.co.uk/fourteen.htm http://puzzles.nigelcoldwell.co.uk/fourteen.htm)

Dalewyn 4y ago
From some quick "just several minutes" beer-laden kit bashing in my brain: 1. Draw 26 cards. 2a. Equal to or greater than $26? Stop. 2b. Less than $26? Draw 13 more cards. 3a. Equal to or greater than $1? Stop. 3b. Equal to or less than $0? Keep drawing until equal to $0, then stop. I'm assuming I want to always stop at a non-negative value, else I'd pay the house on the way out. If ending with a negative value has no consequences beyond the game itself, then just stop at 2b after drawing.
- nramanand 4y ago
  Not sure I followed what you meant by >= $26 in 2a. The max profit one can make is $26, by drawing 26 red cards in a row, never more. You are correct though that you'd never want to stop on a negative number, as you always can execute 3b
  - chrchang523 4y ago
    For the same reason, you’d never intentionally stop at $0 (unless the deck is exhausted). You can always get back to $0 by drawing the rest of the deck, and there’s a 50% chance of going up a dollar on the next card.
    - Filligree 4y ago
      If your sum is currently positive, then the chance of going up a dollar is below 50%.

stevespang 4y ago

ffhhj 4y ago

Reminds me of the St. Petersburg paradox [0], which was one of the first problems I simulated in Python to learn the language. Pretty cool exercise. [0]: https://en.wikipedia.org/wiki/St._Petersburg_paradox https://en.wikipedia.org/wiki/St._Petersburg_paradox

LifeIsBio 4y ago

I recently came across the concept of Gambler’s Ruin in Taleb’s “Skin in the Game”. It’s… definitely written in Taleb’s style, but I’ve noticed myself relating all sorts of things back to the book recent. Worthwhile, overall. https://en.m.wikipedia.org/wiki/Skin_in_the_Game_(book) https://en.m.wikipedia.org/wiki/Skin_in_the_Game_(book)

CTDOCodebases 4y ago

This is relevant for trading and the reason why people adopt the 1% risk rule.

max_ 4y ago
What's the 1% risk rule?
- CTDOCodebases 4y ago
  Never risk more than 1% of your capital. At any one time your position(s) size can be 100% of your capital but the most you can loose from the trade(s) is 1% of your capital. So after winning a trade(s) you increase the amount you are risking and after loosing you decrease the amount you are risking.

greenkiweez 4y ago

Studying CS a while ago, we had a very practical statistics and now I'm struggling to understand more theoretical proof-based papers like this one. Is there a good statistics/probability book out there to brush up on my statistics and understand papers like this better?

vital303 4y ago

Here is another solution. Assume a head multiplies your money by `r = q/p', and a tail divides by `r'. This bet is fair (the expected value of a dollar is a dollar: `p r + q 1/r = q + p = 1'). Start with a dollar, after several tosses you have `r^(head-tail difference)' dollars. The game ends if head-tail difference is `N - i' (with probability `x') or if head-tail difference is `-i' (probability is `1 - x'). The expected value is still a dollar: 1 = x r^(N - i) + (1 - x) (1/r)^i Solve this equation for x.