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
      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
      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

      Identifiers