1996 | OriginalPaper | Buchkapitel
Half-Prophets and Robbins’ Problem of Minimizing the Expected Rank
verfasst von : F. Thomas Bruss, Thomas S. Ferguson
Erschienen in: Athens Conference on Applied Probability and Time Series Analysis
Verlag: Springer New York
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let X1, X2,…X n be i.i.d. random variables with a known continuous distribution function. Robbins’ problem is to find a sequential stopping rule without recall which minimizes the expected rank of the selected observation. An upper bound (obtained by memoryless threshold rules) and a procedure to obtain lower bounds of the value are known, but the difficulty is that the optimal strategy depends for all n > 2 in an intractable way on the whole history of preceding observations. The goal of this article is to understand better the structure of both optimal memoryless threshold rules and the (overall) optimal rule. We prove that the optimal rule is a “stepwise” monotone increasing threshold-function rule and then study its property of, what we call, full history-dependence. For each n, we describe a tractable statistic of preceding observations which is sufficient for optimal decisions of decision makers with half-prophetical abilities who can do generally better than we. It is shown that their advice can always be used to improve strictly on memoryless rules, and we determine such an improved rule for all n sufficiently large. We do not know, however, whether one can construct, as n → ∞ asymptotically relevant improvements.