Riddle

[RunDownHouse]

I'm cross-posting this in OOT since they had such fun with a game theory post a while back. Background: from this (http://www.riddles.com/riddle.php?riddleid=1022) riddles site, I found this particular riddle under the "Impossible" section. In the answer, the contributor says that he couldn't answer the riddle at all, and didn't find an answer until one (in the form of a huge spreadsheet) was emailed to him two years after posting. I don't see what is particularly difficult about it, though, after thinking about it for a few minutes. Maybe the calculation of the exact expected payoff is the hard part, as I didn't try that. On to the riddle.

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?

Also, what is the expected payoff following this optimal rule?

[bocablkr]

Obviously, the most you can make is 26 bucks and you can never lose. At worst break even. My rule would be to draw until I am up the same amount of cards remaining and then stop. Ex. I am up 6 and there are 6 cards left. But I am sure this is not the most optimal rule to follow.

[hmkpoker]

Play till you're one ahead and quit?

[Borodog]

[ QUOTE ]
Play till you're one ahead and quit?

[/ QUOTE ]

This seems like the intuitive answer to me. If you get up a dollar, the next draw is -EV, so you should quit.

[atrifix]

Forward induction would seem to indicate that you should just play until you reach +1 (or 0, if you exhaust the entire deck) and then quit. The EV of this play is very close to 1, whereas the EV of other plays seemingly always approaches 0. I'm not sure that this is the best answer, though. The fact that you get to continue playing may be worth something.

[Sephus]

[ QUOTE ]
Play till you're one ahead and quit?

[/ QUOTE ]

pretty sure this is wrong. the EV of this game (played optimally) is significantly more than $1. the worst you can do is zero and it seems like if your rule was something like "stop when you're up 2" you would get $2 much more than half the time. i think the solution really is difficult.

[Borodog]

[ QUOTE ]
[ QUOTE ]
Play till you're one ahead and quit?

[/ QUOTE ]

pretty sure this is wrong. the EV of this game is significantly more than $1.

[/ QUOTE ]

Can you show this?

[Sephus]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Play till you're one ahead and quit?

[/ QUOTE ]

pretty sure this is wrong. the EV of this game is significantly more than $1.

[/ QUOTE ]

Can you show this?

[/ QUOTE ]

probably, given time.

[Sephus]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
Play till you're one ahead and quit?

[/ QUOTE ]

pretty sure this is wrong. the EV of this game is significantly more than $1.

[/ QUOTE ]

Can you show this?

[/ QUOTE ]

i know this isn't proof but i just tried stopping when up 2. i played 10 times, won $2 9 times and $0 once.

[Borodog]

[ QUOTE ]
[ QUOTE ]
Play till you're one ahead and quit?

[/ QUOTE ]

pretty sure this is wrong. the EV of this game (played optimally) is significantly more than $1. the worst you can do is zero and it seems like if your rule was something like "stop when you're up 2" you would get $2 much more than half the time. i think the solution really is difficult.

[/ QUOTE ]

Your edit convinced me. I ran through ten trials and got to +$2 ever time. Clearly the problem is more complex than I gave it credit for.

[Borodog]

Heh.

[Jshuttlesworth]

Not sure how to get this, but I think the solution will be of the form "stop if you are ahead n dollars after x red cards and y black cards have been seen." Does anyone agree with this?

[ZeeJustin]

This has been posted before, although I can't remember what forum. It may have been in the theory forum.

I think the EV of the game was around +$4-$5, and when to stop depends on both the money won and number of cards left in the deck.

[GBP04]

[ QUOTE ]
This has been posted before, although I can't remember what forum. It may have been in the theory forum.

I think the EV of the game was around +$4-$5, and when to stop depends on both the money won and number of cards left in the deck.

[/ QUOTE ]

Theory Forum, Sklansky posted it I believe.

[xorbie]

As I said in the other thread, showing that EV(continuing at +1) is clearly > 1, unless there are no cards left. Even with just 4 cards in the deck, if you draw a +1 at first its 0EV to draw again. This is the caluclation:

EV = 1/3*1 + 2/3*1/2*1 = 1

the first multiple is the chance of drawing the last +1 card, at which point you quit, the second is the chance of drawing a -1 but then drawing a +1, at which point you quit.

intuitively you should be able to see that (a) the chance of drawing another +1 card increases as we add more cards and (b) the chance of getting back to +1 increases as we add more cards.

clearly stopping at +1 anytime before there are just 3 cards left in the deck is estupido.