A random walk version of Robbins' problem : small horizon

• Autorzy: Allaart Pieter C. , Allen Andrew

Identyfikatory

DOI

10.14708/ma.v47i2.6477

Warianty tytułu

PL

Problem Robbinsa dla błądzenia losowego : mały horyzont

• Języki publikacji: EN

Abstrakty

EN

In Robbins' problem of minimizing the expected rank, a finite sequence of n independent, identically distributed random variables are observed sequentially and the objective is to stop at such a time that the expected rank of the selected variable (among the sequence of all n variables) is as small as possible. In this paper we consider an analogous problem in which the observed random variables are the steps of a symmetric random walk. Assuming continuously distributed step sizes, we describe the optimal stopping rules for the cases n = 2 and n = 3 in two versions of the problem: a „full information" version in which the actual steps of the random walk are disclosed to the decision maker; and a „partial information" version in which only the relative ranks of the positions taken by the random walk are observed. When n = 3, the optimal rule and expected rank depend on the distribution of the step sizes. We give sharp bounds for the optimal expected rank in the partial information version, and fairly sharp bounds in the full information version.

PL

W problemie Robbinsa celem jest zatrzymanie sekwencyjnych obserwacji skończonego ciągu niezależnych zmiennych losowych o tym samym rozkładzie tak, aby zminimalizować oczekiwaną rangę zatrzymanej zmiennej. Niniejsza praca poświęcona jest analogonowi problemu Robbinsa, w którym obserwowane zmienne losowe są wartościami symetrycznego błądzenia losowego. Zakładamy, że długości kroków są symetrycznymi zmiennymi losowymi o rozkładzie typu ciągłego. Opisujemy optymalne reguły zatrzymania dla przypadków n = 2 i n = 3 w dwóch wersjach problemu: wersja z pełną informacją, w której rzeczywiste długości kroków losowych są jawne i znane podejmującemu decyzje statystykowi, oraz wersja z częściową informacją, w której obserwowane są tylko względne ciągi pozycji zajmowanych przez ciągły, symetryczny, spacer losowy. Dla n = 3 optymalna strategia i oczekiwana ranga zależą od rozkładu długości kroków. Otrzymano ostre oszacowania dla wartości oczekiwanej otrzymanej rangi dla wersji problemu z częściową informacją oraz lepsze oszacowania dla problemu z pełną informacją.

Słowa kluczowe

EN

expected rank; Robbins' problem; stopping time; symmetric random walk

PL

proces Ornsteina-Uhlenbecka; FLOC; estymacja; rozkład stabilny

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2019
• Tom: Vol. 47, no. 2
• Strony: 293--312
• Opis fizyczny: Bibliogr. 12 poz., fot., tab., wykr.

Twórcy

autor

Allaart Pieter C.

• University of North Texas, Department of Mathematics, 1155 Union Circle #311430, Denton, TX 76203-5017, USA

autor

Allen Andrew

• University of North Texas, Department of Mathematics, 1155 Union Circle #311430, Denton, TX 76203-5017, USA

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. MR 1404312. Cited on p. 294.
• [2] F. T. Bruss. What is known about Robbins' problem? J. Appl. Probab., 42 (1):108-120, 2005. ISSN 0021-9002. doi: 10.1239/jap/1110381374. MR 2144897. Cited on p. 294.
• [3] 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. MR 1232739. Cited on p. 294.
• [4] 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. MR 1466704. Cited on p. 294.
• [5] F. T. Bruss and Y. C. Swan. A continuous-time approach to Robbins' problem of minimizing the expected rank. J. Appl. Probab., 46 (1):1-18, 2009. ISSN 0021-9002. doi: 10.1239/jap/1238592113. MR 2508502. Cited on p. 294.
• [6] Y. S. Chow, S. Moriguti, H. Robbins, and S. M. Samuels. Optimal selection based on relative rank (the „Secretary problem”). Israel J. Math., 2:81-90, 1964. ISSN 0021-2172. doi: 10.1007/BF02759948. MR 176583. Cited on p. 294.
• [7] R. Dendievel and Y. Swan. One step more in Robbins' problem: explicit solution for the case n = 4. Math. Appl. (Warsaw), 44 (1):135-148, 2016. ISSN 1730-2668. doi: 10.14708/ma.v44i1.1138. MR 3557094. Cited on p. 294.
• [8] A. Gnedin and A. Iksanov. Moments of random sums and Robbins' problem of optimal stopping. J. Appl. Probab., 48 (4):1197-1199, 2011. ISSN 0021-9002. doi: 10.1239/jap/1324046028. MR 2896677. Cited on p. 294.
• [9] A. V. Gnedin. Optimal stopping with rank-dependent loss. J. Appl. Probab., 44 (4):996-1011, 2007. ISSN 0021-9002. doi: 10.1239/jap/1197908820. MR 2382941. Cited on p. 294.
• [10] D. A. Goldberg and Y. Chen. Beating the curse of dimensionality in options pricing and optimal stopping. CoRR, abs/1807.02227, 2018. URL http://arxiv.org/abs/1807.02227. Cited on p. 294.
• [11] M. Meier and L. Sögner. A new strategy for Robbins' problem of optimal stopping. J. Appl. Probab., 54 (1):331-336, 2017. ISSN 0021-9002. doi: 10.1017/jpr.2016.103. MR 3632622. Cited on p. 294.
• [12] Y. Swan. On two unsolved problems in probability. PhD thesis, Université Libre de Bruxelles, 2007. Cited on p. 294.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).