Content deleted Content added
format as Template:wikicite |
|||
| (46 intermediate revisions by 19 users not shown) | |||
Line 1:
{{short description|Method of computing optimal strategies for last-success problems}}
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
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 <math>n</math> 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''.
# A physician, using a special treatment, may use the code 1 for a successful treatment, 0 otherwise. The physician treats a sequence of <math>n</math> 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 <math>n
the event that the kth observation is interesting (as defined by the decision maker), and <math>\, I_k=0</math> for non-interesting.
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
== Algorithmic procedure==
The odds
:<math> r_n + r_{n-1} + r_{n-2}\, +\cdots, \, </math>
Line 38:
# <math>\,w = Q_s R_s</math>, the win probability.
== Odds
The odds
The importance of the odds
==Odds
The odds
# The odds
# The win probability of the odds
# If <math>
==Features==
The odds
exist for all sequences, so that the odds
==Sources==
==Applications==
{{secretary_problem.svg}}
Applications reach from medical questions in [[clinical trial]]s over sales problems, [[secretary problems]], [[portfolio (finance)|portfolio]] selection, (one
There exists, in the same spirit, an Odds
and wrong stops as well as replacing independence assumptions by weaker ones
== Variations ==
{{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.
'''multiple choice 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>
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>.
Line 73 ⟶ 78:
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>
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}}
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=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}} (n \rightarrow \infty). </math>
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
== See also ==
Line 87 ⟶ 96:
== 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=
* {{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 }}
**
**
*{{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=
*{{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=
*{{cite journal |last1=Matsui |first1=T |last2=Ano | first2=K |title=
*{{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=
*
*{{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 }}
* 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).▼
* 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–959 (2001).
▲* E. Thomas, E. Levrat, B. Iung: "[https://hal.archives-ouvertes.fr/hal-00149994/document L'algorithme de Bruss comme contribution à une maintenance préventive]", ''[[Sciences et Technologies de l'automation]]'', Vol. 4, 13-18 (2007).
{{reflist}}
==External links==
* Bruss
{{DEFAULTSORT:Odds Algorithm}}
| |||