Odds algorithm: Difference between revisions

Revision as of 23:13, 6 January 2010

Latest revision as of 20:35, 3 August 2025

(108 intermediate revisions by 45 users not shown)

Line 1:

{{short description|Method of computing optimal strategies for last-success problems}}

The '''odds-algorithm''' is a mathematical method to compute optimal

strategies for a class of problems which belong to the ___domain of [[optimal stopping]]. Its solution determines the ''odds-strategy'', and the importance of the

odds-strategy lies in its optimality, as explained below.

In [[decision theory]], 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]] 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 is to maximize the probability of identifying in a

sequence of sequentially observed independent events a last specific event. This identification must be done on-line, that is, at the time of observation. No recall on preceding observations is permitted. Usually a specific

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.

event is defined by the decision maker as an event which is of true interest to her/him in the view of "stopping"

in order to take

a well-defined action. Such

problems are encountered in several

real-world 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 <math>n</math> potential peoplebuyers respond and ask to see the car. TheyEach allinsists insistupon thatan theyimmediate woulddecision needfrom the immediateseller decisionto whetheraccept the their offer is acceptedbid, or not. Define ana offerbid as ''interesting'', and coded ''1'' say, if it is better than all preceding offersbids, and coded ''0'' otherwise. The offersbids will form a [[random sequence]] of 0's0s and 1's1s. Only 1's are of1s interest to the seller, and with each 1 he/shewho may fear that thereeach willsuccessive 1 might be nothe further 1'slast. It follows from the definition that the very last 1 is the highest offerbid. 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. TreatingThe physician treats a sequence of <math>n</math> patients with the same treatmentway, he/sheand wants to minimize unnecessaryany sufferingssuffering, and, atto thetreat sameevery time,responsive obtain ''all'' successespatient in the sequence of patients. Stopping on the last 1 in such a random sequence of 0's0s and 1's1s meanswould to realizeachieve this objective. Since the physician hasis no prophetical powerprophet, his/herthe objective translatesis into the goal of finding a strategyto maximizingmaximize the probability of stopping on the last 1. (See [[Compassionate use]].)

== Definitions ==

Consider a sequence of <math>n</math> [[independent events]]. Associate with this sequence another sequence of independent events <math> I_1,\, I_2,\, \dots ,\, I_n </math> with values 1 or 0. Here <math> \,I_k =1</math>, called a success, stands for

the event that the kth observation is interesting (as defined by the decision maker), and <math>\, I_k=0</math> for non-interesting.

These random variables <math> I_1,\, I_2,\, \dots ,\, I_n </math> are observed sequentially and the goal is to correctly select the last success when it is observed.

Let <math> \,p_k = P( \,I_k\,=1)</math> be the probability that the kth event is interesting. Further let

<math> \,q_k = \,1- p_k </math> and <math> \,r_k = p_k/q_k</math>. Note that <math> \,r_k</math> represents the [[odds]] of the kth event turning out to be interesting, explaining the name of the odds algorithm.

<math> \,r_k</math> 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

:<math> r_n + r_{n-1} + r_{n-2}\, +\cdots, \, </math>

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

:<math> R_s = \,r_n + r_{n-1} + r_{n-2} + \cdots + r_s. \, </math>

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

:<math> Q_{s}=q_n q_{n-1}\cdots q_s.\,</math>

Line 44 ⟶ 38:

# <math>\,w = Q_s R_s</math>, 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.

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 <math>\,w= Q_s R_s </math>

# If <math>\, R_s \ge \,1 </math>, the win probability <math>\, w</math> is always at least <{{math> \,|1=1/[[e (mathematical constant)|''e'']] = 0.378\dots</math>367879...}}, 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.

==SourceSources==

The{{harvnb|Bruss|2000}} devised the odds algorithm, is due to F. T. Bruss (2000) whoand coined thisits name. It is also known underas theBruss name Bruss-algorithm (strategy). Free implementations can be found on the web.

==Applications==

{{secretary_problem.svg}}

Applications reach from medical questions in [[clinical trial]]s over sales problems, [[secretary problems]], [[portfolio (finance)|portfolio]] selection, (one- way) search strategies, trajectory problems and the [[parking problem]] to problems in on-lineonline [[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]] ({{harvnb|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 estimatesestimate]]s 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 ({{harv|Ferguson (|2008))}}.

== See alsoVariations ==

{{harvnb|Bruss|Paindaveine|2000}} discussed a problem of selecting the last <math> k </math> successes.

{{harvnb|Tamaki|2010}} proved a multiplicative odds theorem which deals with a problem of stopping at any of the last <math> \ell </math> successes.

* [[Secretary problem]]

A tight lower bound of win probability is obtained by {{harvnb|Matsui|Ano|2014}}.

{{harvnb|Matsui|Ano|2017}} discussed a problem of selecting <math>k </math> out of the last <math> \ell </math> successes and obtained a tight lower bound of win probability. When <math> \ell= k = 1,</math> the problem is equivalent to Bruss' odds problem. If <math>\ell= k \geq 1,</math> the problem is equivalent to that in {{harvnb|Bruss|Paindaveine|2000}}. A problem discussed by {{harvnb|Tamaki|2010}} is obtained by setting <math> \ell \geq k=1. </math>

=== Multiple choice problem ===

A player is allowed <math>r</math> choices, and he wins if any choice is the last success.

For classical secretary problem, {{harvnb|Gilbert|Mosteller|1966}} discussed the cases <math>r=2,3,4</math>.

The odds problem with <math> r=2, 3 </math> is discussed by {{harvnb|Ano|Kakinuma|Miyoshi|2010}}.

For further cases of odds problem, see {{harvnb|Matsui|Ano|2016}}.

An optimal strategy for this problem belongs to the class of strategies defined by a set of threshold numbers <math>(a_1, a_2, ..., a_r)</math>, where <math>a_1 > a_2 > \cdots > a_r</math>.

Specifically, imagine that you have <math>r</math> letters of acceptance labelled from <math>1</math> to <math>r</math>. You would have <math>r</math> 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 <math>i</math> would send their letter of acceptance to the first candidate that is better than all candidates <math>1</math> to <math>a_i</math>. (Unsent letters of acceptance are by default given to the last applicants, the same as in the standard secretary problem.)

When <math>r=2 </math>, {{harvnb|Ano|Kakinuma|Miyoshi|2010}} showed that the tight lower bound of win probability is equal to <math> e^{-1}+ e^{-\frac{3}{2}}. </math>

For general positive integer <math>r</math>, {{harvnb|Matsui|Ano|2016}} proved that the tight lower bound of win probability is the win probability of the [[Secretary problem#Pick the best, using multiple tries|secretary problem variant where one must pick the top-k candidates using just k attempts]].

When <math> r=3,4,5 </math>, tight lower bounds of win probabilities are equal to <math> e^{-1}+ e^{-\frac{3}{2}}+e^{-\frac{47}{24}} </math>, <math> e^{-1}+e^{-\frac{3}{2}}+e^{-\frac{47}{24}}+e^{-\frac{2761}{1152}} </math> and <math> e^{-1}+e^{-\frac{3}{2}}+e^{-\frac{47}{24}}+e^{-\frac{2761}{1152}}+e^{-\frac{4162637}{1474560}}, </math> respectively.

For further numerical cases for <math>r=6,...,10</math>, and an algorithm for general cases, see {{harvnb|Matsui|Ano|2016}}.

== See also ==

* [[Odds]]

* [[Clinical trial]]

* [[Expanded access]]

* [[Maintenance, repair and operations]]

* [[House sellingSecretary problem]]

* [[Parking problem]]

== References ==

*{{cite journal |last1=Ano |first1=K.|first2=H. |last2=Kakinuma |first3=N. |last3=Miyoshi |title=Odds theorem with multiple selection chances |journal=Journal of Applied Probability |volume=47 |year=2010 |issue=4|pages=1093–1104 |doi=10.1239/jap/1294170522|s2cid=17598431|doi-access=free }}

* {{cite journal | last=Bruss | first=F. Thomas | authorlink=Franz Thomas Bruss | title=Sum the odds to one and stop | journal=The Annals of Probability | publisher=Institute of Mathematical Statistics | volume=28 | issue=3 | year=2000 | issn=0091-1798 | doi=10.1214/aop/1019160340 | pages=1384–1391 | doi-access=free }}

** "[https://www.cambridge.org/core/journals/journal-of-applied-probability/article/note-on-a-lower-bound-for-the-multiplicative-odds-theorem-of-optimal-stopping/B759B6E4A9D83DB84D6EE1B4C827785B A note on Bounds for the Odds Theorem of Optimal Stopping]", ''[[Annals of Probability]]'' Vol. 31, 1859&ndash;1862, (2003).

** &mdash;"[https:''//web.archive.org/web/20230409100437/https://www.ems-ph.org/journals/newsletter/pdf/2006-12-62.pdf The art of a right decision.]", '' Newsletter of the [[European Mathematical Society]]'', Issue 62, 14&ndash;20, (2005).

*{{wikicite |ref={{SfnRef|Ferguson|2008}} |reference=[[Thomas S. Ferguson|T. S. Ferguson]]: (2008, unpublished)}}{{sfn whitelist|CITEREFFerguson2008}}

*{{cite journal |first1=F. T. |last1=Bruss |first2=D. |last2=Paindaveine |title=Selecting a sequence of last successes in independent trials |journal=Journal of Applied Probability |volume=37 |pages=389–399 |year=2000 |issue=2 |doi=10.1239/jap/1014842544 |url=https://mpra.ub.uni-muenchen.de/21166/1/MPRA_paper_21166.pdf}}

*{{Cite journal|last1=Gilbert |first1=J |last2=Mosteller |first2=F |title= Recognizing the Maximum of a Sequence |journal=Journal of the American Statistical Association |volume=61 |pages=35–73 |year=1966 |issue=313 |doi=10.2307/2283044 |jstor=2283044 }}

*{{cite journal |last1=Matsui |first1=T |last2=Ano | first2=K |title=A note on a lower bound for the multiplicative odds theorem of optimal stopping | journal=Journal of Applied Probability |volume=51 |pages=885–889 |year=2014 |issue=3 |doi=10.1239/jap/1409932681 |doi-access=free }}

*{{cite journal |last1=Matsui |first1=T |last2=Ano | first2=K |title=Lower bounds for Bruss' odds problem with multiple stoppings |journal=[[Mathematics of Operations Research]] |volume=41 |pages=700–714 |year=2016 |issue=2 |doi=10.1287/moor.2015.0748 |arxiv=1204.5537 |s2cid=31778896 }}

*{{cite journal |last1=Matsui |first1=T |last2=Ano | first2=K |title=Compare the ratio of symmetric polynomials of odds to one and stop |journal=Journal of Applied Probability |volume=54 |pages=12–22 |year=2017 |doi=10.1017/jpr.2016.83 |s2cid=41639968 |url=http://t2r2.star.titech.ac.jp/cgi-bin/publicationinfo.cgi?q_publication_content_number=CTT100773751 }}

* Shoo-Ren Hsiao and Jiing-Ru. Yang: ''"[https://www.cambridge.org/core/journals/journal-of-applied-probability/article/selecting-the-last-success-in-markovdependent-trials/09D192C389B4BA5D4E2CA678E11B31CC Selecting the Last Success in Markov-Dependent Trials'']", ''[[Journal of Applied Probability]]'', Vol. 93, 271&ndash;281, (2002).)

*{{cite journal |last1=Tamaki |first1=M | title=Sum the multiplicative odds to one and stop |journal=Journal of Applied Probability |volume=47 |pages=761–777 |year=2010 |issue=3 |doi=10.1239/jap/1285335408 |s2cid=32236265 |doi-access=free }}

* Mitsushi Tamaki:'' "[https://www.cambridge.org/core/journals/journal-of-applied-probability/article/optimal-stopping-on-trajectories-and-the-ballot-problem/4DEDE2A52A75420648C0DF39797E4A64 Optimal Stopping on Trajectories and the Ballot Problem'']", ''[[Journal of Applied Probability]] '' Vol. 38, 946&ndash;959 (2001).

* E. Thomas, E. Levrat, B. Iung: ''"[https://hal.archives-ouvertes.fr/hal-00149994/document L'algorithme de Bruss comme contribtioncontribution à une maintenance préventive'']", ''[[Sciences et Technologies de l'automation]]'', Vol. 4, 13-18 (2007).

{{reflist}}

* [[F. Thomas Bruss]]:'' Sum the Odds to One and Stop'', [[Annals of Probability]] Vol. 28, 1384&ndash;1391 (2000).

* &mdash;:'' A note on Bounds for the Odds-Theorem of Optimal Stopping'', [[Annals of Probability]] Vol. 31, 1859&ndash;1862, (2003).

* &mdash;:'' The art of a right decision.'' Newsletter of the [[European Mathematical Society]], Issue 62, 14&ndash;20, (2005).

* Mitsushi Tamaki:''Optimal Stopping on Trajectories and the Ballot Problem'', [[Journal of Applied Probability]] Vol. 38, 946&ndash;959 (2001).

* Shoo-Ren Hsiao and Jiing-Ru. Yang: ''Selecting the Last Success in Markov-Dependent Trials'', [[Journal of Applied Probability]], Vol. 93, 271&ndash;281, (2002.)

* E. Thomas, E. Levrat, B. Iung: ''L'algorithme de Bruss comme contribtion à une maintenance préventive'', [[Sciences et Technologies de l'automation]], Vol. 4, 13-18 (2007).

*T.S. Ferguson: (2008, unpublished)

==External links==

* Bruss- Algorithmus http://www.p-roesler.de/odds.html

{{DEFAULTSORT:Odds Algorithm}}

[[Category:MathematicalOptimization optimizationalgorithms and methods]]

[[Category:Statistical algorithms]]

[[Category:Optimal decisions]]