A refined and asymptotic analysis of optimal stopping problems of Bruss and Weber

• Autorzy: Louchard G.

Identyfikatory

DOI

10.14708/ma.v45i2.4376

Warianty tytułu

PL

Dokładna i asymptotyczna analiza rozwiązań optymalnych problemów zatrzymania

• Języki publikacji: EN

Abstrakty

EN

The classical secretary problem has been generalized over the years into several directions. In this paper we confine our interest to those generalizations which have to do with the more general problem of stopping on a last observation of a specific kind. The Bruss-Weber problems we consider center around the following model: Let X₁, X₂,…,X_n be a sequence of independent and identically distributed random variables which can take three values: {+1,−1, 0}. The goal is to maximize the probability of stopping on a value +1 or −1 appearing for the last time in the sequence. We study related problems both in discrete and continuous time settings, with known or unknown number of observations, and known and unknown probability measure. In particular, so called x-strategy with incomplete information is taken into consideration. Our contribution in the present paper is a refined analysis of several problems in this class and a study of the asymptotic behaviour of solutions. We also present simulations of the corresponding complete selection algorithms.

PL

Klasyczny problem sekretarki został uogólniony na przestrzeni lat w kilku kierunkach. W niniejszym artykule ograniczamy nasze zainteresowanie do tych uogólnień, które mają związek z bardziej ogólnym problemem zatrzymania na ostatniej obserwacji określonego rodzaju. Problemy Brussa-Webera, które rozważamy, koncentrują się wokół następującego modelu: Obserwowany jest ciąg niezależnych zmiennych losowych o tym samym rozkładzie przyjmujących trzy wartosci: +1; −1; 0. Celem jest maksymalizacja prawdopodobieństwa zatrzymania na wartości +1 lub −1 pojawiającej się po raz ostatni w sekwencji. Badamy pokrewne problemy zarówno z czasem dyskretnym, jak i ciągłym, ze znaną lub nieznaną liczbą obserwacji oraz znanym i nieznanym rozkładem. W szczególności bierze się pod uwagę tak zwaną strategię z niepełną informacją. Nowością w niniejszej pracy jest udoskonalona analiza kilku problemów w tej klasie oraz badanie asymptotycznego zachowania się rozwiązań. Prezentujemy również symulacje odpowiednich kompletnych algorytmów wyboru.

Słowa kluczowe

EN

stopping times; unified approach to best choice; oddsalgorithm; optimal solutions; x-strategy; asymptotic expansions; incomplete information

PL

optymalny wybór momentu zatrzymania; problem wyboru najlepszego obiektu; algorytm oparty na ilorazie szans; rozwiązanie optymalne; ujęcie asymptotyczne; niepełna informacja

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2017
• Tom: Vol. 45, No. 2
• Strony: 95--118
• Opis fizyczny: Bibliogr. 18 poz., fot., tab., wykr.

Twórcy

autor

Louchard G.

• Université Libre de Bruxelles, Département d’Informatique, CP 212, Boulevard du Triomphe, B-1050 Bruxelles, Belgium

Bibliografia

• [1] K. Ano and M. Ando. A note on Bruss’ stopping problem with random availability. In Papers in honor of Thomas S. Ferguson, IMS Lectures Notes- Monograph Series, volume 35, pages 71-82. 2000. doi: 10.1214/lnms/1215089745MR1833852.
• [2] D. Assaf and E. Samuel-Cahn. Simple ratio prophet inequalities for a mortal with multiple choices. Journal of Applied Probability, 37 (4): 1084-1091, 2000. doi: 10.1239/jap/1014843085MR1808870.
• [3] F. T. Bruss. A unified approach to a class of best choice problems with an unknown number of options. Annals of Probability, 12(3):882-889, 1984. doi: 10.1214/aop/1176993237MR744243.
• [4] F. T. Bruss. On an optimal selection problem of Cowan and Zabczyk. Journal of Applied Probability, 24 (4): 918-928, 1987. doi: 10.2307/3214216MR913832Zbl0596.60046.
• [5] F. T. Bruss. Sum the odds to one and stop. Annals of Probability, 28 (3): 1384-1391, 2000. doi: 10.1214/aop/1019160340Zbl1005.60055.
• [6] F. T. Bruss. A note on bounds for the odds-theorem of optimal stopping. Annals of Probability, 31 (4): 1859-1861, 2003. doi: 10.1214/aop/1068646368Zbl1059.60056.
• [7] F. T. Bruss and T. S. Ferguson. High-risk and competitive investment models. Annals of Applied Probability, 12 (4): 1202-1226, 2002. doi: 10.1214/aoap/1037125860Zbl005.60054.
• [8] F. T. Bruss and G. Louchard. The odds-algorithm based on sequential updating and its performance. Advances in Applied Probability, 41: 131-153, 2009. doi: 10.1239/aap/1240319579Zbl1169.60006.
• [9] F. T. Bruss and M. Yor. Stochastic processes with proportional increments and the last arrival problem. Stochastic Processes and Their Applications, 122 (9): 3239-3261, 2012. doi: 10.1016/j.spa.2012.05.010Zbl1255.60166.
• [10] R. Dendievel. Weber’s optimal stopping problem and generalizations. Statistics and Probability Letters, 97: 176-184, 2015. doi: 10.1016/j.spl.2014.11.002Zbl1314.60088.
• [11] R. Dendievel. Sequential stopping under different environments of weak information. Ph.D. unpublished dissertation. Université libre de Bruxelles, Faculté des Sciences – Mathématiques, Bruxelles, 2016.
• [12] S. R. Hsiau and J. R. Yang. Selecting the last success in Markovdependent trials. Journal of Applied Probability, 39 (2): 271-281, 2002. doi: 10.1239/jap/1025131425MR1908944Zbl1006.60038.
• [13] A. Kurishima and K. Ano. Multiple stopping odds problem in Bernoulli trials with random number of observations. Mathematica Applicanda, 44 (1): 209-220, 2016. doi: 10.14708/ma.v44i1.1246MR3557098Zbl1370.60076.
• [14] T. Matsui and K. Ano. Lower bounds for Bruss’ odds problem with multiple stoppings. Mathematics of Operations Research, 41 (2): 700-714, 2016. doi: 10.1287/moor.2015.0748MR3486816Zbl1338.60119.
• [15] K. Szajowski and D. Łebek. Optimal strategies in high risk investments. Bulletin of the Belgian Mathematical Society-Simon Stevin, 14 (1): 143-155, 2007. MR 2327332 Zbl 1219.91128.
• [16] M. Tamaki. Sum the multiplicative odds to one and stop. Journal of Applied Probability, 47 (3): 761-777, 2010. doi: 10.1239/jap/1285335408MR2731347Zbl1201.60039.
• [17] R. R. Weber. Optimization and control, Section 6. Lecture Notes, Stat. Lab. U. Cambridge, 2013. available at www.statslab.cam.uk.
• [18] R. R. Weber. Private communication to Bruss. 2013.

Uwagi

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