Sum the odds to one and stop

2000/06/01 by F. Thomas Bruss · 144 citations
Computer Science · Decision Sciences · Mathematics · #Optimization and Search Problems #Auction Theory and Applications #Advanced Bandit Algorithms Research #Mathematics #Optimal stopping #Mathematical proof #Class (philosophy) #Stopping time #Value (mathematics) #Stopping rule #Applied mathematics #Calculus (dental) #Discrete mathematics #Mathematical optimization #Statistics #Computer science

paper · pdf · doi:10.1214/aop/1019160340

published in The Annals of Probability 28(3) (Institute of Mathematical Statistics)

openalex publication_date 2000/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02

Abstract

The objective of this paper is to present two theorems which are directly applicable to optimal stopping problems involving independent indicator functions. The proofs are elementary. One implication of the results is a convenient solution algorithm to obtain the optimal stopping rule and the value.We will apply it to several examples of sequences of independent indicators, including sequences of random length. Another interesting implication of the results is that the well-known asymptotic value 1 / e for the classical best-choice problem is in fact a typical lower boundin a much more general class of problems.

Citations

• A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options

Cited by

• A note on bounds for the odds theorem of optimal stopping
• A New Proof and Extension of the Odds-Theorem
• Compare the ratio of symmetric polynomials of odds to one and stop
• Sum the Multiplicative Odds to One and Stop
• Odds Theorem with Multiple Selection Chances
• A Note on a Lower Bound for the Multiplicative Odds Theorem of Optimal Stopping
• Odds algorithm [wikipedia]
• Secretary problem [wikipedia]