Red vs Black cards - Expected payoff
This is a variation of the problem discussed some time back: Don't roll More. Just published the solution to the earlier problem. Thought it would be interesting to solve this problem taken once again from the book "Heard on The Street".
Problem: You have 52 playing cards (26 black and 26 red). You draw cards one by one. A red card pays you a dollar. A black card costs you a dollar. You can stop any point 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 the optimal rule?
Hint: Try the problem with 4 cards (2 red, 2 black) :)
Update(29/01/10): Question was incomplete. Added more information.
Solution: (Update (05/02/10)) Idea posted by Aman in comments!! Solution posted by me in comments!!
The problem/solution is very difficult and not so beautiful. Its not very mathematical though. Do this only if you have time and you are humble enough to accept defeat :P
Problem: You have 52 playing cards (26 black and 26 red). You draw cards one by one. A red card pays you a dollar. A black card costs you a dollar. You can stop any point 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 the optimal rule?
Hint: Try the problem with 4 cards (2 red, 2 black) :)
Update(29/01/10): Question was incomplete. Added more information.
Solution: (Update (05/02/10)) Idea posted by Aman in comments!! Solution posted by me in comments!!
The problem/solution is very difficult and not so beautiful. Its not very mathematical though. Do this only if you have time and you are humble enough to accept defeat :P
im not sure i follow this problem...
ReplyDeleteif every red card pays you a dollar, then draw all 52 cards.
else if ending on a red card gives you a dollar, stop drawing on a red card.
my point is, what is stopping me from drawing all 52 cards?
I am sorry. Just missed that line. my mistake. If you pick a black card, you loose one dollar. :) Change made in the problem.
ReplyDeletethen wouldn't you want to stop when the number of red cards left is strictly less than the number of black cards left in the deck?
ReplyDeleteUnlike the "Don't Roll More" case, here the strategy cannot be specified as what he gets in the nth draw depends upon what he has already drawn.
ReplyDeleteBut in general, he should stop as soon as the expectation of future play becomes < 0.
For the 4 cards case, if he gets +1 in the first draw, the expectation becomes 1/3*1 + 2/3*0.5*0 + 2/3*1/2*-1 = 0 for the rest of the play, so he can leave the game safely.
else if he gets -1 in the 1st draw, the expectation > 0, so he should play on; and if he gets +1 in the 2nd draw, the expectation is again 0 but as his earning is also 0, he should play on.
he should stop picking the cards as soon as he has earned a dollar !
ReplyDelete@Tiger and Pranay: Consider the case when he has 1 red and 2 black cards left, the expectation as shown above is 0 and not, in general, negative.
ReplyDeletefor 6 cards case even if gets +1 in the first draw, he should play on as the expectation for future play is 2/5x1 + 3/5x-1 + 3/5x2/3 =1/5 > 0.
(2/3 being the expectation of the 4 cards play)
@Aman.. nice point raised. Thanx a lot. I was also under the impression that once number of red cards in the set is less than number of black cards, quit. But your solution makes sense. Thanx for the solution.
ReplyDelete@Tiger(Omkar) and Pranay.. Hope the explanation by Aman was clear.
Solution in detail provided at http://puzzles.nigelcoldwell.co.uk/fourteen.htm
Just to summarize the solution from the link I posted.. There is no mathematical solution. The solution is as follows:
ReplyDeleteE(r,b) =
max {(r/r+b)(E(r-1,b)+1) + (b/r+b)(E(r,b-1)-1), 0} for r,b>0
E(0,b)=0
E(r,0)=r
Mathematically, Quit iff (r/r+b)(E(r-1,b)+1) + (b/r+b)(E(r,b-1)-1) < 0
Thats all we got.
Can't do any math beyond this. It is left to calculating the results with a computer from now on. Use dynamic programming to calculate each E(r,b). And then see what's the value for E(26,26).
Write a program to do it. Sorry for the not so mathematical problem. Will take care this does not happen in future.
true... i didn't look at the whole scenario but just the next card... nice problem...
ReplyDeleteThe answer one gets running the computer program is 2.624 :P
ReplyDeletehttp://www.math.kit.edu/stoch/~baeuerle/seite/markov_nb/media/brdmv-2.pdf
ReplyDeleteapproach to this problem is given in this paper.