Odds-theorem and monotonicity

• Autorzy: Bruss F. Thomas

Identyfikatory

DOI

10.14708/ma.v47i1.6481

Warianty tytułu

PL

Optymalne zatrzymywanie w oparciu o algorytm ilorazu szans a monotoniczność wartości problemu

• Języki publikacji: EN

Abstrakty

EN

Given a finite sequence of events and a well-defined notion of events being interesting, the Odds-theorem (Bruss(2000)) 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.

PL

Rozważamy optymalne zatrzymanie na wyróżnionym zdarzeniu w sekwencyjnym eksperymencie ze skończoną liczbą opcji. Twierdzenie o ilorazie szansach (Bruss(2000)) wyznacza taką strategię, która maksymalizuje szansę na właściwy wybór. Strategia ta jest optymalna, gdy mamy sekwencję niezależnych eksperymentów, a jej wyznaczanie jest proste. Służy do tego wspomniany algorytm oparty o sumowanie ilorazu szans. W pracy analizowane są szczególne własności takich zadań. Badana jest monotoniczność wartości optymalnej w powiązaniu z monotonicznością podstawowej sekwencji prawdopodobieństw zdarzeń. Podana jest motywacja do takich badań, a następnie udzielono pełnych odpowiedzi. Motywację wzmacniają problemy, w których pożądane jest zastosowanie algorytmu szans, ale w których brak informacji nie pozwala na to bez zastosowania sekwencyjnej estymacji nieznanych parametrów. W związku z takimi zagadnieniami wprowadzono pojęcie adaptacyjnego algorytmu ilorazu szans. Rozważania są ilustrowane przykładami.

Słowa kluczowe

EN

odds-algorithm; plug-in odds-algorithm; secretary problem; multiple stopping; group interviews; games; clinical trial; prophet inequality

PL

oscylacje harmoniczne; rozmaitości konfiguracji; rozwiązania przybliżone

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2019
• Tom: Vol. 47, no. 1
• Strony: 25--43
• Opis fizyczny: Bibliogr. 21 poz., fot.

Twórcy

autor

Bruss F. Thomas

• Université Libre de Bruxelles, Département de Mathématique, CP 210, B-1050 Brussels, Belgium

Bibliografia

• [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. ISSN 0001-8678. doi: 10.2307/1428183. Cited on p. 39.
• [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. ISSN 1382-6905. doi: 10.1007/s10878-017-0203-4. Cited on p. 38.
• [3] F. T. Bruss. Sum the odds to one and stop. Ann. Probab., 28 (3):1384-1391, 2000. ISSN 0091-1798. doi: 10.1214/aop/1019160340. Cited on pp. 25, 26, 27, 28, 30, 34, 38, and 43.
• [4] F. T. Bruss. Die Kunst der richtigen Entscheidung. Spektrum der Wissenschaft, June:78-82, 2005. Cited on p. 28.
• [5] F. T. Bruss. A mathematical approach to comply with ethical constraints in compassionate use treatments. Math. Sci., 43 (1):10-22, 2018. ISSN 0312-3685. Cited on pp. 28 and 37.
• [6] F. T. Bruss and T. S. Ferguson. Minimizing the expected rank with full information. J. Appl. Probab., 30 (3):616-626, 1993. ISSN 0021-9002. doi: 10.2307/3214770. Cited on p. 39.
• [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. doi: 10.1007/978-1-4612-0749-8_1. Cited on p. 39.
• [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. ISSN 0001-8678. doi: 10.1239/aap/1240319579. Cited on p. 28.
• [9] Bruss, F. Thomas. A unified approach to a class of best choice problems with an unknown number of options. Ann. Probab., 12 (3): 882-889, 1984. ISSN 0091-1798. URL http://links.jstor.org/sici?sici=0091-1798(198408)12:3<882:AUATAC>2.0.CO;2-M&origin=MSN. Cited on p. 40.
• [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. doi: 10.1214/aop/1068646368. Cited on p. 25.
• [11] R. Dendievel. New developments of the odds-theorem. Math. Sci., 38 (2):111-123, 2013. ISSN 0312-3685. Cited on p. 26.
• [12] T. S. Ferguson. The sum-the-odds theorem with application to a stopping game of Sakaguchi. Math. Appl., 44 (1):45-61, 2016. ISSN 1730-2668. doi: 10.14708/ma.v44i1.1192. Cited on p. 26.
• [13] A. V. Gnedin. On a best-choice problem with dependent criteria. J. Appl. Probab., 31 (1):221-234, 1994. ISSN 0021-9002. doi: 10.2307/3215248. Cited on p. 26.
• [14] A. Goldenshluger, Y. Malinovsky, and A. Zeevi. A Unified Approach for Solving Sequential Selection Problems. arXiv e-prints, art. arXiv:1901.04183, Jan 2019. Cited on p. 26.
• [15] S.-R. Hsiau and J.-R. Yang. A natural variation of the standard secretary problem. Statist. Sinica, 10 (2):639-646, 2000. ISSN 1017-0405. Cited on p. 38.
• [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. ISSN 0021-9002. doi: 10.1239/jap/1409932681. Cited on p. 26.
• [17] T. Matsui and K. Ano. Lower bounds for Bruss' odds problem with multiple stoppings. Math. Oper. Res., 41 (2):700-714, 2016. ISSN 0364-765X. doi: 10.1287/moor.2015.0748. Cited on p. 26.
• [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. ISSN 0040-361x. Cited on p. 40.
• [19] K. Szajowski. A game version of the Cowan-Zabczyk-Bruss' problem. Statist. Probab. Lett., 77 (17):1683-1689, 2007. ISSN 0167-7152. doi: 10.1016/j.spl.2007.04.008. Cited on p. 26.
• [20] M. Tamaki. Sum the multiplicative odds to one and stop. J. Appl. Probab., 47 (3):761-777, 2010. ISSN 0021-9002. doi: 10.1239/jap/1285335408. Cited on p. 26.
• [21] M. Tamaki. Maximizing the probability of stopping on any of the last m successes in independent Bernoulli trials with random horizon. Adv. in Appl. Probab., 43 (3):760-781, 2011. ISSN 0001-8678. doi: 10.1239/aap/1316792669. Cited on p. 26.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).