Content deleted Content added
No edit summary |
format as Template:wikicite |
||
| (97 intermediate revisions by 38 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 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
==Examples==
Two different situations exemplify
# 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
# 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
== 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
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.
== Algorithmic procedure
The odds
:<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'' = 1. At the same time it computes
:<math> Q_{s}=q_n q_{n-1}\cdots q_s.\,</math>
Line 40 ⟶ 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
==
==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
==
{{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.
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]]
* [[
== 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–1862, (2003).
**
*{{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:
*{{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:
* E. Thomas, E. Levrat, B. Iung:
{{reflist}}
▲* —:'' 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).
==External links==
* Bruss
{{DEFAULTSORT:Odds Algorithm}}
[[Category:
[[Category:Statistical algorithms]]
[[Category:Optimal decisions]]
| |||