2010/12/01 by Katsunori Ano, Hideo Kakinuma, Naoto Miyoshi · 16 citations
Computer Science · Decision Sciences · Mathematics · #Artificial intelligence #Auction Theory and Applications #Central limit theorem #Combinatorics #Computer science #Cryptography and Data Security #Discrete mathematics #Limit (mathematics) #Logistic regression #Mathematical economics #Mathematical optimization #Mathematics #Odds #Optimal stopping #Optimization and Search Problems #Secretary problem #Selection (genetic algorithm) #Statistics
paper · pdf · doi:10.1239/jap/1294170522
published in Journal of Applied Probability 47(4), 1093-1104 (Cambridge University Press)
openalex publication_date 2010/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
We study the multi-selection version of the so-called odds theorem by Bruss (2000). We observe a finite number of independent 0/1 (failure/success) random variables sequentially and want to select the last success. We derive the optimal selection rule when m (≥ 1) selection chances are given and find that the optimal rule has the form of a combination of multiple odds-sums. We provide a formula for computing the maximum probability of selecting the last success when we have m selection chances and also provide closed-form formulae for m = 2 and 3. For m = 2, we further give the bounds for the maximum probability of selecting the last success and derive its limit as the number of observations goes to ∞. An interesting implication of our result is that the limit of the maximum probability of selecting the last success for m = 2 is consistent with the corresponding limit for the classical secretary problem with two selection chances.