15
$\begingroup$

We play a game. I shuffle a deck of cards and start dealing them face up. After any card you can say "stop", at which point I pay you 1 dollar for every red card dealt and you pay me 1 for every black card dealt. What is your optimal strategy, and how much would you play to pay this game?

Clearly the game is worth at least 0, since you can follow the strategy 'wait until all the cards are dealt' and get paid 0.

We can conclude that at any stage of the game, we will ask for another card if the expected value of continuing to play is greater than the amount of money already won; otherwise we will say stop. Mathematically, if $r$ is the number of red cards remaining and $b$ is the number of black cards remaining, and $f_{r,b}$ is the expected value of the game at this point, then the expected value of taking another card is

$e_{r,b} = \frac{r}{r+b} f_{r-1,b} + \frac{b}{r+b} f_{r,b-1}$

and hence the value of the game at this point, assuming we play the optimal strategy, is

$f_{r,b} = \max ( \frac{r}{r+b} f_{r-1,b} + \frac{b}{r+b} f_{r,b-1}, b-r )$

with $f_{r,0} = 0$ (if there are only red cards remaining, we have a guaranteed payout of 0) and $f_{0,b} = b$ (if there are only black cards remaining we won't take any more cards).

Solving numerically gives an expected value for this game of 2.624 with 52 cards. I'm interested in what the value is for a deck of $2n$ cards, and if the optimal strategy can be expressed analytically as a function of $r$ and $b$ (ie keep taking cards until you have made $g(r,b)$ dollars, then stop).

I've tried changing coordinates to $u=b-r$, $v=b+r$, and I've tried approximating the difference equation as a PDE, but no luck with an analytical solution yet - or even any decent approximations.

Improve this question
$\endgroup$
6
  • $\begingroup$ It would be interesting to understand the asymptotics of the winning as $n \to \infty$. Do you have a sense of that? An easy upper-bound seems to be $O(\sqrt{n \log \log n})$ from the iterated logarithm law. I think (not sure) that this should be the asymptotic behavior here too (i.e. the fact that you're constrained to return to zero after 2n steps shouldn't change the asymptotic behavior). $\endgroup$
    – Or Zuk
    Commented Feb 18, 2011 at 19:31
  • 1
    $\begingroup$ Certainly the upper bound can be $O(\sqrt{n})$ as this is the maximum of a Brownian motion (or bridge). You can achieve this order of magnitude since there is a positive probability of reaching this value. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Feb 18, 2011 at 23:02
  • 2
    $\begingroup$ @Ori, @Or: Not just a bound, but a precise asymtotic limit. If $V$ is the optimal value for a Brownian bridge, then the value for the game with $n$ cards satisfies $V_n\sim V\sqrt{n}$. $\endgroup$
    – George Lowther
    Commented Feb 19, 2011 at 1:35
  • $\begingroup$ And, in the case of a Brownian bridge $B_t$ (stop at some time $0\le t\le1$ to maximize $\mathbb{E}[B_T]$) must have value $f(B_t/\sqrt{1-t})\sqrt{1-t}$ at time (assuming we haven't stopped yet) for some function $f$, and you stop as soon as this is equal to $B_t$. So $f$ will reduce to an ODE (rather than a PDE). I assume that Andreas' linked article does something like this. $\endgroup$
    – George Lowther
    Commented Feb 19, 2011 at 1:46
  • 3
    $\begingroup$ For a second, the title led me thinking that the question was about the game of bridge, perhaps played at random ... $\endgroup$
    – Denis Serre
    Commented Feb 19, 2011 at 10:21

3 Answers 3

Reset to default
7
$\begingroup$

I think the article Optimal stopping of a Brownian bridge by Ekström and Wanntorp (preprint) would give you the answer for the limiting case as $n\to\infty$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 for finding that reference. So, you have $V_n\sim V\sqrt{n}$. From equation (6) of the preprint, $V=(1-B^2)\sqrt{\pi/2}$ where $B$ is the unique solution to $\sqrt{2\pi}(1-B^2)e^{B^2/2}\Phi(B)=B$. $\endgroup$
    – George Lowther
    Commented Feb 19, 2011 at 2:26
2
$\begingroup$

This specific game seems very familiar, and I'm sure I have seen it discussed before along with a discussion of the optimal strategy, although I can't remember where. It might have been the Project Euler forums, perhaps in one of the forums restricted to those who have solved a particular problem. Using Google to search for the exact answer for $52$ cards might find it if it is in an open forum.

I believe the simulations said you should stop when there are about $k$ cards left in the deck and you are ahead by $c\sqrt k$, where $c$ did not seem to depend on $n$.

In an interesting variant, you can choose the fraction of your bankroll that you wager on whether each card is red or black. You do not need to bet only on red. It turns out that as long as you bet on the right side, and you bet your whole bankroll when you have a lock, your expected bankroll is multiplied by $\prod_{k=1}^n \frac {2k}{2k-1}$. Betting according to the Kelly criterion gives you that result with $0$ variance.

Improve this answer
$\endgroup$
2
$\begingroup$

Perhaps the delightful paper, How to lose as little as possible, by Vittorio Addona, Stan Wagon, and Herbert Wilf, is related to your question? If not, you lose little by scanning it. From their Abstract:

Suppose Alice has a coin with heads probability $q$ and Bob has one with heads probability $p>q$. Now each of them will toss their coin $n$ times, and Alice will win iff she gets more heads than Bob does. Evidently the game favors Bob, but for the given $p,q$, what is the choice of $n$ that maximizes Alice's chances of winning?

They determine the optimal strategy, and it is essentially unique, non-obvious, and requires intricate calculation to pinpoint. I think(?) your case is $p=q$, whereas they assume throughout that $p>q$. Perhaps you can extract something useful from their results by letting $q \rightarrow p$? Their recurrence relations are analogous to those you detailed.

See also this MO question: Recurrence relations whose base case is at $\infty$, in which I raised the question of this whole class of recurrence relations. Although for you, $\infty = 52$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ The OP's example should be very different from what you suggest: you know the number of Heads and Tails that you're going to get, but on the other hand the length of the game is not fixed in advance. Or am I missing something? $\endgroup$
    – Thierry Zell
    Commented Feb 19, 2011 at 1:57
  • $\begingroup$ @Thierry: What struck me is the similarity between the OP's recurrence for $f_{r,b}$, and the equation I display in the MO posting for $f(h,t)$. In both cases the recurrence is a max over three terms: a fraction of $\pm 1$ in one parameter, a fraction of $\pm 1$ in the second variable, and a simple function of the two parameters. I am not claiming that either problem reduces to the other, but the recurrence relations have a structural similarity that might permit transfer of ideas from one domain to the other. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 19, 2011 at 2:27
  • $\begingroup$ @Joseph: Thanks for the clarification, and for the arxiv link. This promises to be a very interesting paper. $\endgroup$
    – Thierry Zell
    Commented Feb 19, 2011 at 2:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .