2. An upper bound for the value function $\boldsymbol{{V}}^{\boldsymbol{{S}}}$

We construct an upper bound for the value function $V^{S}$ of the $\frac{S_n}{n}$ problem, where S can be any random walk with sub-Gaussian increments. The classical Chow–Robbins game is a special case of these stopping problems.

Some examples of sub-Gaussian random variables are:

• X with $P(X_i =-1) = P(X_i =1) = \frac{1}{2} $ is 1-sub-Gaussian.

• The normal distribution $\mathcal{N}(0,\sigma^2)$ is $\sigma^2$ -sub-Gaussian.

• The uniform distribution on $[-a,a]$ is $a^2$ -sub-Gaussian.

• Any random variable Y with values in a compact interval [a, b] is $\frac{1}{4}(b-a)^2$ -sub-Gaussian.

In the following we show that the value function $V^{W}$ of the continuous-time problem (2) is an upper bound for the value function $V^{S}$ whenever S is a random walk with 1-sub-Gaussian increments. We first state the solution of (2).

Let

\begin{equation*} h(t,x) \,:\!=\, \big(1-\alpha^2\big)\int_{0}^{\infty}\exp\bigg[ax-\frac{a^2}{2}t\bigg] \mathop{}\!\mathrm{d} a =\big(1-\alpha^2\big)\frac{1}{t}\frac{\Phi_{t}(x)}{\varphi_t(x)},\end{equation*}

where $\Phi_t(x) = \Phi\big(x/\sqrt{t}\big)$ denotes the cummulative distribution function of a centered normal distribution with variance $\sigma^2 = t$ , $\varphi_t$ is the corresponding density function, and $\alpha \approx 0.839\,923\,675\,692\,373$ is the unique solution to $\alpha \varphi(\alpha) = \big(1-\alpha^2\big)\Phi(\alpha)$ .

Lemma 1. The stopping problem (2) is solved by $\tau_{\ast} = \inf\{s\mid x+W_s\geq \alpha\sqrt{s+t}\}$ with value function

\begin{equation*}V^W(t,x) = \begin{cases} h(t,x) & {if } x \leq \alpha \sqrt{t},\\[5pt] \frac{x}{t} & {otherwise}. \end{cases}\end{equation*}

$V^{W}(t,x)$ is differentiable (smooth fit), and $h(t,x)\geq g(t,x) = \frac{x}{t}$ for all $t>0$ and $x\in \mathbb{R}$ .

This result was proved independently in [Reference Shepp9, Reference Walker10].

We now prove that $V^{W}$ is an upper bound for $V^{S}$ . We know from general theory that $V^{S}$ is the smallest superharmonic function dominating the gain function g (see, e.g., [Reference Peskir and Shiryaev8]). If we find a superharmonic function dominating g we have an upper bound for $V^{S}$ .

Proof.We first show the claim for fixed $a\in \mathbb{R}$ and $f(t,x) = \mathrm{e}^{ax - \frac{1}{2}a^2t}$ . We need to show that $\mathbb{E} [f(t+1,x+X_1)]\leq f(t,x)$ for all $t>0$ and $x\in \mathbb{R}$ , and calculate

(3) \begin{alignat}{2} & & \mathbb{E}\bigg[\exp\!\bigg\{a(x+X_{1}) - \frac{a^2}{2}(t+1)\bigg\}\bigg] & \leq \exp\!\bigg\{ax - \frac{a^2}{2}t\bigg\} \nonumber \\ \Longleftrightarrow & \quad & \exp\!\bigg\{ax - \frac{a^2}{2}(t+1)\bigg\} \mathbb{E}\big[\mathrm{e}^{aX_{1}}\big] & \leq \exp\!\bigg\{ax - \frac{a^2}{2}t\bigg\} \nonumber \\ \Longleftrightarrow & & \mathrm{e}^{-\frac{a^2}{2}} \mathbb{E}\big[\mathrm{e}^{aX_{1}}\big] & \leq 1 \nonumber \\ \Longleftrightarrow & & \mathbb{E}\big[\mathrm{e}^{aX_{1}}\big] & \leq \mathrm{e}^{\frac{a^2}{2}}. \end{alignat}

The last inequality (3) is just the defining property of a 1-sub-Gaussian random variable. By integration over a and multiplication by $(1-\alpha)$ , the result follows.

Theorem 1. (An upper bound for $V^{S}$ ) Let W be a standard Brownian motion, S a random walk with 1-sub-Gaussian increments, and

\begin{equation*} V^{S}(t,x) = \sup_{\tau }\mathbb{E} \left [ \frac{x + S_\tau}{t+\tau}\right], \qquad V^W(t,x)=\sup_{\tau }\mathbb{E} \left [ \frac{x+W_\tau}{t+\tau}\right ]. \end{equation*}

Then $V^{W}(t,x)\geq V^{S}(t,x)$ for all $t>0$ , $x\in \mathbb{R}$ .

2.1. The Chow–Robbins game

Let $X_1, X_2, \dots$ be i.i.d. random variables with $P(X_i =-1) =P(X_i =1) = \frac{1}{2} $ and $S_n = \sum_{i=1}^{n}X_i$ . The classical Chow–Robbins problem is given by

(4) \begin{equation} V^S(t,x)=\sup_{\tau }\mathbb{E} \left [ \frac{x + S_\tau}{t+\tau}\right ].\end{equation}

The $X_i$ are 1-sub-Gaussian with variance 1. An almost surely (a.s.) finite stopping time $\tau_{\ast}$ exists that solves (4) (see [Reference Dvoretzky3]). By Theorem 1 we get that $V^S(t,x)\leq V^{W}(t,x) = h(x,t)\textbf{1}_{\{x \leq \alpha \sqrt{t}\}} + \frac{x}{t}\textbf{1}_{\{x > \alpha\sqrt{t}\}}$ . We will see later that this upper bound is very tight. We will construct a lower bound for $V^S$ in the next section and give a rigorous computer analysis of the problem in Section 5.

Example 1. For some time it was unclear whether it is optimal to stop in (8, 2) or not. It was first shown in [Reference Medina and Zeilberger7] and later confirmed in [Reference Häggström and Wästlund4] that $(8,2)\in D^{S}$ (in [Reference Häggström and Wästlund4] this is written as 5–3, 5 heads–3 tails). We show here how to immediately prove this with our upper bound. We choose the time horizon $T=9$ , set $V_\mathrm{u}^{S}(T,x) = V^{W}(T,x)$ , and calculate with one-step backward induction $V_\mathrm{u}^{S}(8,2)$ as an upper bound for $V^{S}(8,2)$ : $V^{S}_\mathrm{u}(9,3) = \frac{3}{9} = \frac{1}{3}$ (since $3> \alpha\sqrt{9}$ ), $V^{S}_\mathrm{u}(9,1) = h(9,1) \approx 0.1642$ , and we get

\begin{align*} V^{S}(8,2) \leq V_\mathrm{u}^{S}(8,2) & = \max\left\{\frac{2}{8}, \frac{V^{S}_\mathrm{u}(9,3) + V^{S}_\mathrm{u}(9,1)}{2}\right\} , \\ \frac{V^{S}_\mathrm{u}(9,3) + V^{S}_\mathrm{u}(9,1)}{2} & = \frac{1}{6} + \frac{0.1642}{2}=0.2488 < \frac{2}{8}. \end{align*}

Hence, we have $V^{S}(8,2)\leq g(8,2) = \frac{2}{8}$ , and it follows that (8, 2) is in the stopping set. For a detailed description of the method see Section 5.

2.2. Generalizations

In the proof of Theorem 1 we did not use the specific form of the gain function $g(t,x) = \frac{x}{t}$ . All we needed was that:

• The value function of the stopping problem

  (5) \begin{equation} V^{W}(t,x) = \sup_{\tau }\mathbb{E} \left [ g(t+\tau,x + W_\tau)\right] \end{equation}
  is on C of the form $V^{W}\big|_{C}(t,x) = \int_{\mathbb{R}}\exp\Big[ax - \frac{1}{2}a^2t\Big]\mathop{}\!\mathrm{d} \mu(a)$ for a measure $\mu$ .

• The function $h(t,x) = \int_{\mathbb{R}}\exp\Big[ax - \frac{1}{2}a^2t\Big] \mathop{}\!\mathrm{d} \mu(a)$ dominates g on $\mathbb{R}^{+}\times\mathbb{R}$ .

• The boundary of the continuation set $\partial C^{S}$ of the stopping problem $V^{S}(t,x) = \sup_{\tau }\mathbb{E} \left [ g(t+\tau,x + S_\tau)\right]$ is the graph of a function $b \colon \mathbb{R}^{+}\to \mathbb{R}$ . (This requirement can easily be relaxed to the symmetric case, where $\partial C^{S} = \mathrm{Graph}(b) \cup \mathrm{Graph}(-b)$ .)

These requirements are not very restrictive, and there are many other gain functions and associated stopping problems for which this kind of upper bound can be constructed. A set of examples which fulfill these requirements and for which (5) is explicitly solvable can be found in [Reference Peskir and Shiryaev8]. Some of these are:

\begin{alignat*}{2} g(t,x) & = \frac{x^{2d-1}}{t^{q}} & & \text{with } d\in \mathbb{N} \text{ and } q>d-\frac{1}{2}, \\ g(t,x) & = |x|-\beta\sqrt{t} \qquad & & \text{for some } \beta \geq 0, \\ g(t,x) & = \frac{|x|}{t}. & &\end{alignat*}

3. A lower bound for $\boldsymbol{{V}}^{\boldsymbol{{S}}}$

In this section we want to give a lower bound for the value function of the Chow–Robbins game (4). Here, S will always be a symmetric Bernoulli random walk. The basis of our construction is the following lemma.

We modify the function $h(t,x)=\big(1-\alpha^2\big)\int_{0}^{\infty}\exp\Big[ax-\frac{a^2}{2}t\Big] \mathop{}\!\mathrm{d} a$ from Lemma 1 slightly to

(6) \begin{equation} h_{c}(t,x) \,:\!=\, K \int_{0}^{\infty}\exp\bigg[ax-\frac{c}{2}a^2t\bigg] \mathop{}\!\mathrm{d} a\end{equation}

for some $0 < c < 1$ and $K>0$ to match the assumptions of Lemma 3. As a stopping time we choose $\tau_0 = \inf \big\{n\geq 0\mid x+S_n \geq \alpha \sqrt{t+n}-1\big\}$ . Unfortunately there is no c such that (6) is globally S-subharmonic, and hence we have to choose c depending on the time horizon T. This makes the following result a bit technical.

Theorem 2. (A lower bound for $V^{S}$ ) Let

\begin{equation*}h_c(t,x)\,:\!=\,K \int_{0}^{\infty}\exp\bigg[ax-\frac{c}{2}a^2t\bigg] \mathop{}\!\mathrm{d} a = K\frac{1}{ct}\frac{\Phi_{ct}(x)}{\varphi_{ct}(x)}, \qquad K = \alpha c \frac{\varphi_{c}(\alpha)}{\Phi_{c}(\alpha)}.\end{equation*}

Given a time horizon $T>0$ , let $c_1$ be the biggest solution smaller than 1 to $\frac{1}{2}\big(h_{c}\big(T+1, \alpha\sqrt{T}-1\big)+h_{c}\big(T+1,\alpha\sqrt{T}+1\big)\big) = h_{c}\big(T,\alpha\sqrt{T}\big)$ , $c_2$ the unique positive solution of

(7) \begin{equation} h_c\Big(T,\alpha\sqrt{T}-1\Big)=\frac{\alpha\sqrt{T}-1}{T} , \end{equation}

and $c=\min\{c_1,c_2\}$ . Let $a_0$ be the unique positive solution (in a) to $\frac{1}{2}\left(e^{a}+e^{-a}\right)e^{-\frac{c}{2} a^2}=1$ . If

(8) \begin{equation} T\geq\left(\frac{\alpha}{a_0c}\right)^2, \end{equation}

then $h_c(t,x)$ is a lower bound for $V^{S}(t,x)$ for all $t\geq T$ and $x\leq \alpha \sqrt{t}$ .

Remark 1. Our numerical evaluations suggest that for $T\geq 4$ (8) is always satisfied, and for $T\geq 200$ we always have $c=c_1$ .

Figure 1.

The upper bound $V^{W}$ and the lower bound $h_c$ for a fixed T. For a better illustration $c=0.6$ is chosen very small.

Proof. We divide the proof into three parts. First, we show that the stopped process $h_c\big(t\wedge\tau_0,x+S_{t\wedge\tau_0}\big)_{t\geq T}$ is a submartingale; second, we calculate K; and third, we show that $h\big(\tau_0,x+S_{\tau_0}\big)\leq g\big(\tau_0,x+S_{\tau_0}\big)$ $P_{T,x}$ -a.s. and use Lemma 3 to prove the statement. An illustration of the setting is given in Figure 1.

First, we have to show that $\frac{1}{2}\!\left(h_{c}(t+1,x-1)+h_{c}(t+1,x+1)\right) \geq h_{c}(t,x)$ for every $t\geq T$ and $x\leq \alpha \sqrt{t}-1$ ; we will even show that it applies for all $x\leq \alpha \sqrt{t}$ . The constant K has no influence on this inequality, so we set it to 1 for now. We have

(9) \begin{align} f_c(t,x)& \,:\!=\, \frac{1}{2}\big(h_{c}(t+1,x-1)+h_{c}(t+1,x+1)\big) - h_{c}(t,x) \nonumber \\ & = \int_{0}^{\infty}\frac{1}{2} \exp\bigg[a(x+1)-\frac{c}{2}a^2(t+1)\bigg]\mathop{}\!\mathrm{d} a + \int_{0}^{\infty}\frac{1}{2} \exp\bigg[a(x-1)-\frac{c}{2}a^2(t+1)\bigg] \mathop{}\!\mathrm{d} a \nonumber \\ & \quad - \int_{0}^{\infty}\exp\bigg[ax-\frac{c}{2}a^2t\bigg] \mathop{}\!\mathrm{d} a \nonumber \\ & = \int^{\infty}_{0}\exp\bigg[ax-\frac{c}{2}a^2t\bigg]\left[\frac{1}{2}\big(\mathrm{e}^a+\mathrm{e}^{-a}\big)\mathrm{e}^{-\frac{c}{2}a^2}-1 \right ]\mathop{}\!\mathrm{d} a. \end{align}

The function $\lambda(a)\,:\!=\,\frac{1}{2}\big(\mathrm{e}^a+\mathrm{e}^{-a}\big)e^{-\frac{c}{2}a^2}-1$ has a unique positive root $a_0$ ; for $a\in[0,a_0]$ we have $\lambda(a)\geq 0$ , and for $a\geq a_0$ , $\lambda(a)\leq 0$ . Suppose, for given (t, x), we have $f_c(t,x)\geq 0$ . Let $\delta \geq 0$ , $\varepsilon \in \mathbb{R}$ ; we have

\begin{align*} f_c(t+\delta,x+\varepsilon) & = \int^{a_0}_{0}\exp\bigg[ax-\frac{c}{2}a^2t\bigg] \lambda(a) \exp\bigg[\varepsilon a - \delta \frac{c}{2} a^2\bigg] \mathop{}\!\mathrm{d} a \\ & \quad + \int^{\infty}_{a_0}\exp\bigg[ax-\frac{c}{2}a^2t\bigg] \lambda(a) \exp\bigg[\varepsilon a - \delta \frac{c}{2} a^2\bigg] \mathop{}\!\mathrm{d} a \\ & \overset{(\ast)}\geq \int^{a_0}_{0}\exp\bigg[ax-\frac{c}{2}a^2t\bigg] \lambda(a) \exp\bigg[\varepsilon a_0 - \delta \frac{c}{2} a_0^2\bigg] \mathop{}\!\mathrm{d} a \\ & \quad + \int^{\infty}_{a_0}\exp\bigg[ax-\frac{c}{2}a^2t\bigg] \lambda(a) \exp\bigg[\varepsilon a_{0} - \delta \frac{c}{2} a_0^2\bigg] \mathop{}\!\mathrm{d} a \\ & = \exp\bigg[\varepsilon a_{0} - \delta \frac{c}{2} a_0^2\bigg]\, f_c(t,x) \geq 0. \end{align*}

Here, $(\ast)$ is true if $\varepsilon a - \delta \frac{c}{2} a^2 \geq \varepsilon a_{0} - \delta \frac{c}{2} a_0^2$ for $a\leq a_{0}$ and $\varepsilon a - \delta \frac{c}{2} a^2 \leq \varepsilon a_{0} - \delta \frac{c}{2} a_0^2$ for $a\geq a_{0}$ , which is the case if

(10) \begin{equation} \varepsilon \leq a_0 \delta \frac{c}{2}. \end{equation}

By assumption, we have $f_c(T,\alpha \sqrt{T})\geq 0$ . (If $c=c_1 $ as in all our computational examples, this is clear. If $c=c_2<c_1$ , inspection of $f_c$ in (9) shows that $f_c>f_{c_1}$ .) The function $\alpha \sqrt{t}$ is concave and

\begin{equation*}\frac{\partial}{\partial t}\alpha\sqrt{t}=\frac{\alpha}{2\sqrt{t}\,},\end{equation*}

so for $t\geq T$ and $x\leq \alpha\sqrt{t}$ with $(t,x)=\big(T+\delta,\alpha \sqrt{T}+\varepsilon\big)$ we have

\begin{equation*}\varepsilon\leq \delta\frac{\alpha}{2\sqrt{T}\,}.\end{equation*}

Putting this into (10) we get the condition

\begin{equation*}\delta\frac{\alpha}{\sqrt{T}\,}\leq a_0 \delta c, \text{ i.e. } T \geq \left(\frac{\alpha}{a_0c}\right)^2,\end{equation*}

which is true by assumption. That concludes the first part of the proof.

Second, we want to choose K such that $h_c\big(t,\alpha\sqrt{t}\big)=g\big(t,\alpha\sqrt{t}\big) = \frac{\alpha}{\sqrt{t}\,}$ . We first show that this is possible, and then calculate K. We have

\begin{align*} h_c(t,x ) & = K \int_{0}^{\infty}\exp\bigg[ax-\frac{c}{2}a^2t\bigg] \mathop{}\!\mathrm{d} a = K\frac{1}{ct}\frac{\Phi_{ct}(x)}{\varphi_{ct}(x)} , \\ h_c\big(t,\alpha\sqrt{t}\big) & = K\frac{1}{ct}\frac{\Phi_{ct}\big(\alpha\sqrt{t}\big)}{\varphi_{ct}\big(\alpha\sqrt{t}\big)} = K\frac{1}{c\sqrt{t}\,}\frac{\Phi_{c}(\alpha)}{\varphi_{c}(\alpha)} , \end{align*}

which depends only on $\frac{1}{\sqrt{t}\,}$ . Solving $h_c\big(t,\alpha\sqrt{t}\big) = \frac{\alpha}{\sqrt{t}\,}$ we get

\begin{equation*}K = \alpha c \frac{\varphi_{c}(\alpha)}{\Phi_{c}(\alpha)}.\end{equation*}

Third, we chose $\tau_0 = \inf \big\{n\geq 0\mid x+S_n \geq \alpha \sqrt{t+n}-1\big\}$ and need to show that $h_c(\tau_0,S_{\tau_0})\leq g(\tau_0,S_{\tau_0})$ . It is clear that $S_{\tau_0}\in \big[\alpha\sqrt{\tau_0}-1,\alpha\sqrt{\tau_0}\big]$ . By the construction of K in the second part, we know that $h_c\big(t,\alpha\sqrt{t}\big)= g\big(t,\alpha\sqrt{t}\big)$ . Since $h_c$ has strictly positive curvature, we know that $h(t, \cdot)$ has exactly one more intersection with $g(t,\cdot)$ , which we denote by $\alpha \sqrt{t}-d(t)$ . We will see that $d(t) \geq 1$ for $t\geq T$ and hence $h_c(t,x)\leq g(t,x)$ for $x\in \big[\alpha\sqrt{t}-d(t),\alpha\sqrt{t}\big]$ . We saw in the second part that $\sqrt{t}\cdot h_c\big(t,\beta\sqrt{t}\big)$ is constant for any $\beta>0$ . If, for some $x_0$ , $h_c(T,x_0)\leq g(T,x_0)=\frac{x_0}{T}$ , we set $\beta \,:\!=\,\frac{x_0}{\sqrt{T}\,}$ and see that, for all $t>T$ ,

\begin{equation*}h\bigg(t,\frac{x_0}{\sqrt{T}\,}\sqrt{t}\bigg) \leq g\bigg(t,\frac{x_0}{\sqrt{T}\,}\sqrt{t}\bigg) = \frac{1}{\sqrt{t}\,}\frac{x_0}{\sqrt{T}\,}.\end{equation*}

If $x_0\leq \alpha\sqrt{T}-1$ , then $ \frac{x_0}{\sqrt{T}\,}\sqrt{t}\leq \alpha\sqrt{t}-1$ . If $d(T) \geq 1 $ then we set $x_0 \,:\!=\, \alpha \sqrt{T}-d(T)$ . We can now conclude that for $t \geq T$ we have $d(t) \geq 1$ , hence it is enough to show that $d(T)\geq 1$ . For $c=c_2$ this is true by assumption. In general $c\leq c_2$ , and we have $\frac{\partial }{\partial x}h_c(t,x) \leq \frac{\partial }{\partial x}h_{c_2}(t,x)$ . Since $h_{c_2}\big(T,\alpha \sqrt{T}\big)= h_{c_2}\big(T,\alpha \sqrt{T}\big)$ we have

\begin{equation*}h_{c}\Big(T,\alpha \sqrt{T}-1\Big)\leq h_{c_2}\Big(T,\alpha \sqrt{T}-1\Big)=\frac{\alpha \sqrt{T}-1}{T}\end{equation*}

and the statement follows. Now $h_c$ and $\tau_0$ fulfill the conditions of Lemma 3. This completes the proof.

Some values for c are given in Table 1.

Table 1.

Values of c for various T.

4. Error of the bounds

We want to show that the relative error of the constructed bounds is of order $\mathcal{O}\big(\frac{1}{T}\big)$ for $x\geq 0$ . First, we show that $c = c(T) \geq \frac{T-1}{T}$ for T large enough. Indeed, for $c_1$ , evaluating (9) for $c = \frac{T}{T+1}$ yields

\begin{equation*} f_{\frac{T}{T+1}}(T,x) = \int^{\infty}_{0}\exp\bigg[ax-\frac{1}{2}a^2T\bigg]\left[\frac{1}{2}\big(\mathrm{e}^a+\mathrm{e}^{-a}\big)-\mathrm{e}^{\frac{1}{2}\frac{1}{T+1}} \right ]\mathop{}\!\mathrm{d} a,\end{equation*}

which can be seen to be positive for T large enough, yielding $c_1\geq \frac{T}{T+1}\geq \frac{T-1}{T}$ . We evaluate (7) for $c = \frac{T-1}{T}$ and get, with elementary estimates,

\begin{align*} h_{\frac{T-1}{T}}\Big(T,\alpha\sqrt{T}-1\Big) & = \frac{K}{\sqrt{T-1}\,}\frac{\Phi\left(\frac{\alpha \sqrt{T}-1}{\sqrt{T}}\right)}{\varphi\left(\frac{\alpha \sqrt{T}-1}{\sqrt{T}}\right)}\\[2pt] & \leq \frac{K}{\sqrt{T-1}\,}\left(\frac{\Phi\left(\frac{\alpha \sqrt{T}}{\sqrt{T}}\right) - \frac{1}{\sqrt{T-1}\,}\varphi\left(\frac{\alpha \sqrt{T}}{\sqrt{T}}\right)}{\varphi\left(\frac{\alpha \sqrt{T}}{\sqrt{T}}\right)\exp\left[\frac{\alpha\sqrt{T}-\frac{1}{2}}{T-1}\right]}\right) \\[2pt] & = \exp\bigg[{-}\frac{\alpha\sqrt{T}-\frac{1}{2}}{T-1}\bigg]\left(\frac{\alpha }{\sqrt{T}\,} - \frac{K}{T-1}\right) \leq \frac{\alpha \sqrt{T}-1}{T}\end{align*}

for T large enough, so that $c_2 \geq \frac{T-1}{T}$ . We obtain $c = \min \{c_1,c_2\}\geq \frac{T-1}{T}$ . We now calculate the asymptotic relative error between $V_\mathrm{u}$ and $V_\mathrm{l}$ in $x = 0$ :

\begin{align*} & \frac{V_\mathrm{u}(T,0)}{V_\mathrm{l}(T,0)}-1 = \frac{h(T,0)}{h_c(T,0)}-1 = \frac{1-\alpha^2}{K}\sqrt{c}-1 =\frac{1-\alpha^2}{\alpha}\frac{\Phi\left(\frac{\alpha}{\sqrt{c}\,}\right)}{\varphi\left(\frac{\alpha}{\sqrt{c}\,}\right)}-1 .\end{align*}

We use the approximation

\begin{align*} \frac{\Phi\left(\frac{\alpha}{\sqrt{c}\,}\right)}{\varphi\left(\frac{\alpha}{\sqrt{c}\,}\right)} & \approx \exp\bigg[{-}\frac{\alpha^2(c-1)}{2c}\bigg]\left(\frac{\Phi(\alpha)}{\varphi(\alpha)} + \frac{\alpha\big(1-\sqrt{c}\big)}{\sqrt{c}}\right) \\ & = \exp\bigg[{-}\frac{\alpha^2(c-1)}{2c}\bigg]\left(\frac{\alpha}{1-\alpha^2} + \frac{\alpha\big(1-\sqrt{c}\big)}{\sqrt{c}}\right)\end{align*}

and get, with $c = \frac{T-1}{T}$ ,

\begin{align*} \frac{h(T,0)}{h_c(T,0)}-1 & \approx \exp\bigg[-\frac{\alpha^2(c-1)}{2c}\bigg]\left(1+\frac{\alpha\big(1-\sqrt{c}\big)}{\sqrt{c}}\right) -1\\ & = \exp\bigg[\frac{\alpha^2}{2T-2}\bigg]\left(1+\alpha\left(\sqrt{\frac{T-1}{T}}-1\right)\right)-1 = \mathcal{O}\bigg(\frac{1}{T}\bigg).\end{align*}

It is now straightforward to check that, for $\alpha \sqrt{T} \geq x\geq 0$ ,

\begin{equation*}\frac{h(T,0)}{h_c(T,0)}-1 \geq \frac{h(T,x)}{h_c(T,x)}-1. \end{equation*}

This yields

\begin{equation*}\frac{V(T,x)}{V_\mathrm{l}(T,x)}-1 =\mathcal{O}\left(\frac{1}{T}\right) , \qquad \frac{V(T,x)}{V_\mathrm{u}(T,x)}-1 =\mathcal{O}\left(\frac{1}{T}\right),\end{equation*}

for all $\alpha \sqrt{T} \geq x\geq 0$ .

5. Computational results

In this section we show how to compute the continuation and stopping set for the Chow–Robbins game. In 2013, Häggström and Wästlund [Reference Häggström and Wästlund4] computed stopping and continuation points starting from (0, 0). They used another unsymmetric notation for the problem. We give their bounds transformed into our setting. They chose a, rather large, time horizon of $T=10^{7}$ , and set $V^S_\mathrm{l}(T,x)= \max\left\{\frac{x}{T},0\right\}$ as a lower bound and

\begin{equation*}V^S_\mathrm{u}(T,x)= \max\left\{\frac{x}{T},0\right\} + \min\left\{\sqrt{\frac{\pi}{T}},\frac{1}{|x|}\right\}\end{equation*}

as an upper bound. Then they used backward induction to calculate $V^S(n,x)$ for $n<T$ and $i\in\{\mathrm{u},\mathrm{l}\}$ with $V_{i}^S(n,x) = \max \left \{ \frac{x}{n}, \mathbb{E}\big[V_i^{S}(n+1,x+X_i)\big] \right \}$ . If $V_\mathrm{u}(n,x)=\frac{x}{n}$ then $(n,x)\in D$ ; if $V_\mathrm{l}(n,x)>\frac{x}{n}$ then $(n,x)\in C$ . In this way they were able to decide for all but seven points $(n,x)\in\mathbb{N}\times\mathbb{Z}$ with $n\leq 1000$ whether they belong to C or D.

We use backward induction from a finite time horizon as well, but use the much sharper bounds given in Sections 2 and 3. For our upper bound this has a nice intuition. We play the Chow–Robbins game up to the time horizon T, then we change the game to the favorable $\frac{W_t}{t}$ game, which slightly rises our expectation.

With a time horizon of $T=10^{6}$ we are able to calculate all the stopping and continuation points $(n,x)\in\mathbb{N}\times\mathbb{Z}$ with $n\leq 489\,241$ . We show that all open points in [Reference Häggström and Wästlund4] belong to D.

Table 2.

Exceptions for Theorem 3.

Unlike [Reference Häggström and Wästlund4] we use the symmetric notation. Let $X_i$ be i.i.d. random variables with $P(X_i =-1) =P(X_i =1) = \frac{1}{2} $ and $S_n=\sum^{n}_{i=1} X_i$ . We choose a time horizon T and use $V^{W}$ given in Lemma 1 as an upper bound, $V^S_\mathrm{u}(T,x)= V^{W}(T,x)$ , and $h_c$ given in Theorem 2 as a lower bound, $V^S_\mathrm{l}(T,x)= h_c(T,x)$ , for $x\in \mathbb{Z}$ with $x\leq \alpha \sqrt{T}$ . For $i\in\{\mathrm{u},\mathrm{l}\}$ we now recursively calculate $V_i^S(n,x) = \max \left \{ \frac{x}{n}, \frac{1}{2}\big(V_i^S(n+1,x+1) + V_i^S(n+1,x-1)\big) \right \}$ . If $V_\mathrm{l}(n,x)>\frac{x}{n}$ , then $(n,x)\in C$ . To check if $(n,x)\in D$ we use, instead of $V_\mathrm{u}(n,x)=\frac{x}{n}$ , the slightly stronger, but numerically easier to evaluate, condition $(n,x)\in D$ if $\frac{1}{2}\big(V_\mathrm{u}^S(n+1,x+1) + V_\mathrm{u}^S(n+1,x-1)\big)< \frac{x}{n}$ . We use $T=10^{6}$ to calculate V(0, 0) and the integer thresholds $\hat b(n) \,:\!=\, \lceil b(n) \rceil$ . For 34 values of $n\leq 10^{6}$ the exact value $\hat b(n)$ cannot be determined this way; the smallest such value is $n = 489\,242$ .

Theorem 3. For the stopping problem (4) starting in $(0,0)$ , the stopping boundary $\hat b$ for $n\leq 489\,241$ is given by

(11) \begin{equation} \hat b(n)=\left \lceil \alpha\sqrt{n} - \frac{1}{2} + \frac{1}{7.9+4.54\sqrt[4]{n}\,} \right \rceil \end{equation}

with the eight exceptions shown in Table 2. For the value function we have

\begin{equation*}0.585\,907\,012\,8172 \leq V^{S}(0,0) \leq 0.585\,907\,012\,8182.\end{equation*}

Häggström and Wästlund used a different notation (denoted with a ^′ here), with $P\big(X^{\prime}_i =0\big)$ $=P\big(X^{\prime}_i =1\big) = \frac{1}{2}$ . Our functions and values translate to $ V(n,x) = 2V^{\prime}\big(n,\frac{x+n}{2}\big)-1$ , $b^{\prime}(n)=\left \lceil \frac{\alpha\sqrt{n}+n}{2} -\rho^{\prime}(n) \right \rceil$ with $\rho^{\prime}(n) = \frac{1}{4} - \frac{1}{15.8+9\sqrt[4]{n}\,}$ , and

\begin{equation*}0.792\,953\,506\,4086 \leq V^{\prime}(0,0) \leq 0.792\,953\,506\,4091.\end{equation*}

The value of V(0, 0) is calculated with $T=2\cdot10^{6}$ .

We also calculated $V^{S}$ and b for non-integer values. We did this by choosing an integer D and then calculating $V^{S}$ on $\frac{1}{D}\mathbb{N}\times\frac{1}{D}\mathbb{Z}$ with the method described above; for most plots we used $D=300$ . Some plots of b and $V^{S}$ are given in Figures 2–4. The method enables us to get very detailed impressions of b and $V^{S}$ that inspire further analytical research. In [Reference Christensen and Fischer2] the authors showed that $V^S$ is not differentiable on a dense subset of $C^S$ , and that $C^S$ is not convex.

Figure 2.

The boundaries of the continuation sets. While asymptotically similar, they behave differently close to 0.

Figure 3.

The value functions $V^{W}$ and $V^{S}$ in $t=1$ . $V^{S}$ does not follow the smooth fit principle and is not everywhere smooth on C.

Figure 4.

The value functions $V^{W}$ and $V^{S}$ in $t=10$ .