Robbins' problem

<h2 id="importance">Importance</h2>
One of the motivations to study Robbins' problem is that with its solution all classical (four) <a href="/facts/Secretary_problem/JNFqX2zR">secretary problems</a> would be solved. But the major reason is to understand how to cope with full history dependence in a (deceptively easy-looking) problem.
On the Ester's Book International Conference in Israel (2006) Robbins' problem was accordingly named one of the four most important problems in the field of <a href="/facts/Optimal_stopping/33AYC76Y">optimal stopping</a> and <a href="/facts/Sequential_analysis/K8nla6cd">sequential analysis</a>.

<h2 id="history">History</h2>
<a href="/facts/Herbert_Robbins/Gk2X6ap9">Herbert Robbins</a> presented the above described problem at the International Conference on Search and Selection in Real Time<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> in <a href="/facts/Amherst%2c_Massachusetts/u8KnDYqx">Amherst</a>, 1990. He concluded his address with the words I should like to see this problem solved before I die. Scientists working in the field of optimal stopping have since called this problem Robbins' problem. Unfortunately, Herbert Robbins' wish did not become true. He died in 2001.

<h2 id="chowrobbins-game">Chow–Robbins game</h2>
Another optimal stopping problem bearing Robbins' name (and not to be c onfused with Robbins' problem) is the Chow–Robbins game:<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><blockquote>Given an infinite sequence of <a href="/facts/Independent_and_identically_distributed_random_variables/othIRaWt">IID</a> random variables 
 
 
 
 
 X
 
 1
 
 
 ,
 
 X
 
 2
 
 
 ,
 .
 .
 .
 
 
 {\displaystyle X_{1},X_{2},...}
 
 with distribution 
 
 
 
 F
 
 
 {\displaystyle F}
 
, how to decide when to stop, in order to maximize the sample average 
 
 
 
 
 
 1
 n
 
 
 (
 
 X
 
 1
 
 
 +
 ⋯
 
 X
 
 n
 
 
 )
 
 
 {\displaystyle {\frac {1}{n}}(X_{1}+\cdots X_{n})}
 
 where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is the stopping time?
The probability of eventually stopping must be 1 (that is, you are not allowed to keep sampling and never stop).</blockquote>For any distribution 
 
 
 
 F
 
 
 {\displaystyle F}
 
 with finite second moment, there exists an optimal strategy, defined by a sequence of numbers 
 
 
 
 
 β
 
 1
 
 
 ,
 
 β
 
 2
 
 
 ,
 .
 .
 .
 
 
 {\displaystyle \beta _{1},\beta _{2},...}
 
. The strategy is to keep sampling until 
 
 
 
 
 
 1
 n
 
 
 (
 
 X
 
 1
 
 
 +
 ⋯
 
 X
 
 n
 
 
 )
 ≥
 
 β
 
 n
 
 
 
 
 {\displaystyle {\frac {1}{n}}(X_{1}+\cdots X_{n})\geq \beta _{n}}
 
.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a><a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
<h3>Optimal strategy for very large n</h3>
If 
 
 
 
 F
 
 
 {\displaystyle F}
 
 has finite second moment, then after subtracting the mean and dividing by the standard deviation, we get a distribution with mean zero and variance one. Consequently it suffices to study the case of 
 
 
 
 F
 
 
 {\displaystyle F}
 
 with mean zero and variance one.
With this, 
 
 
 
 
 lim
 
 n
 
 
 
 β
 
 n
 
 
 
 /
 
 
 
 n
 
 
 ≈
 α
 =
 0.8399236757
 
 
 {\displaystyle \lim _{n}\beta _{n}/{\sqrt {n}}\approx \alpha =0.8399236757}
 
, where 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 is the solution to the equation<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
 
 
 
 α
 =
 
 (
 
 1
 −
 
 α
 
 2
 
 
 
 )
 
 
 ∫
 
 0
 
 
 ∞
 
 
 
 e
 
 λ
 α
 −
 
 λ
 
 2
 
 
 
 /
 
 2
 
 
 d
 λ
 
 
 {\displaystyle \alpha =\left(1-\alpha ^{2}\right)\int _{0}^{\infty }e^{\lambda \alpha -\lambda ^{2}/2}d\lambda }
 
which can be proved by solving the same problem with continuous time, with a <a href="/facts/Wiener_process/KPh7vYd7">Wiener process</a>. At the limit of 
 
 
 
 n
 →
 ∞
 
 
 {\displaystyle n\to \infty }
 
, the discrete time problem becomes the same as the continuous time problem.
This was proved independently<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> by.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>
When the game is a fair coin toss game, with heads being +1 and tails being -1, then there is a sharper result<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>
 
 
 
 
 β
 
 n
 
 
 =
 α
 
 
 n
 
 
 −
 1
 
 /
 
 2
 +
 
 
 
 (
 −
 2
 ζ
 (
 −
 1
 
 /
 
 2
 )
 )
 
 
 α
 
 
 
 
 π
 
 
 
 
 n
 
 −
 1
 
 /
 
 4
 
 
 +
 O
 
 (
 
 n
 
 −
 7
 
 /
 
 24
 
 
 )
 
 
 
 {\displaystyle \beta _{n}=\alpha {\sqrt {n}}-1/2+{\frac {(-2\zeta (-1/2)){\sqrt {\alpha }}}{\sqrt {\pi }}}n^{-1/4}+O\left(n^{-7/24}\right)}
 
where 
 
 
 
 ζ
 
 
 {\displaystyle \zeta }
 
 is the <a href="/facts/Riemann_zeta_function/MnfRu7lY">Riemann zeta function</a>.

<h3>Optimal strategy for small n</h3>
When n is small, the asymptotic bound does not apply, and finding the value of 
 
 
 
 
 β
 
 n
 
 
 
 
 {\displaystyle \beta _{n}}
 
 is much more difficult. Even the simplest case, where 
 
 
 
 
 X
 
 1
 
 
 ,
 
 X
 
 2
 
 
 ,
 .
 .
 .
 
 
 {\displaystyle X_{1},X_{2},...}
 
 are fair coin tosses, is not fully solved.
For the fair coin toss, a strategy is a binary decision: after 
 
 
 
 n
 
 
 {\displaystyle n}
 
 tosses, with k heads and (n-k) tails, should one continue or should one stop? Since 1D random walk is recurrent, starting at any 
 
 
 
 k
 ,
 (
 n
 −
 k
 )
 
 
 {\displaystyle k,(n-k)}
 
, the probability of eventually having more heads than tails is 1. So, if 
 
 
 
 k
 ≤
 n
 −
 k
 
 
 {\displaystyle k\leq n-k}
 
, one should always continue. However, if 
 
 
 
 k
 >
 n
 −
 k
 
 
 {\displaystyle k>n-k}
 
, it is tricky to decide whether to stop or continue.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>
<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a> found an exact solution for all 
 
 
 
 n
 ≤
 489241
 
 
 {\displaystyle n\leq 489241}
 
.
Elton<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a> found exact solutions for all 
 
 
 
 n
 ≤
 9.06
 ×
 
 10
 
 7
 
 
 
 
 {\displaystyle n\leq 9.06\times 10^{7}}
 
, and it found an almost always optimal decision rule, of stopping as soon as 
 
 
 
 k
 −
 (
 n
 −
 k
 )
 ≥
 Δ
 
 k
 
 n
 
 
 
 
 {\displaystyle k-(n-k)\geq \Delta k_{n}}
 
 where
 
 
 
 Δ
 
 k
 
 n
 
 
 =
 
 ⌈
 
 α
 
 
 n
 
 
 
 
 −
 1
 
 /
 
 2
 
 
 +
 
 
 
 
 
 
 (
 
 −
 2
 ζ
 (
 −
 1
 
 /
 
 2
 )
 
 )
 
 
 
 α
 
 
 
 
 π
 
 
 
 
 
 n
 
 −
 1
 
 /
 
 4
 
 
 
 
 ⌉
 
 
 
 {\displaystyle \Delta k_{n}=\left\lceil {\alpha {\sqrt {n}}\,\,-1/2\,\,+\,\,{\frac {\left({-2\zeta (-1/2)}\right){\sqrt {\alpha }}}{\sqrt {\pi }}}{n^{-1/4}}}\right\rceil }

<h2 id="footnotes">Footnotes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Chow, Y.S.; Moriguti, S.; Robbins, Herbert Ellis; Samuels, Stephen M. (1964). "Optimal Selection Based on Relative Rank". Israel Journal of Mathematics. 2 (2): 81–90. doi:10.1007/bf02759948. <a href="/wiki/Herbert_Robbins" target="_blank">/wiki/Herbert_Robbins</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Bruss, F. Thomas (2005). "What is known about Robbins' Problem?". Journal of Applied Probability. 42 (1): 108–120. doi:10.1239/jap/1110381374. JSTOR 30040773. <a href="/wiki/F._Thomas_Bruss" target="_blank">/wiki/F._Thomas_Bruss</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Bruss, F.Thomas; Ferguson, S. Thomas (1993). "Minimizing the expected rank with full information". Journal of Applied Probability. 30 (3): 616–626. doi:10.1007/bf02759948. ISSN 0021-9002. JSTOR 3214770. <a href="/wiki/F._Thomas_Bruss" target="_blank">/wiki/F._Thomas_Bruss</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Bruss, F.Thomas; Ferguson, S. Thomas (1996). "Half-Prophets and Robbins' Problem of Minimizing the expected rank". Lecture Notes in Statistics (LNS). Athens Conference on Applied Probability and Time Series Analysis. Vol. 114. New York, NY: Springer New York. pp. 1–17. doi:10.1007/978-1-4612-0749-8_1. ISBN 978-0-387-94788-4. <a href="978-0-387-94788-4" target="_blank">978-0-387-94788-4</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Assaf, David; Samuel-Cahn, Ester (1996). "The secretary problem: Minimizing the expected rank with i.i.d. random variables". Advances in Applied Probability. 28 (3): 828–852. doi:10.2307/1428183. ISSN 0001-8678. JSTOR 1428183. <a href="/wiki/Ester_Samuel-Cahn" target="_blank">/wiki/Ester_Samuel-Cahn</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Bruss, F. Thomas; Swan, Yvik C. (2009). "What is known about Robbins' Problem?". Journal of Applied Probability. 46 (1): 1–18. doi:10.1239/jap/1238592113. JSTOR 30040773. <a href="/wiki/F._Thomas_Bruss" target="_blank">/wiki/F._Thomas_Bruss</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Krieger, Abba M.; Samuel-Cahn, Ester (2009). "The secretary problem of minimizing the expected rank: a simple suboptimal approach with generalization". Advances in Applied Probability. 41 (4): 1041–1058. doi:10.1239/aap/1261669585. JSTOR 27793918. <a href="/wiki/Ester_Samuel-Cahn" target="_blank">/wiki/Ester_Samuel-Cahn</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">The Joint Summer Research Conferences in the Mathematical Sciences were held at the University of Massachusetts from June 7 to July 4, 1990. These were sponsored by the AMS, SIAM, and the Institute for Mathematical Statistics (IMS). Topics in 1990 were: Probability models and statistical analysis for ranking data, Inverse scattering on the line, Deformation theory of algebras and quantization with applications to physics, Strategies for sequential search and selection in real time, Schottky problems, and Logic, fields, and subanalytic sets.
 <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Chow, Y. S.; Robbins, Herbert (September 1965). "On optimal stopping rules for $S_{n}/n$". Illinois Journal of Mathematics. 9 (3): 444–454. doi:10.1215/ijm/1256068146. ISSN 0019-2082. <a href="/wiki/Herbert_Robbins" target="_blank">/wiki/Herbert_Robbins</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Elton, John H. (2023-06-06). "Exact Solution to the Chow-Robbins Game for almost all n, using the Catalan Triangle". arXiv:2205.13499 [math].{{cite arXiv}}: CS1 maint: date and year (link) <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Dvoretzky, Aryeh. "Existence and properties of certain optimal stopping rules." Proc. Fifth Berkeley Symp. Math. Statist. Prob. Vol. 1. 1967. <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Teicher, H.; Wolfowitz, J. (1966-12-01). "Existence of optimal stopping rules for linear and quadratic rewards". Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete. 5 (4): 361–368. doi:10.1007/BF00535366. ISSN 1432-2064. <a href="https://doi.org/10.1007/BF00535366" target="_blank">https://doi.org/10.1007/BF00535366</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">import numpy as np
from scipy.integrate import quad
from scipy.optimize import root

def f(lambda_, alpha):
    return np.exp(lambda_ * alpha - lambda_**2 / 2)

def equation(alpha):
    integral, error = quad(f, 0, np.inf, args=(alpha))
    return integral * (1 - alpha**2) - alpha

solution = root(equation, 0.83992, tol=1e-15)

# Print the solution
if solution.success:
 print(f"Solved α = {solution.x[0]} with a residual of {solution.fun[0]}")
else:
 print("Solution did not converge")
 <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Simons, Gordon; Yao, Yi-Ching (1989-08-01). "Optimally stopping the sample mean of a Wiener process with an unknown drift". Stochastic Processes and Their Applications. 32 (2): 347–354. doi:10.1016/0304-4149(89)90084-7. ISSN 0304-4149. <a href="https://dx.doi.org/10.1016/0304-4149%2889%2990084-7" target="_blank">https://dx.doi.org/10.1016/0304-4149%2889%2990084-7</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Shepp, L. A. (June 1969). "Explicit Solutions to Some Problems of Optimal Stopping". The Annals of Mathematical Statistics. 40 (3): 993–1010. doi:10.1214/aoms/1177697604. ISSN 0003-4851. <a href="/wiki/Lawrence_Alan_Shepp" target="_blank">/wiki/Lawrence_Alan_Shepp</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Taylor, Howard M. (1968). "Optimal Stopping in a Markov Process". The Annals of Mathematical Statistics. 39 (4): 1333–1344. doi:10.1214/aoms/1177698259. ISSN 0003-4851. JSTOR 2239702. <a href="https://doi.org/10.1214%2Faoms%2F1177698259" target="_blank">https://doi.org/10.1214%2Faoms%2F1177698259</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Walker, Leroy H. (1969). "Regarding stopping rules for Brownian motion and random walks". Bulletin of the American Mathematical Society. 75 (1): 46–50. doi:10.1090/S0002-9904-1969-12140-3. ISSN 0002-9904. <a href="https://www.ams.org/bull/1969-75-01/S0002-9904-1969-12140-3/" target="_blank">https://www.ams.org/bull/1969-75-01/S0002-9904-1969-12140-3/</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Elton, John H. (2023-06-06). "Exact Solution to the Chow-Robbins Game for almost all n, using the Catalan Triangle". arXiv:2205.13499 [math].{{cite arXiv}}: CS1 maint: date and year (link) <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Häggström, Olle; Wästlund, Johan (2013). "Rigorous Computer Analysis of the Chow–Robbins Game". The American Mathematical Monthly. 120 (10): 893. doi:10.4169/amer.math.monthly.120.10.893. <a href="/wiki/Olle_H%C3%A4ggstr%C3%B6m" target="_blank">/wiki/Olle_H%C3%A4ggstr%C3%B6m</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Christensen, Sören; Fischer, Simon (June 2022). "On the Sn/n problem". Journal of Applied Probability. 59 (2): 571–583. doi:10.1017/jpr.2021.73. ISSN 0021-9002. <a href="https://www.cambridge.org/core/journals/journal-of-applied-probability/article/abs/on-the-snn-problem/8CE3A5834AC35E7ADD137749F61E27A2" target="_blank">https://www.cambridge.org/core/journals/journal-of-applied-probability/article/abs/on-the-snn-problem/8CE3A5834AC35E7ADD137749F61E27A2</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Elton, John H. (2023-06-06). "Exact Solution to the Chow-Robbins Game for almost all n, using the Catalan Triangle". arXiv:2205.13499 [math].{{cite arXiv}}: CS1 maint: date and year (link) <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
</ol>

Robbins' problem open-in-new

Robbins' problem