Optimal selection based on relative ranks of a sequence by ties (Q3317831)

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 3848333
Language Label Description Also known as
default for all languages
No label defined
    English
    Optimal selection based on relative ranks of a sequence by ties
    scientific article; zbMATH DE number 3848333

      Statements

      Optimal selection based on relative ranks of a sequence by ties (English)
      0 references
      0 references
      1984
      0 references
      best choice problem
      0 references
      optimal stopping problem
      0 references
      relative ranks
      0 references
      secretary problem
      0 references
      Dirichlet process
      0 references
      Let \(X_ 1,X_ 2,...,X_ n\) denote a sequence of independent, identically distributed random variables from distribution function F. The optimal stopping problem of interest is to observe the X's one at a time and to stop at the maximum value, with no recall permitted. In this paper it is assumed that F is not continuous, so the maximum is not necessarily unique and the optimal strategy allows for ties. If F is continuous but unknown, and the loss function is 0-1 (0 if maximum selected, 1 if not), the optimal rule depends only on the relative ranks of the observations. This is the classical ''secretary problem''. This problem has been generalized in various ways; the realistic generalization considered here is to allow ties; in particular, assume F is not continuous or, alternately, the original observations have been grouped into ordered categories. The loss function is 0-1 (best-choice problem). Several approaches to ties are treated. One strategy is to break ties randomly and employ the optimal rule for the continuous problem. Another intuitive strategy is to discard all previous ties. If at X, there are m distinct values among \(X_ 1,...,X_ r\), reduce n to n-(r-m) and reduce r to m and employ the optimal rule for the continuous problem. This will be referred to as the reduced rule. A third approach assumes that an upper bound k on the number of atoms of the discrete distribution function F is known. Minimax rules are obtained and the behavior of the rules as k tends to \(\infty\) is investigated. If the sequence is random from F, a random distribution function from a Dirichlet process prior with non-atomic parameters, optimal rules are developed. The limiting behavior of these rules is studied and compared with other rules. The selection of the parameter of the Dirichlet process regulates the ties.
      0 references

      Identifiers