Skip to main content

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

Comments

  1. im not sure i follow this problem...

    if 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?

    ReplyDelete
  2. I am sorry. Just missed that line. my mistake. If you pick a black card, you loose one dollar. :) Change made in the problem.

    ReplyDelete
  3. then 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?

    ReplyDelete
  4. Unlike 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.
    But 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.

    ReplyDelete
  5. he should stop picking the cards as soon as he has earned a dollar !

    ReplyDelete
  6. @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.

    for 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)

    ReplyDelete
  7. @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.

    @Tiger(Omkar) and Pranay.. Hope the explanation by Aman was clear.

    Solution in detail provided at http://puzzles.nigelcoldwell.co.uk/fourteen.htm

    ReplyDelete
  8. Just to summarize the solution from the link I posted.. There is no mathematical solution. The solution is as follows:

    E(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.

    ReplyDelete
  9. true... i didn't look at the whole scenario but just the next card... nice problem...

    ReplyDelete
  10. The answer one gets running the computer program is 2.624 :P

    ReplyDelete
  11. http://www.math.kit.edu/stoch/~baeuerle/seite/markov_nb/media/brdmv-2.pdf

    approach to this problem is given in this paper.

    ReplyDelete

Post a Comment

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"


Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

Solution:
1)
(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Source:
Sent to me by Gaurav Sinha

Problem:
Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions. In total, Siddhant scores 25 out of 34. 

Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34.

Note that
a) Vaibhav scores more than Siddhant
b) Siddhant score better than Vaibhav in both individual topics - 5/6 > 20/25 and 20/28 > 6/9

How is it possible?