View source for Robbins' problem

In [[Probability theory|probability theory]], '''Robbins' problem of [[Optimal stopping|optimal stopping]]<ref name=CRS1964>{{cite journal|last1=Chow|first1=Y.S.|last2=Moriguti|first2=S.|
last3=Robbins|first3=Herbert Ellis | author-link3=Herbert Robbins | 
last4=Samuels|first4=Stephen M.|author-link4=Stephen Mitchell Samuels |
title=Optimal Selection Based on Relative Rank|journal=[[Israel Journal of Mathematics]]|year=1964|volume=2|issue=2|pages=81–90|doi=10.1007/bf02759948|doi-access=free}}</ref>''', named after [[Biography:Herbert Robbins|Herbert Robbins]], is sometimes referred to as the fourth [[Secretary problem|secretary problem]] or the problem of minimizing the [[Expected value|expected]] rank with full information.<ref name=Bruss20005>{{cite journal| title=What is known about Robbins' Problem?| last1=Bruss |first1=F. Thomas| 
author-link1=F. Thomas Bruss | journal=Journal of Applied Probability|
volume=42|year=2005 |pages=108-120 |
doi=10.1239/jap/1110381374 |
url=https://www.jstor.org/stable/30040773|doi-access=free}}</ref> <blockquote>Let ''X''<sub>1</sub>, ... , ''X''<sub>''n''</sub> be independent, identically distributed [[Random variable|random variable]]s, [[Continuous uniform distribution|uniform]] on [0,&nbsp;1]. We observe the ''X''<sub>''k''</sub>'s sequentially and must stop on exactly one of them. No recall of preceding observations is permitted. What stopping rule minimizes the expected rank of the selected observation, and what is its corresponding value?</blockquote>The general solution to this full-information expected rank problem is unknown. The major difficulty is that the problem is fully history-dependent, that is, the optimal rule depends at every stage on all preceding values, and not only on simpler sufficient statistics of these. Only bounds are known for the limiting value ''v'' as ''n'' goes to infinity, namely 1.908&nbsp;<&nbsp;''v''&nbsp;<&nbsp;2.329. It is known that there is some room to improve the lower bound by further computations for a truncated version of the problem. It is still not known how to improve on the upper bound which stems from the subclass of memoryless threshold rules.<ref name=BrussFerguson1973>{{cite journal|
last1=Bruss|first1=F.Thomas|author-link1=F. Thomas Bruss |
last2=Ferguson|first2=S. Thomas|author-link2=Thomas S. Ferguson |
title=Minimizing the expected rank with full information|journal=Journal of Applied Probability|year=1993|volume=30|issue=3|pages=616–626|doi=10.1007/bf02759948|doi-access=free|issn=00219002|url=http://www.jstor.org/stable/3214770}}</ref><ref name=BrussFerguson1996>{{cite  conference|last1=Bruss|first1=F.Thomas|last2=Ferguson|first2=S. Thomas|title=Half-Prophets and Robbins' Problem of Minimizing the expected rank|book-title=Lecture Notes in Statistics (LNS)|volume=114|conference=Athens Conference on Applied Probability and Time Series Analysis| year=1996| publisher=Springer New York| location=New York, NY |pages=1–17|doi=10.1007/978-1-4612-0749-8_1|doi-access=free|isbn=978-0-387-94788-4}}</ref><ref name=AssafSamCahn1996>{{cite journal| 
last1=Assaf|first1=David|last2=Samuel-Cahn|first2=Ester|author-link2=Ester Samuel-Cahn |
title=The secretary problem: Minimizing the expected rank with i.i.d. random variables | 
journal=Advances in Applied Probability|volume=28
|number=3 | year=1996|pages=828--852|
doi=10.2307/1428183|doi-access=free|issn=0001-8678}}</ref>

It was proposed the continuous time version of the problem where the observations follow a Poisson arrival process of homogeneous rate 1. Under some assumptions, the corresponding value function <math>w(t)</math> is bounded and Lipschitz continuous, and the differential equation for this value function is derived.<ref name=BruSwan2009>{{cite journal| title=What is known about Robbins' Problem?| 
last1=Bruss |first1=F. Thomas| author-link1=F. Thomas Bruss | 
last2=Swan | first2=Yvik C. |
journal=Journal of Applied Probability|
volume=46|year=2009 |pages=1-18 |
doi=10.1239/jap/1238592113 |
url=https://www.jstor.org/stable/30040773|doi-access=free }}</ref> The limiting value of <math>w(t)</math> presents the solution of Robbins’ problem. It is shown that for large <math>t</math>, <math>1\leq w(t)\leq 2.33183</math>. This estimation coincides with the bounds mentioned above.

A simple suboptimal rule, which performs
almost as well as the optimal rule, was proposed by Krieger & Samuel-Cahn.<ref name=KriegerSamuelCahn2009>{{cite journal| 
title=The secretary problem of minimizing the expected rank: a simple suboptimal approach with generalization| 
last1=Krieger |first1=Abba M.| 
last2=Samuel-Cahn | first2=Ester |author-link2=Ester Samuel-Cahn |
journal=Advances in Applied Probability|
volume=41|year=2009 |pages=1041-1058 |
doi=10.1239/aap/1261669585 |
url=https://www.jstor.org/stable/27793918|doi-access=free }}</ref> The rule stops with the smallest <math>i</math> such that <math>R_i < ic/(n + i)</math> for a given constant c, where <math>R_i</math> is the relative rank of the ith observation and n is the total number of items. This rule has added flexibility. A curtailed version thereof can be used to select an item with a given probability <math>P</math>, <math>P < 1</math>. The rule can be used to select two or more items. The problem of selecting a fixed percentage <math>\alpha</math>, <math> 0 < \alpha < 1</math>, of n, is also treated.

== Chow-Robbins game ==
Another optimal stopping problem bearing Robbins' name is the Chow-Robbins game:<ref name=CowRob>{{Cite journal |last=Chow |first=Y. S. |last2=Robbins |first2=Herbert |
date=September 1965 |title=On optimal stopping rules for $S_{n}/n$ |url=https://projecteuclid.org/journals/illinois-journal-of-mathematics/volume-9/issue-3/On-optimal-stopping-rules-for-S_nn/10.1215/ijm/1256068146.full |journal=Illinois Journal of Mathematics |volume=9 |issue=3 |pages=444–454 |doi=10.1215/ijm/1256068146 |issn=0019-2082|doi-access=free }}</ref><ref name=Elton2022 /><blockquote>Given an infinite sequence of [[Independent and identically distributed random variables|IID]] random variables <math>X_1, X_2, ...</math> with distribution <math>F</math>, how to decide when to stop, in order to maximize the sample average <math>\frac 1n(X_1 + \cdots X_n)</math> where <math>n</math> 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 <math>F</math> with finite second moment, there exists an optimal strategy, defined by a sequence of numbers <math>\beta_1, \beta_2, ...</math>. The strategy is to keep sampling until <math>\frac 1n(X_1 + \cdots X_n) \geq \beta_n</math>.<ref name=Dvoretzky>Dvoretzky, Aryeh. "Existence and properties of certain optimal stopping rules." ''Proc. Fifth Berkeley Symp. Math. Statist. Prob''. Vol. 1. 1967.</ref><ref>{{cite journal |last=Teicher |first=H. |last2=Wolfowitz |first2=J. |date=1966-12-01 |title=Existence of optimal stopping rules for linear and quadratic rewards |url=https://doi.org/10.1007/BF00535366 |journal=Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete |language=en |volume=5 |issue=4 |pages=361–368 |doi=10.1007/BF00535366 |issn=1432-2064}}</ref>

=== Optimal strategy for very large n ===
If <math>F</math> 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 <math>F</math> with mean zero and variance one.

With this, <math>\lim_{n} \beta_n/\sqrt n \approx \alpha = 0.8399236757</math>, where <math>\alpha</math> is the solution to the equation{{NoteTag|<source lang="python">
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")
</source>}}<math display="block">\alpha=\left(1-\alpha^2\right) \int_0^{\infty} e^{\lambda \alpha-\lambda^2 / 2} d \lambda</math>which can be proved by solving the same problem with continuous time, with a [[Wiener process]]. At the limit of <math>n\to \infty</math>, the discrete time problem becomes the same as the continuous time problem.

This was proved independently<ref name=GordonYao>{{cite journal |last=Simons |first=Gordon |last2=Yao |first2=Yi-Ching |date=1989-08-01 |title=Optimally stopping the sample mean of a Wiener process with an unknown drift |url=https://www.sciencedirect.com/science/article/pii/0304414989900847 |journal=Stochastic Processes and their Applications |language=en |volume=32 |issue=2 |pages=347–354 |doi=10.1016/0304-4149(89)90084-7 |issn=0304-4149}}</ref> by.<ref>{{Cite journal |last=Shepp |first=L. A. |date=June 1969 |title=Explicit Solutions to Some Problems of Optimal Stopping |url=https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-40/issue-3/Explicit-Solutions-to-Some-Problems-of-Optimal-Stopping/10.1214/aoms/1177697604.full |journal=The Annals of Mathematical Statistics |volume=40 |issue=3 |pages=993–1010 |doi=10.1214/aoms/1177697604 |issn=0003-4851|doi-access=free }}</ref><ref>{{Cite journal |last=Taylor |first=Howard M. |date=1968 |title=Optimal Stopping in a Markov Process |url=https://www.jstor.org/stable/2239702 |journal=The Annals of Mathematical Statistics |volume=39 |issue=4 |pages=1333–1344 |issn=0003-4851}}</ref><ref>{{Cite journal |last=Walker |first=Leroy H. |date=1969 |title=Regarding stopping rules for Brownian motion and random walks |url=https://www.ams.org/bull/1969-75-01/S0002-9904-1969-12140-3/ |journal=Bulletin of the American Mathematical Society |language=en |volume=75 |issue=1 |pages=46–50 |doi=10.1090/S0002-9904-1969-12140-3 |issn=0002-9904|doi-access=free }}</ref>

When the game is a fair coin toss game, with heads being +1 and tails being -1, then there is a sharper result<ref name=Elton2022>{{cite arXiv
	| last =Elton 
	| first = John H.
	| date = 2023-06-06
	| title = Exact Solution to the Chow-Robbins Game for almost all n, using the Catalan Triangle
	| eprint=2205.13499
	| class =math
    | year=2023
}}</ref><math display="block">\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)</math>where <math>\zeta</math> is the [[Riemann zeta function]].

=== Optimal strategy for small n ===
When n is small, the asymptotic bound does not apply, and finding the value of <math>\beta_n</math> is much more difficult. Even the simplest case, where <math>X_1, X_2, ...</math> are fair coin tosses, is not fully solved.

For the fair coin toss, a strategy is a binary decision: after <math>n</math> tosses, with k heads and (n-k) tails, should one continue or should one stop? Since 1D random walk is recurrent, starting at any <math>k, (n-k)</math>, the probability of eventually having more heads than tails is 1. So, if <math>k \leq n-k</math>, one should always continue. However, if <math>k > n-k</math>, it is tricky to decide whether to stop or continue.<ref>{{Cite journal |last1=Häggström |first1=Olle |last2=Wästlund |first2=Johan |author-link2=Johan Wästlund|date=2013 |title=Rigorous Computer Analysis of the Chow–Robbins Game |url=https://www.tandfonline.com/doi/full/10.4169/amer.math.monthly.120.10.893 |journal=The American Mathematical Monthly |volume=120 |issue=10 |pages=893 |doi=10.4169/amer.math.monthly.120.10.893}}</ref>

<ref>{{Cite journal |last=Christensen |first=Sören |last2=Fischer |first2=Simon |date=June 2022 |title=On the Sn/n problem |url=https://www.cambridge.org/core/journals/journal-of-applied-probability/article/abs/on-the-snn-problem/8CE3A5834AC35E7ADD137749F61E27A2 |journal=Journal of Applied Probability |language=en |volume=59 |issue=2 |pages=571–583 |doi=10.1017/jpr.2021.73 |issn=0021-9002}}</ref> found an exact solution for all <math>n \leq 489241</math>.

Elton<ref name=Elton2022 /> found exact solutions for all <math>n \leq 9.06 \times 10^7</math>, and it found an almost always optimal decision rule, of stopping as soon as <math>k - (n-k) \geq \Delta k_n</math> where<math display="block">\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</math>

==Importance==
One of the motivations to study Robbins' problem is that with its solution all classical (four) [[Secretary problem|secretary problem]]s 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 [[Optimal stopping|optimal stopping]] and [[Sequential analysis|sequential analysis]].

==History ==

[[Biography:Herbert Robbins|Herbert Robbins]] presented the above described problem at the ''International Conference on Search and Selection in Real Time''{{NoteTag|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. }} in Amherst, 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''. Robbins himself died in 2001.

==References==

<references />

== Footnotes ==
{{reflist|group=note}}

[[Category:Stochastic optimization]]

{{Sourceattribution|Robbins' problem}}