What is Known About Robbins' Problem? (Q5312844)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2199096
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | What is Known About Robbins' Problem? |
scientific article; zbMATH DE number 2199096 |
Statements
What is Known About Robbins' Problem? (English)
0 references
25 August 2005
0 references
Robbins' problem
0 references
best-choice problem
0 references
full information
0 references
upper bound
0 references
lower bound
0 references
memoryless
0 references
threshold rule
0 references
0 references
0 references
0.8716655373573303
0 references
0.8658603429794312
0 references
0.8540434837341309
0 references
0.8461093306541443
0 references
The paper presents in an expository style what is known about Robbins' problem: for a sequence of i.i.d. random variables which are uniform on \([0,1]\) find a stopping time that minimizes the expected rank of the chosen variable, and determine the corresponding expected rank \(V(n)\) and its limit \(V\) as \(n\to \infty\). The form of the optimal stopping time is given, which makes it clear that at any possible stopping instant the optimal rule depends on the entire prehistory. The optimal stopping time in the class of memoryless threshold rules can be computed by solving a system of \(n-1\) equations. It is unknown whether \(V\) is equal to the limit of the values for this restricted class. The following known bounds are given: \[ V(n) \leq 1+[4(n-1)/3(n+1)] \leq 7/3\quad\text{and}\quad 1.908 \leq V \leq 2.3267. \]
0 references