# What is the expected value of this game for large N?

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})$$.

• 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.
– Him
Commented Sep 4, 2019 at 16:17
• Don't know if this helps but this game is called the Larry Shepp urn game, by Larry Shepp of Rutgers. Commented Sep 4, 2019 at 18:12
• 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.
– Him
Commented Sep 4, 2019 at 19:37
• 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. Commented Sep 6, 2019 at 20:31

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.

• Agrees with numerical evaluation. Commented Sep 12, 2019 at 13:02
• 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?
– VF1
Commented May 9, 2021 at 15:35