Interview Question: Optimal Card Playing

Sample Question #250 (statistics – probability)

I have a well-shuffled deck of n red cards and n black cards, all facing down. I let you draw one card at a time. If you draw a black card, I pay you $1. If you draw a red card, you pay me $1. You can stop the game at any time. (As long as you want to play, I’ll accommodate.)

1. What’s the expected payoff of this game to you?

2. What’s your optimal stopping rule?

[A real interview question I was asked at a Goldman Sachs on-site interview]

Advertisements
This entry was posted in Sample Qs. Bookmark the permalink.

9 Responses to Interview Question: Optimal Card Playing

  1. Steven says:

    1. let me take a shot. this a simple random walks problem, take A=1, A’=-1, then
    p= PA=50%,  q=PA’=50%   since n could be infinite number, the expected payoff will be zero.
     
    2.  p = q, say if i have 20 bucks, i would stop playing is i win $20, or lose $10 ( still need $10 for gas to drive home ), then i should play (20-10)(40-20)=200 hands to see God let me win or lose  🙂
     
    if i was interviewed by this question, i would say zero payoff, and may say don’t play it at all or play first hand, stop playing if i won $1,  keep playing till zero blance if i lose at first hand, hahaha~~~ Brett, let me know the correct answer.

  2. Icedragon says:

    I think the best strategy is to 1. stop the game when you win $1, 2. otherwise play till the end of the game then you lose nothing. Once you win $1, the odds is against you if keep playing. (Your opponent has a bigger chance of winning the next bet and winning any amount of money). This strategy guarantees that you won’t lose and the expected return is positive. But I have not totally figured not how to calculate the exact expectation of this strategy. (I have a inductive formula in terms of n. But it is messy)

  3. Brett says:

    Thanks, guys.  This question ranks very high in difficulty level.  At my Goldman interview I was asked to solve the case where n=2 first — and I couldn’t finish it!
     
    I’ll post the answer when I find it.
    -brett

  4. Talbot says:

    You can find a full analysis of this game for n=3 at http://www.baruch.cuny.edu/math/pdf/game2.pdf

  5. Brett says:

    That’s a great link!  Thanks very much.  Happy New Year!
    -brett

  6. Brett says:

    Yeah, it’s really a combination of backward induction and recursive maximization over expected values.
     
    This is generally known as the "urn problem," since the original formulation involved taking balls out of an urn.
     
    Thanks for your contribution.
    -brett

  7. Brett says:

    Of course, the original number of blacks and reds need not be equal. In fact, the solution involves some backward induction which begins by looking at cases where there’s 1 card (or ball) of one color and 0 of the other color.
    -brett

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s