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

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.

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)

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

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

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

-brett

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

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