MINIMAX-OPTIMAL STOP RULES AND DISTRIBUTIONS IN SECRETARY PROBLEMS

• 成果类型: Article
• 署名作者: HILL, TP; KRENGEL, U
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/aop/1176990548
• 发表日期: 1991
• 页码: 342-353
• 关键词: unknown number; unified approach; options

摘要

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.