Odds algorithm - Revision history

Cmglee: /* Applications */ Add secretary problem illustration

2025-04-04T15:08:12Z

Applications: Add secretary problem illustration

← Previous revision		Revision as of 15:08, 4 April 2025
Line 58:		Line 58:

	==Applications==		==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 online maintenance and others.		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 online maintenance and others.

DuncanHill: sfn whitelist

2024-06-15T20:35:57Z

sfn whitelist

← Previous revision		Revision as of 20:35, 15 June 2024
Line 99:		Line 99:
	** "[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).		** "[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).
	** "[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–20, (2005).		** "[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–20, (2005).
	*{{SfnRef inline\|Ferguson\|2008}}[[Thomas S. Ferguson\|T. S. Ferguson]]: (2008, unpublished)		*{{SfnRef inline\|Ferguson\|2008}}[[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 \|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=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 }}

Olexa Riznyk: Fixing style/layout errors

2024-06-10T20:16:29Z

Fixing style/layout errors

← Previous revision		Revision as of 20:16, 10 June 2024
Line 61:		Line 61:

	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 estimate]]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		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 estimate]]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 (Ferguson (2008)).		and wrong stops as well as replacing independence assumptions by weaker ones {{harv\|Ferguson\|2008}}.

	== Variations ==		== Variations ==
Line 99:		Line 99:
	** "[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).		** "[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).
	** "[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–20, (2005).		** "[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–20, (2005).
	*[[Thomas S. Ferguson\|T. S. Ferguson]]: (2008, unpublished)		*{{SfnRef inline\|Ferguson\|2008}}[[Thomas S. Ferguson\|T. S. Ferguson]]: (2008, unpublished)
	*{{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 \|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=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 }}

Olexa Riznyk: /* References */ Fixing style/layout errors

2024-05-27T18:42:32Z

References: Fixing style/layout errors

← Previous revision		Revision as of 18:42, 27 May 2024
Line 97:		Line 97:
	*{{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 \|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 }}		* {{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).		** "[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).
	* ~~—:~~ "[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–20, (2005).		** "[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–20, (2005).
	*[[Thomas S. Ferguson\|T. S. Ferguson]]: (2008, unpublished)		*[[Thomas S. Ferguson\|T. S. Ferguson]]: (2008, unpublished)
	*{{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 \|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}}

Olexa Riznyk: /* References */ Adding a wikilink

2024-05-27T18:13:46Z

References: Adding a wikilink

← Previous revision		Revision as of 18:13, 27 May 2024
Line 96:		Line 96:
	== References ==		== 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 \|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 \| 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 }}		* {{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).		* —: "[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).
	* —: "[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–20, (2005).		* —: "[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–20, (2005).

Lmendo: /* Examples */

2024-03-17T19:00:31Z

Examples

← Previous revision		Revision as of 19:00, 17 March 2024
Line 8:		Line 8:
	Two different situations exemplify the interest in maximizing the probability to stop on a last specific event.		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]] 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''.		# 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 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]].)		# 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 ==		== Definitions ==

TheMathCat: wikilink

2023-12-09T07:40:48Z

wikilink

← Previous revision		Revision as of 07:40, 9 December 2023
Line 103:		Line 103:
	*{{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=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=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=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 }}		*{{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–281, (2002).		* 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–281, (2002).

Cosmia Nebula: /* Multiple choice problem */ Pick the best, using multiple tries

2023-06-26T01:39:09Z

Multiple choice problem: Pick the best, using multiple tries

← Previous revision		Revision as of 01:39, 26 June 2023
Line 82:		Line 82:

	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>		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}} ~~discussed~~ the tight lower bound of win probability.		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.		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.

Cosmia Nebula: /* Multiple choice problem */ and an algorithm

2023-06-26T01:37:30Z

Multiple choice problem: and an algorithm

← Previous revision		Revision as of 01:37, 26 June 2023
Line 84:		Line 84:
	For general positive integer <math>r</math>, {{harvnb\|Matsui\|Ano\|2016}} discussed the tight lower bound of win probability.		For general positive integer <math>r</math>, {{harvnb\|Matsui\|Ano\|2016}} discussed the tight lower bound of win probability.
	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.		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 cases ~~that~~ <math>r=6,...,10</math>, see {{harvnb\|Matsui\|Ano\|2016}}.		For further numerical cases for <math>r=6,...,10</math>, and an algorithm for general cases, see {{harvnb\|Matsui\|Ano\|2016}}.

	== See also ==		== See also ==

Cosmia Nebula: /* Multiple choice problem */ clearer language

2023-06-26T01:36:44Z

Multiple choice problem: clearer language

← Previous revision		Revision as of 01:36, 26 June 2023
Line 77:		Line 77:
	For further cases of odds problem, see {{harvnb\|Matsui\|Ano\|2016}}.		For further cases of odds problem, see {{harvnb\|Matsui\|Ano\|2016}}.

	An optimal strategy 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~~>. ~~The~~ ~~first choice is to be used on the first candidates starting with <math~~>~~a_1</math>th applicant, and once the first choice is used, second choice is to be used on the first candidate starting with~~ ~~<math>a_2~~</math>~~th applicant, and so on~~.		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>		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>

← Previous revision		Revision as of 07:40, 9 December 2023
Line 103:		Line 103:
	*{{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=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=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=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 }}		*{{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–281, (2002).		* 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–281, (2002).