HOME

TheInfoList



OR:

In
decision theory Decision theory or the theory of rational choice is a branch of probability theory, probability, economics, and analytic philosophy that uses expected utility and probabilities, probability to model how individuals would behave Rationality, ratio ...
, the odds algorithm (or Bruss algorithm) is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of
optimal stopping In mathematics, the theory of optimal stopping or early stopping : (For French translation, secover storyin the July issue of ''Pour la Science'' (2009).) is concerned with the problem of choosing a time to take a particular action, in order to ...
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.


Examples

Two different situations exemplify the interest in maximizing the probability to stop on a last specific event. # Suppose a car is advertised for sale to the highest bidder (best "offer"). Let 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 The concept of a random sequence is essential in probability theory and statistics. The concept generally relies on the notion of a sequence of random variables and many statistical discussions begin with the words "let ''X''1,...,''Xn'' be independ ...
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''. # 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 treat every responsive 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. (See Compassionate use.)


Definitions

Consider a sequence of n
independent events Independence is a fundamental notion in probability theory, as in statistics and the theory of stochastic processes. Two events are independent, statistically independent, or stochastically independent if, informally speaking, the occurrence of ...
. Associate with this sequence another sequence of independent events I_1,\, I_2,\, \dots ,\, I_n with values 1 or 0. Here \,I_k =1, called a success, stands for the event that the kth observation is interesting (as defined by the decision maker), and \, I_k=0 for non-interesting. These random variables I_1,\, I_2,\, \dots ,\, I_n are observed sequentially and the goal is to correctly select the last success when it is observed. 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 In probability theory, odds provide a measure of the probability of a particular outcome. Odds are commonly used in gambling and statistics. For example for an event that is 40% probable, one could say that the odds are or When gambling, o ...
of the kth event turning out to be interesting, explaining the name of the odds algorithm.


Algorithmic procedure

The odds algorithm sums up the odds in reverse order : r_n + r_ + r_\, +\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_ + r_ + \cdots + r_s. \, If the sum of the odds does not reach 1, it sets ''s'' = 1. At the same time it computes : Q_=q_n q_\cdots q_s.\, The output is # \,s, the stopping threshold # \,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 # The odds strategy is ''optimal'', that is, it maximizes the probability of stopping on the last 1. # The win probability of the odds strategy equals w= Q_s R_s # If R_s \ge 1, the win probability w is always at least , and this lower bound is ''best possible''.


Features

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.


Sources

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 trial Clinical trials are prospective biomedical or behavioral research studies on human subject research, human participants designed to answer specific questions about biomedical or behavioral interventions, including new treatments (such as novel v ...
s over sales problems, secretary problems,
portfolio Portfolio may refer to: Objects * Portfolio (briefcase), a type of briefcase Collections * Portfolio (finance), a collection of assets held by an institution or a private individual * Artist's portfolio, a sample of an artist's work or a ...
selection, (one way) search strategies, trajectory problems and the parking problem to problems in online 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 In probability theory, statistics and related fields, a Poisson point process (also known as: Poisson random measure, Poisson random point field and Poisson point field) is a type of mathematical object that consists of Point (geometry), points ...
(). 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 .


Variations

discussed a problem of selecting the last k successes. proved a multiplicative odds theorem which deals with a problem of stopping at any of the last \ell successes. A tight lower bound of win probability is obtained by . discussed a problem of selecting k out of the last \ell successes and obtained a tight lower bound of win probability. When \ell= k = 1, the problem is equivalent to Bruss' odds problem. If \ell= k \geq 1, the problem is equivalent to that in . A problem discussed by is obtained by setting \ell \geq k=1.


Multiple choice problem

A player is allowed r choices, and he wins if any choice is the last success. For classical secretary problem, discussed the cases r=2,3,4. The odds problem with r=2, 3 is discussed by . For further cases of odds problem, see . An optimal strategy for this problem belongs to the class of strategies defined by a set of threshold numbers (a_1, a_2, ..., a_r), where a_1 > a_2 > \cdots > a_r. Specifically, imagine that you have r letters of acceptance labelled from 1 to r. You would have r application officers, each holding one letter. You keep interviewing the candidates and rank them on a chart that every application officer can see. Now officer i would send their letter of acceptance to the first candidate that is better than all candidates 1 to a_i. (Unsent letters of acceptance are by default given to the last applicants, the same as in the standard secretary problem.) When r=2 , showed that the tight lower bound of win probability is equal to e^+ e^. For general positive integer r, proved that the tight lower bound of win probability is the win probability of the secretary problem variant where one must pick the top-k candidates using just k attempts. When r=3,4,5 , tight lower bounds of win probabilities are equal to e^+ e^+e^ , e^+e^+e^+e^ and e^+e^+e^+e^+e^, respectively. For further numerical cases for r=6,...,10, and an algorithm for general cases, see .


See also

*
Odds In probability theory, odds provide a measure of the probability of a particular outcome. Odds are commonly used in gambling and statistics. For example for an event that is 40% probable, one could say that the odds are or When gambling, o ...
*
Clinical trial Clinical trials are prospective biomedical or behavioral research studies on human subject research, human participants designed to answer specific questions about biomedical or behavioral interventions, including new treatments (such as novel v ...
*
Expanded access Expanded access or compassionate use is the use of an unapproved drug or medical device under special forms of investigational new drug, investigational new drug applications (IND) or Investigational device exemption, IDE application for devices, o ...
*
Secretary problem The secretary problem demonstrates a scenario involving optimal stopping theory For French translation, secover storyin the July issue of ''Pour la Science'' (2009). that is studied extensively in the fields of applied probability, statistics, a ...


References

* * **
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 The European Mathematical Society (EMS) is a European organization dedicated to the development of mathematics in Europe. Its members are different mathematical societies in Europe, academic institutions and individual mathematicians. The curren ...
'', Issue 62, 14–20, (2005). * T. S. Ferguson: (2008, unpublished) * * * * * * Shoo-Ren Hsiao and Jiing-Ru. Yang:
Selecting the Last Success in Markov-Dependent Trials
, '' Journal of Applied Probability'', Vol. 93, 271–281, (2002). * * Mitsushi Tamaki:
Optimal Stopping on Trajectories and the Ballot Problem
, '' Journal of Applied Probability'' Vol. 38, 946–959 (2001). * 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).


External links

* Bruss Algorithmus http://www.p-roesler.de/odds.html {{DEFAULTSORT:Odds Algorithm Optimization algorithms and methods Statistical algorithms Optimal decisions