1
$\begingroup$

Here is a question asked on MSE a few years ago: Optimal stopping in red vs black card game deck of 52 cards

Imagine you are playing a card game you start with a well shuffled deck of $52$ cards, containing $26$ red cards and $26$ black cards, stacked face down. You have a sequence of turns, $52$ possible turns in total, each turn you either pull the top card and turn it over, or you quit. If you pull a red card you win $1$, and if you pull a black card you lose $1$. If you played all $52$ turns without stopping you are guaranteed to break even. What is the optimal stopping strategy?


There is an answer given there by quasi: https://math.stackexchange.com/a/2544082/834963

Let $v(r,b)$ be the expected value of the game for the player, assuming optimal play, if the remaining deck has $r$ red cards and $b$ black cards.

Then $v(r,b)$ satisfies the recursion $$ v(r,b) = \begin{cases} 0&\;\text{if}\;r=0\\[4pt] r&\;\text{if}\;b=0\;\text{and}\;r>0\\[4pt] \max(0,f(r,b))&\;\text{if}\;r,b>0\\[4pt] \end{cases} $$ where $$ f(r,b) = \left({\small{\frac{r}{r+b}}}\right)(1+v(r-1,b)) + \left({\small{\frac{b}{r+b}}}\right)(-1+v(r,b-1)) $$ The stopping rule is simple: Stop when $v(r,b)=0$.

To explain the recursion . . .

If $r,b>0$, and the player elects to play a card, then:

  • The revealed card is red with probability ${\large{\frac{r}{r+b}}}$, and in that case, the player gets a score of $+1$, and the new value is $v(r-1,b)$.$\\[4pt]$
  • The revealed card is black with probability ${\large{\frac{b}{r+b}}}$, and in that case, the player gets a score of $-1$, and the new value is $v(r,b-1)$.
Thus, if $r,b>0$, electing to play a card yields the value $f(r,b)$.

But the player always has the option to quit, hence, if $r,b>0$, we get $v(r,b) = \max(0,f(r,b))$.

Implementing the recursion in Maple, the value of the game is $$v(26,26) = \frac{41984711742427}{15997372030584}\approx 2.624475549$$ and the optimal stopping strategy is as follows . . .

  • If $24 \le b \le 26$, play while $r \ge b - 5$.$\\[4pt]$
  • If $17 \le b \le 23$, play while $r \ge b - 4$.$\\[4pt]$
  • If $11 \le b \le 16$, play while $r \ge b - 3$.$\\[4pt]$
  • If $6 \le b \le 10$, play while $r \ge b - 2$.$\\[4pt]$
  • If $3 \le b \le 5$, play while $r \ge b - 1$.$\\[4pt]$
  • If $1 \le b \le 2$, play while $r \ge b$.$\\[4pt]$
  • If $b = 0$, play while $r > 0$.

However, given that this question was asked as part of a job interview, I don't think it's very realistic to get $2.62$ in a short amount of time. I was wondering if there a quick way to:

  1. Find the optimal stopping rule in terms of maximizing expected payoff.
  2. Get an estimate close to the actual answer of around $2.62$ without laborious recursive calculation or writing a program.
$\endgroup$
5
  • 1
    $\begingroup$ Eyeballing it, it looks like you play while $r \ge b - \sqrt{b}$. Perhaps there's an easy heuristic to get there. $\endgroup$ Commented Jul 19, 2022 at 3:26
  • $\begingroup$ Not sure it's feasible to pull off in an interview, but you can approximate the expected value/optimal stopping rule by looking at the continuous version of the problem: the optimal stopping of a Brownian Bridge. cambridge.org/core/services/aop-cambridge-core/content/view/… $\endgroup$
    – user51547
    Commented Jul 21, 2022 at 22:03
  • $\begingroup$ @JRichey That's a different problem where the payout is determined only by the last card after stopping. Here, there's a payout for every card drawn. You can certainly do better than breaking even - you can never do worse than breaking even (by simply drawing all cards), and it's possible to do better by simply stopping at a time when you have a positive value. The expected value must be positive, since it's possible to win money but impossible to lose money. $\endgroup$ Commented Jul 25, 2022 at 15:56
  • $\begingroup$ A simple heuristic that probably gives the right order of magnitude: the probability that a bridge reaches height $\sqrt{n}$ is constant order. So you can just pick a height on that order and stop when you hit it, with expected value constant root $n$. Finding the best constant might even be doable in the large $n$ limit using the distribution for the maximum of a Brownian bridge. $\endgroup$
    – J Richey
    Commented Jul 25, 2022 at 21:38
  • $\begingroup$ Technically they might just want to check how familiar the job candidate was with the standard literature like researchgate.net/publication/… Once you know that the standard Brownian bridge on $[0,1]$ has the optimal stopping value of about $0.37$, you can just scale it by $\sqrt{52}$ to get $2.66$, which is a bit optimistic due to the actual process being discrete, but only a little bit. The strategy expected was just the natural discretization of the continuous strategy, which was also, probably, assumed known to the candidate. $\endgroup$
    – fedja
    Commented Aug 9, 2022 at 5:11

2 Answers 2

1
$\begingroup$

Look for the 'pivot points' and make continuous approximations

Here's part of an answer...

If we do some handwaving and approximations we can get something more compact without actually doing the computations.

First, simplifying the notation of $v$ and $f$, we can combine into $q$ notation: q depends on both state and action, and is the expected value of taking the proposed action in the state and then acting optimally thereafter.

Using Bellman's optimal q equation, writing $q(r, b)$ for the quality of the action $\operatorname{play}$ in state $(r, b)$ (the quality of the action $\operatorname{stop}$ is always $0$)

$$q(r, b) = \frac {r} {r+b}\left(1 + \max(0, q(r-1, b))\right) + \frac {b} {r+b}\left(-1 + \max(0, q(r, b-1))\right)$$

The point of the question is to determine when $q(r, b) > 0$ (i.e. we should take the $\operatorname{play}$ action) and also what is $q(26, 26)$. What follows makes some progress toward the former.

So the criterion is

$$q(r, b) > 0$$

First handwave: in the region of $0$, less $r$ is 'bad', less $b$ is 'good'

Those $\max$ expressions sure make this fiddly!

Let's look for 'pivot points' where $q \simeq 0$.

Assuming $q$ is roughly continuous, when we're near (in $(r, b)$-space) $q(r, b) = 0$ we should expect that reducing $r$ pushes us into negative territory. And we should assume that reducing $b$ pushes us into positive territory.

So 'near a pivot' we can say

$$\max(0, q(r-1, b)) = 0$$ $$\max(0, q(r, b-1)) = q(r, b-1)$$

and also

$$\frac {\partial q} {\partial r}(r, b) > 0$$ $$\frac {\partial q} {\partial b}(r, b) < 0$$

Second handwave: small changes in $r$, and $b$ have roughly linear effects

This is basically a Taylor assumption. I don't justify it here, but it seems intuitively sensible for the domain in question.

Now we can say things like, near a pivot where $q(r, b) = 0$

$$\max(0, q(r-1, b)) = \max\left(0, q(r, b) - \frac {\partial q} {\partial r}(r, b)\right) = 0$$ $$\max(0, q(r, b-1)) = \max\left(0, q(r, b) - \frac {\partial q} {\partial b}(r, b)\right) = -\frac {\partial q} {\partial b}(r, b)$$

Putting it together and 'solving'

Now we have, near a 'pivot point' where $q(r, b) \simeq 0$,

$$q(r, b) \simeq \frac r {r+b} + \frac b {r+b}\left(-1 - \frac {\partial q} {\partial b}(r, b)\right)$$

So we have a first order partial differential equation for $q$ in $b$

$$0 \simeq r + b \left(-1 - \frac {\partial q} {\partial b}\right)$$

Separating,

$$\frac {\partial q} {\partial b} = -1 + \frac r b$$

and solving

$$q = - b + r \ln b + c_r(r)$$

I'm not sure what handwaves are required, but intuitively we should be able to do some similar tricks to get

$$q = r + c_b(b)$$

and from there

$$q = r - b + r\ln b + c$$

which yields the criterion (for some $c$ to be determined, perhaps by inspecting small $r$, $b$ cases)

  • Play while $r > \frac {b + c} {1 + \ln b}$

Presumably an appropriate $c$ is small, maybe zero, since for small $r$ and $b$, $r-b$ is a good criterion.

Finding $q(26, 26)$

The above solution should not be expected to extrapolate usefully 'away from pivots', since many of the assumptions require being in the region of a pivot. So we can't use this to answer the other part of the question.

$\endgroup$
2
  • $\begingroup$ One trouble with this fun theorising is that it doesn't seem to work very well! The factor $\frac 1 {1 + \ln b}$ discounts more rapidly than the brute force calculated optimal criterion (which appears closer to $1 - \sqrt(b)$) $\endgroup$
    – Oly
    Commented Jul 25, 2022 at 16:23
  • $\begingroup$ Thanks Oly. How is one able to get something close to $2.62$ from what you wrote without laborious calculation? $\endgroup$ Commented Jul 29, 2022 at 5:57
1
$\begingroup$

For large $r, b$ with $\frac rb$ close to $1$, we should expect the game to be approximately unchanged after replacing each $+1$ card with four cards $+\frac12, +\frac12, +\frac12, -\frac12$, and each $-1$ card with four cards $+\frac12, -\frac12, -\frac12, -\frac12$, since the replacements have the same sum and variance over a given fraction of the deck. In other words, doubling $b - r$ while quadrupling $r + b$ should approximately double the game value. So the optimal stopping criterion should have $b - r$ approximately proportional to $\sqrt{r + b}$.

$\endgroup$
1
  • $\begingroup$ Thanks Anders. How is one able to get something close to $2.62$ from what you wrote without laborious calculation or writing a program? $\endgroup$ Commented Jul 29, 2022 at 5:56

You must log in to answer this question.

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