Odds-Algorithm #

Odds Algorithm #

Created: December 7, 2019 10:57 PM Tags: Data, Statistics URL: https://en.m.wikipedia.org/wiki/Odds_algorithm The odds-algorithm is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of optimal stopping problems. Formally, the objective in these problems is to maximize the probability of identifying in a sequence of sequentially observed independent events the last event satisfying a specific criterion (a “specific event”). At the same time it computes The output is The odds-strategy is the rule to observe the events one after the other and to stop on the first interesting event from index s onwards (if any), where s is the stopping threshold of output a. Applications reach from medical questions in clinical trials over sales problems, secretary problems, portfolio selection, (one-way) search strategies, trajectory problems and the parking problem to problems in on-line maintenance and others. Matsui & Ano 2017 discussed a problem of selecting out of the last successes and obtained a tight lower bound of win probability. A problem discussed by Tamaki 2010 is obtained by setting multiple choice problem: A player is allowed choices, and he wins if any choice is the last success. When , Ano, Kakinuma & Miyoshi 2010 showed that the tight lower bound of win probability is equal to For general positive integer , Matsui & Ano 2016 discussed the tight lower bound of win probability.