Odds algorithm

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. Their solution follows from the odds-strategy, and the importance of the odds-strategy lies in its optimality, as explained below.

The odds-algorithm applies to a class of problems called last-success-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"). This identification must be done at the time of observation. No revisiting of preceding observations is permitted. Usually, a specific event is defined by the decision maker as an event that is of true interest in the view of "stopping" to take a well-defined action. Such problems are encountered in several situations.

Contents

Examples

Two different situations exemplify the interest in maximizing the probability to stop on a last specific event.

  1. Suppose a car is advertised for sale to the highest bidder (best "offer"). n potential buyers respond and ask to see the car. Each insists upon an immediate decision from the seller to accept the bid, or not. Define a bid as interesting, and coded 1 if it is better than all preceding bids, and coded 0 otherwise. The bids will form a random sequence of 0s and 1s. Only 1s interest the seller, who may fear that each successive 1 might be the last. It follows from the definition that the very last 1 is the highest bid. Maximizing the probability of selling on the last 1 therefore means maximizing the probability of selling best.
  2. A physician, using a special treatment, may use the code 1 for a successful treatment, 0 otherwise. The physician treats a sequence of n patients the same way, and wants to minimize any suffering, and to achieve success with every patient in the sequence. Stopping on the last 1 in such a random sequence of 0s and 1s would achieve this objective. Since the physician is no prophet, the objective is to maximize the probability of stopping on the last 1.

Definitions

Consider a sequence of n independent events. Associate with this sequence another sequence  I_1,\, I_2,\, \dots ,\, I_n with values 1 or 0. Here  \,I_k =1 stands for the event that the kth observation is interesting (as defined by the decision maker), and \, I_k=0 for non-interesting. Let  \,p_k = P( \,I_k\,=1) be the probability that the kth event is interesting. Further let  \,q_k = \,1- p_k and  \,r_k = p_k/q_k. Note that  \,r_k represents the odds of the kth event turning out to be interesting, explaining the name of the odds-algorithm.

Algorithmic procedure of the odds-algorithm

The odds-algorithm sums up the odds in reverse order

 r_n + r_{n-1} + r_{n-2}\, +\cdots, \,

until this sum reaches or exceeds the value 1 for the first time. If this happens at index s, it saves s and the corresponding sum

 R_s = \,r_n + r_{n-1} + r_{n-2}  + \cdots + r_s. \,

If the sum of the odds does not reach 1, it sets s = 1. At the same time it computes

 Q_{s}=q_n q_{n-1}\cdots q_s.\,

The output is

  1. \,s, the stopping threshold
  2. \,w = Q_s R_s, the win probability.

Odds-strategy

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).

The importance of the odds-strategy, and hence of the odds-algorithm, lies in the following odds-theorem.

Odds-theorem

The odds-theorem states that

  1. The odds-strategy is optimal, that is, it maximizes the probability of stopping on the last 1.
  2. The win probability of the odds-strategy equals \,w= Q_s R_s
  3. If \, R_s \ge \,1 , the win probability \, w is always at least  \,1/e = 0.368\dots, and this lower bound is best possible.

Features of the odds-algorithm

The odds-algorithm computes the optimal strategy and the optimal win probability at the same time. Also, the number of operations of the odds-algorithm is (sub)linear in n. Hence no quicker algorithm can possibly exist for all sequences, so that the odds-algorithm is, at the same time, optimal as an algorithm.

Source

F. T. Bruss (2000) devised the odds algorithm, and coined its name. It is also known as Bruss-algorithm (strategy). Free implementations can be found on the web.

Applications

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.

There exists, in the same spirit, an Odds-Theorem for continuous-time arrival processes with independent increments such as the Poisson process (Bruss (2000)). In some cases, the odds are not necessarily known in advance (as in Example 2 above) so that the application of the odds-algorithm is not directly possible. In this case each step can use sequential estimates of the odds. This is meaningful, if the number of unknown parameters is not large compared with the number n of observations. The question of optimality is then more complicated, however, and requires additional studies. Generalizations of the odds-algorithm allow for different rewards for failing to stop and wrong stops as well as replacing independence assumptions by weaker ones (Ferguson (2008)).

See also

References

  • F. Thomas Bruss: "Sum the Odds to One and Stop", Annals of Probability Vol. 28, 1384–1391 (2000).
  • —: "A note on Bounds for the Odds-Theorem of Optimal Stopping", Annals of Probability Vol. 31, 1859–1862, (2003).
  • —: "The art of a right decision", Newsletter of the European Mathematical Society, Issue 62, 14–20, (2005).
  • Mitsushi Tamaki: "Optimal Stopping on Trajectories and the Ballot Problem", Journal of Applied Probability Vol. 38, 946–959 (2001).
  • Shoo-Ren Hsiao and Jiing-Ru. Yang: "Selecting the Last Success in Markov-Dependent Trials", Journal of Applied Probability, Vol. 93, 271–281, (2002).
  • E. Thomas, E. Levrat, B. Iung: "L'algorithme de Bruss comme contribution à une maintenance préventive", Sciences et Technologies de l'automation, Vol. 4, 13-18 (2007).
  • T.S. Ferguson: (2008, unpublished)

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Odds — For the alternative rock band, see Odds (band). Odds against redirects here. For the 1966 documentary film, see The Odds Against. The odds in favor of an event or a proposition are expressed as the ratio of a pair of integers, which is the ratio… …   Wikipedia

  • Odds-Strategie — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses… …   Deutsch Wikipedia

  • Selection algorithm — In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list (such a number is called the kth order statistic). This includes the cases of finding the minimum, maximum, and median elements. There are… …   Wikipedia

  • Online algorithm — In computer science, an online algorithm is one that can process its input piece by piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an… …   Wikipedia

  • Medical algorithm — A medical algorithm for assessment and treatment of overweight and obesity. A medical algorithm is any computation, formula, statistical survey, nomogram, or look up table, useful in healthcare. Medical algorithms …   Wikipedia

  • Online algorithm — En informatique, un algorithme online (algorithme en ligne) est un algorithme qui reçoit son entrée (son input) prédécoupée en petits morceaux, et qui commence à calculer dès le premier petit morceau reçu, puis continue à traiter, en série, les… …   Wikipédia en Français

  • Genetic algorithm — A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Optimal stopping — In mathematics, the theory of optimal stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of… …   Wikipedia

  • Secretary problem — The secretary problem is an optimal stopping problem that has been studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan s dowry problem, the fussy suitor… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”