1
$\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$
1
$\begingroup$

[Thanks to Brian Scott for pointing out my original misinterpretation of this problem.]

The value of the game is zero.

Let $f(r,b)$ denote the value of the game if there are $r$ red cards and $b$ black cards remaining. If we stop at that point, the expected value is $(r-b)/(r+b)$; but as we also have the option of continuing, we have the recurrence $$f(r,b)=\max\left((r-b)/(r+b),\frac{r}{r+b}f(r-1,b)+\frac{b}{r+b}f(r,b-1)\right).$$

The boundary conditions are $f(0,0)=0$, $f(1,0)=1$, $f(0,1)=-1$, and $f(r,b)=0$ if either $r$ or $b$ is negative. Calculating individual values of $f(r,b)$ is easy using dynamic programming. Here are values of $f(r,b)$ for small $r$ and $b$: $$ \begin{array}{c|cccccc} r\,\backslash b & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 0 & -1 & -1 & -1 & -1 & -1 \\ 1 & 1 & 0 & -\frac{1}{3} & -\frac{1}{2} & -\frac{3}{5} & -\frac{2}{3} \\ 2 & 1 & \frac{1}{3} & 0 & -\frac{1}{5} & -\frac{1}{3} & -\frac{3}{7} \\ 3 & 1 & \frac{1}{2} & \frac{1}{5} & 0 & -\frac{1}{7} & -\frac{1}{4} \\ 4 & 1 & \frac{3}{5} & \frac{1}{3} & \frac{1}{7} & 0 & -\frac{1}{9} \\ 5 & 1 & \frac{2}{3} & \frac{3}{7} & \frac{1}{4} & \frac{1}{9} & 0 \\ \end{array} $$

Apparently $f(r,b)=-f(b,r)$; this is easy to prove from the recurrence. Accordingly $f(26,26)=0$.

[Actually it follows from the recurrence (and is evident from the table] that $f(r,b)=(r-b)/(r+b)$ -- in other words, it is never optimal to continue playing.]

$\endgroup$
  • $\begingroup$ @BrianM.Scott My understanding of the game is that the payoff every time a card is turned over is $1$ or $-1$. So if I find myself at some point in the game having drawn $r$ red cards and $b$ black cards, my aggregate profit to that point in the game is $r-b$. (Which means (oops) I effectively swapped $r$ and $b$ in my table; I'll correct that shortly.) $\endgroup$ – Tad Oct 3 '15 at 17:47
  • $\begingroup$ @BrianM.Scott Thanks - upon re-reading, I agree with your interpretation. Have adjusted accordingly. $\endgroup$ – Tad Oct 3 '15 at 19:21
  • $\begingroup$ Looks good; I hope you don’t mind the small change to make the table a little easier to read. $\endgroup$ – Brian M. Scott Oct 3 '15 at 19:24
  • $\begingroup$ @BrianM.Scott no problem - I'm actually having some difficulty editing for some reason. $\endgroup$ – Tad Oct 3 '15 at 19:26
1
$\begingroup$

Consider the related game which begins the same way, but at the point you stop the game, the host turns up the bottom card from the deck to determine the payout. You have no information about the ordering of the unrevealed cards, so choosing the bottom card instead of the top should make no difference. In this version, it is clear the average payout is $0$: the bottom card is fixed from the beginning, and it is equally likely to be black or red.

$\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.