19
$\begingroup$

For a given even $N$, I have $N/2$ red cards and $N/2$ black cards. Each time I draw a black card I win a dollar, each time I draw a red card I lose a dollar. I can stop at any time I like (and choose to do so in such a way that would maximize my expected winnings).

What is the expected value of the game for large $N$?

For a simple example, when $N=2$ - I would draw a card and if it's red, I would draw again (to get value of $0$), and if it's black I would stop, resulting in expected value of $0.5$.

To clarify, I know how to compute this numerically. I'm interested in the functional form for large $N$. For what it is worth, from simulations it appears to be ${\cal O}(\sqrt{N})$.

$\endgroup$
14
  • 2
    $\begingroup$ See also this question $\endgroup$
    – confucious
    Commented Sep 4, 2019 at 15:37
  • 1
    $\begingroup$ If it helps anyone, the matrix $M$ with entries $M_{i,j} = E(i,j)$ is very nearly symmetric about the anti-diagonal. Here's the picture up to 5000x5000. To put the pic in perspective, the maximum value is at the top right with 5000 black cards and no red cards. Purple areas = expected value of 0. $\endgroup$
    – Him
    Commented Sep 4, 2019 at 16:17
  • 3
    $\begingroup$ Don't know if this helps but this game is called the Larry Shepp urn game, by Larry Shepp of Rutgers. $\endgroup$ Commented Sep 4, 2019 at 18:12
  • 3
    $\begingroup$ From @I.J.Kennedy's clue, it looks like Shepp's paper discussing the matter can be found here. A cursory examination suggests that Theorem 4.3 might answer your conjecture in the affirmative. $\endgroup$
    – Him
    Commented Sep 4, 2019 at 19:37
  • 1
    $\begingroup$ So I failed to found a constant $c$ such that $E(N,N)=c\sqrt{N}+o(\sqrt{N})$. But sometimes such a constant can be guessed as follows. :-) Calculate it suggested numerical value with sufficiently high precision. Say, ten digits after the dot. Then google this value, removing the last digit until you find a link to a possible candidate. $\endgroup$ Commented Sep 6, 2019 at 20:31

1 Answer 1

8
+150
$\begingroup$

Letting $E_N$ be the optimal expected value for even $N$, we can show that $$ E_N\sim c\sqrt N $$ for $N$ large, where $c\approx 0.369136$.

I will give a rough argument, which it should be possible to make rigorous by going through the details. Define a process $X^N_t$ for $0\le t\le 1$ as follows. Let $X^N_{k/N}$ be the number of black cards minus the number of red cards after $k$ have been selected. We interpolate in the range $[(k-1)/N,k/N)$ as constant. This is a random walk conditioned on $X_1=0$. Scaling, $N^{-1/2}X^N_t$ converges, in distribution, to a limit $X$ which is a standard Brownian bridge on the interval $[0,1]$ (i.e., a standard Brownian motion conditioned on $X_1=0$). So, commuting the limit with the supremum, $$ N^{-1/2}E_N=\sup_\tau E[N^{-1/2}X^N_\tau]\to\sup_\tau E[X_\tau]. $$ The supremum is taken over stopping times $0\le\tau\le 1$. So, $E_N\sim c\sqrt N$ where $c=\sup_\tau E[X_\tau]$ is the solution to the continuous-time version of the game described.

To solve for $c$, let $f(t,x)$ be the solution starting from $X=x$ at time $t$. That is, $$ f(t,x)=\sup_{\tau\ge t} E[X_\tau\vert X_t=x]. $$ By considering $\tau=t$ and $\tau=1$, we see that $f(t,x)\ge\max(x,0)$. We need to compute $c=f(0,0)$. We can reduce the dimensionality of the problem: by a simple symmetry, for each fixed time $t$, the process $Y_s=(1-t)^{-1/2}X_{t+s(1-t)}$ is also a Brownian motion conditioned on $Y_1=0$. So, $$ \begin{align} f(t,x)&=\sup_{\tau} E[X_{t+\tau(1-t)}\vert X_t=x]\\ &=\sup_\tau(1-t)^{1/2} E[Y_\tau\vert Y_0=(1-t)^{-1/2}x]\\ &=(1-t)^{1/2}g((1-t)^{-1/2}x) \end{align} $$ where I am setting $g(x)=f(0,x)$. Next, the Brownian bridge satisfies the Stochastic differential equation $$ dX_t = dW_t - (1-t)^{-1}X_tdt $$ for standard Brownian motion $W$. On the domain where $f(t,x) > x$ then $f(t,X_t)$ is locally a martingale, so it satisfies the Kolmogorov backward equation (PDE), $$ \frac{\partial}{\partial t}f+\frac12\frac{\partial^2}{\partial x^2}f-(1-t)^{-1}x\frac{\partial}{\partial x}f=0. $$ Substituting in the expression for $f$ in terms of $g$ gives a linear ODE $$ g^{\prime\prime}(y)-yg^{\prime}(y)-g(y)=0. $$ This has the general solution $$ g(y)=e^{y^2/2}(a+bN(y)) $$ for constants $a,b$, where $N(y)=(2\pi)^{-1/2}\int_{-\infty}^ye^{-t^2/2}dt$ is the cumulative normal distribution function. As $g$ is increasing, it cannot blow up in the limit $y\to-\infty$, so we have $g(y)=be^{y^2/2}N(y)$ on the domain $g(y) > y$. Plugging in $y=0$ gives $c=g(0)=b/2$, so $g(y)=2ce^{y^2/2}N(y)$ over $g(y) > y$. As $g(y)$ cannot blow up faster than linearly in $y$, there must be a $y_0 > 0$ for which $2ce^{y_0^2/2}N(y_0)=y_0$, so that $g(y)=y$ for $y > y_0$. The optimal value of $c$ for which this holds is given by $$ c=\sup_{y > 0}\frac{ye^{-y^2/2}}{2N(y)}. $$ By differentiating, the function of $y$ on the right has a unique local maximum. I am not sure if there is an analytic solution, but I tried in wolfram alpha. Expressing in terms of the error function, $$ c=\sup_{y > 0}\frac{ye^{-y^2/2}}{1+{\rm erf}(y/\sqrt2)} $$ we get $c\approx0.369136$.


For comparison, I also computed the $\alpha$ in the linked paper as $\alpha\approx0.839923675692373$, so $c=(1-\alpha^2)(\pi/2)^{1/2}\approx 0.369136$ and we are in agreement.

$\endgroup$
2
  • 2
    $\begingroup$ Agrees with numerical evaluation. $\endgroup$
    – leonbloy
    Commented Sep 12, 2019 at 13:02
  • $\begingroup$ For the game value $E_N$ to asymptotically match the expected supremum of the underlying process, the optimal strategy must be able to achieve expected return within $o(\sqrt{N})$ of this supremum. Why is that the case? $\endgroup$
    – VF1
    Commented May 9, 2021 at 15:35

You must log in to answer this question.

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