4
$\begingroup$

There are 26 red cards and 26 black cards on the table which are randomly shuffled and are facing down onto the table. The host turns up the cards one at a time. You can stop the game any time (even at the beginning of the game). Once you stops the game, the next card is turned up: if it is red, you get $1; otherwise you pay the host one dollar. What is the payoff of this game?

$\endgroup$
  • 2
    $\begingroup$ Since you apparently get to observe cards as they're turned up, you can "count cards" and employ some stopping rule for when to say "stop". (Personally, if I was actually offered the chance to play this game and had enough preparation time, I'd use simulation to try to work out when to stop so as to give the best return) $\endgroup$ – Glen_b Oct 3 '15 at 6:00
  • $\begingroup$ @Glen_b There's no need to count cards. $\endgroup$ – whuber Oct 3 '15 at 18:26
  • 1
    $\begingroup$ @whuber Yes it looks like you don't need to after all, assuming I understood your answer correctly. [If the game began by turning over some cards and then inviting you to play with what's left, deciding whether or not to play would require counting (knowing r and b for the remainder).] $\endgroup$ – Glen_b Oct 3 '15 at 18:35
4
$\begingroup$

The value is $26/(26+26) = 1/2$.


Let there be $r \ge 0$ red cards and $b \ge 0$ black cards on the table, for a total of $n = r+b \ge 1$ cards. Any optimal strategy stops the game if the expected reward for stopping exceeds that of letting the game continue and continues the game if the expected reward for stopping is less than for continuing.

To find these strategies, let $v(r,b)$ be the expected value of this game. Then the expected reward for stopping now is the chance a red will be revealed, equal to $r/(r+b)$, times the unit reward attached to that plus the chance a black will be revealed, equal to $b/(r+b)$, times the zero reward attached to that event: $$e(r,b) = \frac{r}{r+b}(1) + \frac{b}{r+b}(0) = \frac{r}{r+b}.$$ The expected reward for letting the game continue likewise is a probability-weighted sum over the same two outcomes, $$x(r,b) = \frac{r}{r+b}v(r-1,b) + \frac{b}{r+b}v(r,b-1).$$ Therefore $$v(r,b) = \max(e(r,b), x(r,b)).\tag{Recursion}$$

When there are only red cards or only black cards left on the table the outcome is clear: $$v(r,0) = 1\text{ and }v(0,b) = 0.\tag{Initial conditions}$$

These formulas determine $v(r,b)$ recursively. I claim that $$v(r,b) = \frac{r}{r+b}.\tag{1}$$ This evidently is true for the initial conditions. Let $n \gt 1$. Assuming $(1)$ holds for all values of $r$ and $b$ summing to less than $n$, $$x(r,n) = \frac{r}{r+b}\frac{r-1}{r-1+b} + \frac{b}{r+b}\frac{r}{r+b-1} = \frac{r}{r+b},$$ implying $$v(r,b) = \max(e(r,b),x(r,b)) = \max\left(\frac{r}{r+b}, \frac{r}{r+b}\right) = \frac{r}{r+b}.$$ This completes an inductive proof of the claim.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.