4 ms·

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,

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%.
  - Dalewyn 4y ago
    Looking back, I think I got my numbers mixed up (thanks, beer!). $12 or $13 is probably the number I'm looking for, not $26. Anyway, my logic is if I am at or higher than the median after I have drawn half the deck, then that means there are more black cards than reds in the remaining deck and I have a greater chance each draw of losing a buck than gaining. So it is in my best interest to pull out at that point, than to try my luck against ever worsening odds.
- twoodfin 4y ago
  The EV to drawing another card is going to be tied to the probabilities of continued random walks eventually landing on higher scores than you currently have. You stop as soon as the EV is negative (or 0 if you’re not a gambler). That calculation is presumably the tricky part… integrating over Pascal’s Triangle or something. But it must be positive to start: If the first card is red we have already gained, and if it’s black we’re at worst back where we started.
knaik94 4y ago
This reminds me how I was introduced to this topic, the St Petersburg paradox. It was after a discrete 2 final. The professor heard us talking about a competition from our Quant finance club and decided to ask us this problem. Essentially asking the same thing but with a dice, so with replacement, with bigger values and asking what logic our stop algorithm would be to maximize our return. And what would happen if the gain and loss weren't equal with something like +4,+3,+2,-1,-2,-3 as well aas with -4,-3,-2,+1,+2,+3. We ended up staying an extra 2 hours discussing it.
bluecalm 4y ago
Very nice puzzle! A quick Python script that solves it as it's difficult to do with a pen and paper: #awesome feature from Python 3.9! from functools import cache @cache def ev(score, cards_left): if cards_left == 0: return 0 up_cards_no = (cards_left - score) / 2 p_up = up_cards_no / cards_left p_down = 1 - p_up return max(score, p_up * ev(score + 1, cards_left - 1) + p_down * ev(score - 1, cards_left - 1)) >>> ev(0,52) 2.6244755489939253 Of course we should continue if the current score is lower than ev. Here is the script to find exact thresholds at which we should stop drawing more cards: def find_thresholds(): print(f"EV of tha game: {ev(0,52)}") # fill the cache up for i in range (0,10): thres = 52 - i while ev(i, thres) > i: thres -= 2 print(f"At score {i} you should stop drawing with {thres} cards left") >>> find_thresholds() EV of tha game: 2.6244755489939253 At score 0 you should stop drawing with 0 cards left At score 1 you should stop drawing with 3 cards left At score 2 you should stop drawing with 8 cards left At score 3 you should stop drawing with 17 cards left At score 4 you should stop drawing with 28 cards left At score 5 you should stop drawing with 41 cards left At score 6 you should stop drawing with 46 cards left ... Being up 6 or more we should always stop. The last interesting number is being up 5.

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%.
- Dalewyn 4y ago
  Looking back, I think I got my numbers mixed up (thanks, beer!). $12 or $13 is probably the number I'm looking for, not $26. Anyway, my logic is if I am at or higher than the median after I have drawn half the deck, then that means there are more black cards than reds in the remaining deck and I have a greater chance each draw of losing a buck than gaining. So it is in my best interest to pull out at that point, than to try my luck against ever worsening odds.
twoodfin 4y ago
The EV to drawing another card is going to be tied to the probabilities of continued random walks eventually landing on higher scores than you currently have. You stop as soon as the EV is negative (or 0 if you’re not a gambler). That calculation is presumably the tricky part… integrating over Pascal’s Triangle or something. But it must be positive to start: If the first card is red we have already gained, and if it’s black we’re at worst back where we started.

knaik94 4y ago

This reminds me how I was introduced to this topic, the St Petersburg paradox. It was after a discrete 2 final. The professor heard us talking about a competition from our Quant finance club and decided to ask us this problem. Essentially asking the same thing but with a dice, so with replacement, with bigger values and asking what logic our stop algorithm would be to maximize our return. And what would happen if the gain and loss weren't equal with something like +4,+3,+2,-1,-2,-3 as well aas with -4,-3,-2,+1,+2,+3. We ended up staying an extra 2 hours discussing it.

bluecalm 4y ago

Very nice puzzle! A quick Python script that solves it as it's difficult to do with a pen and paper: #awesome feature from Python 3.9! from functools import cache @cache def ev(score, cards_left): if cards_left == 0: return 0 up_cards_no = (cards_left - score) / 2 p_up = up_cards_no / cards_left p_down = 1 - p_up return max(score, p_up * ev(score + 1, cards_left - 1) + p_down * ev(score - 1, cards_left - 1)) >>> ev(0,52) 2.6244755489939253 Of course we should continue if the current score is lower than ev. Here is the script to find exact thresholds at which we should stop drawing more cards: def find_thresholds(): print(f"EV of tha game: {ev(0,52)}") # fill the cache up for i in range (0,10): thres = 52 - i while ev(i, thres) > i: thres -= 2 print(f"At score {i} you should stop drawing with {thres} cards left") >>> find_thresholds() EV of tha game: 2.6244755489939253 At score 0 you should stop drawing with 0 cards left At score 1 you should stop drawing with 3 cards left At score 2 you should stop drawing with 8 cards left At score 3 you should stop drawing with 17 cards left At score 4 you should stop drawing with 28 cards left At score 5 you should stop drawing with 41 cards left At score 6 you should stop drawing with 46 cards left ... Being up 6 or more we should always stop. The last interesting number is being up 5.