Odds-theorem and monotonicity. (English) Zbl 1463.60063
Summary: Given a finite sequence of events and a well-defined notion of events being interesting, the Odds-theorem [the author, Ann. Probab. 28, No. 3, 1384–1391 (2000; Zbl 1005.60055)] gives an online strategy to stop on the last interesting event. This strategy is optimal for independent events, and it is obtained in a straightforward way by an algorithm which is optimal itself (odds-algorithm). Here we study questions in how far the optimal value mirrors monotonicity properties of the underlying sequence of probabilities of events. We make these questions precise, motivate them, and then give complete answers. The motivation is enhanced by certain problems where it seems desirable to apply the odds-algorithm but where a lack of information does not allow to do so without incorporating sequential estimation. In view of this goal, the notion of a plug-in odds-algorithm is introduced. Several applications are included.
MSC:
| 60G40 | Stopping times; optimal stopping problems; gambling theory |
Keywords:
odds-algorithm; plug-in odds-algorithm; secretary problem; multiple stopping; group interviews; games; clinical trial; prophet inequalityCitations:
Zbl 1005.60055References:
| [1] | D. Assaf and E. Samuel-Cahn. The secretary problem: minimizing the expected rank with i.i.d. random variables. Adv. in Appl. Probab., 28(3): 828-852, 1996. · Zbl 0857.60039 |
| [2] | L. Bayón, P. Fortuny Ayuso, J. M. Grau, A. M. Oller-Marcén, and M. M. Ruiz. The Best-or-Worst and the Postdoc problems. J. Comb. Optim., 35(3):703-723, 2018. · Zbl 1416.90039 |
| [3] | F. T. Bruss. Sum the odds to one and stop. Ann. Probab., 28(3):1384-1391, 2000. · Zbl 1005.60055 |
| [4] | F. T. Bruss. Die Kunst der richtigen Entscheidung. Spektrum der Wissenschaft, June:78-82, 2005. · Zbl 1060.90661 |
| [5] | F. T. Bruss. A mathematical approach to comply with ethical constraints in compassionate use treatments. Math. Sci., 43(1):10-22, 2018. · Zbl 1414.60027 |
| [6] | F. T. Bruss and T. S. Ferguson. Minimizing the expected rank with full information. J. Appl. Probab., 30(3):616-626, 1993. · Zbl 0781.60035 |
| [7] | F. T. Bruss and T. S. Ferguson. Half-prophets and Robbins’ problem of minimizing the expected rank. In Athens Conference on Applied Probability and Time Series Analysis, Vol. I (1995), volume 114 of Lect. Notes Stat., pages 1-17. Springer, New York, 1996. · Zbl 0858.60045 |
| [8] | F. T. Bruss and G. Louchard. The odds algorithm based on sequential updating and its performance. Adv. in Appl. Probab., 41(1):131-153, 2009. · Zbl 1169.60006 |
| [9] | Bruss, F. Thomas. A united approach to a class of best choice problems with an unknown number of options. Ann. Probab., 12(3): 882-889, 1984. · Zbl 0553.60047 |
| [10] | Bruss, F. Thomas. A note on bounds for the odds theorem of optimal stopping. Ann. Probab., 31(4):1859-1861, 2003. ISSN 0091-1798. · Zbl 1059.60056 |
| [11] | R. Dendievel. New developments of the odds-theorem. Math. Sci., 38 (2):111-123, 2013. · Zbl 1291.60082 |
| [12] | T. S. Ferguson. The sum-the-odds theorem with application to a stopping game of Sakaguchi. Math. Appl., 44(1):45-61, 2016. · Zbl 1370.60074 |
| [13] | A. V. Gnedin. On a best-choice problem with dependent criteria. J. Appl. Probab., 31(1):221-234, 1994. · Zbl 0798.62085 |
| [14] | A. Goldenshluger, Y. Malinovsky, and A. Zeevi. A United Approach for Solving Sequential Selection Problems. arXiv e-prints, art. arXiv:1901.04183, Jan 2019. · Zbl 1446.60036 |
| [15] | S.-R. Hsiau and J.-R. Yang. A natural variation of the standard secretary problem. Statist. Sinica, 10(2):639-646, 2000. · Zbl 0963.62076 |
| [16] | T. Matsui and K. Ano. A note on a lower bound for the multiplicative odds theorem of optimal stopping. J. Appl. Probab., 51(3):885-889, 2014. · Zbl 1312.60047 |
| [17] | T. Matsui and K. Ano. Lower bounds for Bruss’ odds problem with multiple stoppings. Math. Oper. Res., 41(2):700-714, 2016. · Zbl 1338.60119 |
| [18] | E. L. Presman and I. M. Sonin. The problem of best choice in the case of a random number of objects. Teor. Verojatnost. i Primenen., 17:695-706, 1972. · Zbl 0296.60031 |
| [19] | K. Szajowski. A game version of the Cowan-Zabczyk-Bruss’ problem. Statist. Probab. Lett., 77(17):1683-1689, 2007. · Zbl 1138.60317 |
| [20] | M. Tamaki. Sum the multiplicative odds to one and stop. J. Appl. Probab., 47(3):761-777, 2010. · Zbl 1201.60039 |
| [21] | M. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
