The Sum-the-Odds Theorem with Application to a Stopping Game of Sakaguchi

• Autorzy: Ferguson T. S.

Identyfikatory

DOI

10.14708/ma.v44i1.1192

Warianty tytułu

PL

Twierdzenie o sumie ilorazów szans i jego zastosowanie do gry Sakaguchi’ego

• Języki publikacji: EN

Abstrakty

EN

The optimal stopping problem of maximizing the probability of stopping on the last success of a finite sequence of independent Bernoulli trials has been studied by Hill and Krengel (1992), Hsiau and Yang (2000) and Bruss (2000).The optimal stopping rule of Bruss stops when the sum of the odds of future successes is less than one. This Sum-the-Odds Theorem is extended in several ways. First, an infinite number of Bernoulli trials is allowed. Second, the payoff for not stopping is allowed to be different from the payoff of stopping on a success that is not the last success. Third, the Bernoulli variables are allowed to be dependent. Fourth, the model is generalized to allow at each stage other dependent random variables to be observed that may influence the assessment of the probability of success at future stages. Finally, application is made to a game of Sakaguchi (1984) in which two players vie for predicting the last success, but in which one of the players is given priority of acting first.

PL

Problem optymalnego zatrzymania na ostatnim sukcesie w ciągu prób Bernoulli’ego z maksymalnym prawdopodobieństwem badali Hill i Krengel (1992), Hsiau i Yang (2000) oraz Bruss (2000). Optymalna reguła zatrzymania podana przez Brussa mówi, ze należy zatrzymać się, gdy suma ilorazów szans przyszłych sukcesów jest mniejsza niż jeden. Twierdzenie wykorzystujące sumy ilorazów szans zostało uogólnione na wiele sposobów. Przede wszystkim uogólniono na nieskończony ciąg prób Bernoulli’ego. Innym jest dopuszczenie różnych wypłat za brak wyboru (zatrzymania) i zatrzymanie na sukcesie, który nie jest ostatnim. Kolejne, to dopuszczenie prób zależnych. Dalej, dopuszczono, aby na każdym etapie były obserwowane dodatkowe zmienne zależne, których obserwacja może zmienić ocenę prawdopodobieństwa sukcesu w przyszłych etapach. Wreszcie, zastosowano metodę do rozwiązania gry sformułowanej przez Sakaguchi’ego (1984), w którym dwaj gracze współzawodniczą o prognozę ostatniego sukcesu, gdy jeden z graczy ma pierwszy prawo podjęcia decyzji na każdym kroku.

Słowa kluczowe

EN

optimal stopping; best choice problems; stopping games

PL

gra o sumie zerowej; dominacja; problem sekretarki

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2016
• Tom: Vol. 44, No. 1
• Strony: 45--61
• Opis fizyczny: Bibliogr. 17 poz., fot.

Twórcy

autor

Ferguson T. S.

• University of California at Los Angeles, Mathematics Department, 405 Hilgard Ave., Los Angeles, CA 90095-1555, U.S.A.

Bibliografia

• [1] Ano, K., Kakinuma, H. and Miyoshi, N. [2010], ‘Odds theorem with multiple selection chances’, J. Appl. Probab. 47(4), 1093–1104. MR 2752887.
• [2] Bruss, F. T. [2000], ‘Sum the odds to one and stop’, Ann. Probab. 28(3), 1384–1391. MR 1797879. URL: http://dx.doi.org/10.1214/aop/1019160340
• [3] Bruss, F. T. [2003], ‘A note on bounds for the odds theorem of optimal stopping’, Ann. Probab. 31(4), 1859–1861. MR 2016602. URL: http://dx.doi.org/10.1214/aop/1068646368
• [4] Bruss, F. T. and Louchard, G. [2009], ‘The odds algorithm based on sequential updating and its performance’, Adv. in Appl. Probab. 41(1), 131–153. MR 2514948. URL: http://dx.doi.org/10.1239/aap/1240319579
• [5] Bruss, F. T. and Paindaveine, D. [2000], ‘Selecting a sequence of last successes in independent trials’, J. Appl. Probab. 37(2), 389–399. MR 1780998.
• [6] Bruss, F. T. and Yor, M. [2012], ‘Stochastic processes with proportional increments and the last-arrival problem’, Stochastic Process. Appl. 122(9), 3239–3261. MR 2946441. URL: http://dx.doi.org/10.1016/j.spa.2012.05.010
• [7] Chow, Y. S., Robbins, H. and Siegmund, D. [1991], The theory of optimal stopping, Dover Publications, Inc., New York. Corrected reprint of the 1971 original. MR 1105325.
• [8] Dendievel, R. [2013], ‘New developments of the odds-theorem’, Math. Sci. 38(2), 111–123. MR 3184683.
• [9] Dynkin, E. [1963], ‘The optimum choice of the instant for stopping a Markov process.’, Sov. Math., Dokl. 4, 627–629. Zbl 0242.60018.
• [10] Ferguson, T. S. [2005], ‘Game theory’. Electronic Text at http://www.math.ucla.edu/˜tom/Game Theory/Contents.html.
• [11] Ferguson, T. S. [2006], ‘Optimal stopping and applications’. Electronic Text at http://www.math.ucla.edu/˜tom/Stopping/Contents.html.
• [12] Gilbert, J. P. and Mosteller, F. [1966], ‘Recognizing the maximum of a sequence’, J. Amer. Statist. Assoc. 61, 35–73.
• [13] Hill, T. P. and Krengel, U. [1992], A prophet inequality related to the secretary problem, in ‘Strategies for sequential search and selection in real time (Amherst, MA, 1990)’, Vol. 125 of Contemp. Math., Amer. Math. Soc., Providence, RI, pp. 209–215. MR 1160621. URL: http://dx.doi.org/10.1090/conm/125/1160621
• [14] Hsiau, S.-R. and Yang, J.-R. [2000], ‘A natural variation of the standard secretary problem’, Statist. Sinica 10(2), 639–646. MR 1769760.
• [15] Hsiau, S.-R. and Yang, J.-R. [2002], ‘Selecting the last success in Markovdependent trials’, J. Appl. Probab. 39(2), 271–281. MR 1908944.
• [16] Sakaguchi, M. [1984], ‘Bilateral sequential games related to the noinformation secretary problem’, Math. Japon. 29(6), 961–973. MR 803454.
• [17] Tamaki, M. [2010], ‘Sum the multiplicative odds to one and stop’, J. Appl. Probab. 47(3), 761–777. MR 2731347. URL: http://dx.doi.org/10.1239/jap/1285335408

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.