Lower Bounds for Bruss' Odds Problem with Multiple Stoppings

• 成果类型: Article
• 署名作者: Matsui, Tomomi; Ano, Katsunori
• 署名单位: Institute of Science Tokyo; Tokyo Institute of Technology; Shibaura Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0748
• 发表日期: 2016
• 页码: 700-714
• 关键词: sequence; THEOREM; trials; stop; SUM

摘要

This paper addresses Bruss' odds problem with multiple stopping chances. A decision maker sequentially observes a sequence of independent 0/1 (failure/success) random variables to correctly predict the last success with multiple stopping chances. First, we give a nontrivial lower bound of the probability of win (obtaining the last success) for the problem with m-stoppings. Next, we show that the asymptotic value for each classical secretary problem with multiple stoppings attains our lower bound. Finally, we prove a conjecture on the classical secretary problem, which gives a connection between the probability of win and the threshold values of the optimal stopping strategy.