Skip to main content
Article
Minimax-Optimal Stop Rules and Distributions in Secretary Problems
The Annals of Probability
  • Theodore P. Hill, Georgia Institute of Technology - Main Campus
  • Ulrich Krengel, University of Gottingen
Publication Date
1-1-1991
Abstract
For the secretary (or best-choice) problem with an unknown number N of objects, minimax-optimal stop rules and (worst-case) distributions are derived, under the assumption that $N$ is a random variable with unknown distribution, but known upper bound n. Asymptotically, the probability of selecting the best object in this situation is of order of (log n)-1. For example, even if the only information available is that there are somewhere between 1 and 100 objects, there is still a strategy which will select the best item about one time in five.
Disciplines
Citation Information
Theodore P. Hill and Ulrich Krengel. "Minimax-Optimal Stop Rules and Distributions in Secretary Problems" The Annals of Probability Vol. 19 Iss. 1 (1991) p. 342 - 353
Available at: http://works.bepress.com/tphill/25/