PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Odds-theorem and monotonicity

Autorzy
Identyfikatory
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.
Rocznik
Strony
25--43
Opis fizyczny
Bibliogr. 21 poz., fot.
Twórcy
  • 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-519d8b15-e709-494f-a294-fffc7b642b2d
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.