One step more in Robbins' problem: Explicit solution for the case n = 4

• Autorzy: Dendievel R. , Swan Y.

Identyfikatory

DOI

10.14708/ma.v44i1.1138

Warianty tytułu

PL

O problemie Robbinsa słów kilka: dokładne rozwiązanie dla n = 4

• Języki publikacji: EN

Abstrakty

EN

Let X₁, X₂, …., X_n be independent random variables drawn from the uniform distribution on [0, 1]. A decision maker is shown the variables sequentially and, after each observation, must decide whether or not to keep the current one, with payoff being the overall rank of the selected observation. Decisions are final: no recall is allowed. The objective is to minimize the expected payoff. In this note we give the explicit solution to this problem, known as Robbins’ problem of optimal stopping, when n = 4.

PL

Niech X₁, X₂, …., X_n będzie ciągiem niezależnych zmiennych losowych o rozkładzie jednostajnym na [0, 1]. Statystyk obserwuje realizacje tych zmiennych sekwencyjnie i po każdej obserwacji decyduje o jej zatrzymaniu lub odrzuceniu. Zaakceptowanej obserwacji nie można w przyszłości zmieniać ani wracać do odrzuconych obserwacji. Celem jest minimalizacja oczekiwanej rangi zaakceptowanej obserwacji. Ten artykuł podaje rozwiązanie tego zadania dla n = 4. Problem w literaturze jest znany jako problem Robinsa.

Słowa kluczowe

EN

Poisson process; optimal stopping; best choice problem; full information; expected rank problem; sequential selection; secretary problem; threshold rules

PL

optymalne zatrzymanie procesu; problem wyboru najlepszego obiektu; problem optymalnego wielokrotnego zatrzymania; proces Poissona

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2016
• Tom: Vol. 44, No. 1
• Strony: 135--148
• Opis fizyczny: Bibliogr. 13 poz., rys., wykr.

Twórcy

autor

Dendievel R.

• Université libre de Bruxelles, Département de Mathematique, CP 212, Boulevard du Triomphe, B-1050 Bruxelles, Belgium

autor

Swan Y.

• Université de Liége, Département de Mathématique - zone polytech 1, 12 allée de la découverte, Bât. B37 pkg 33a, B-4000 Liége, Belgium

Bibliografia

• [1] Assaf, D. and Samuel-Cahn, E. (1996). The secretary problem; minimizing the expected rank with i.i.d. random variables, Adv. Appl. Prob., Vol. 28, pp. 828-852. doi: 10.2307/1428183
• [2] Bruss, F. T. (2005). What is known about Robbins’ problem?, J. Appl. Prob., Vol. 42, pp. 108-120. doi: 10.1239/jap/1110381374; MR 2144897; Zbl 1081.62059
• [3] Bruss, F. T. and Ferguson, T. S. (1993). Minimizing the expected rank with full information, J. Appl. Prob., Vol. 30, pp. 616 - 626. doi: 10.2307/3214770
• [4] Bruss, F. T. and Ferguson, T. S. (1996). Half-Prophets and Robbins’ problem of Minimizing the expected rank, Springer Lecture Notes in Stat. 114, Vol. 1 in honor of J.M. Gani, pp. 1-17. doi: 10.1007/978-1-4612-0749-8_1
• [5] Bruss, F. T. and Louchard, G. (2009). The odds algorithm based on sequential updating and its performance., Adv. Appl. Probab., Vol. 41(1), pp. 131–153. doi: 10.1239/aap/1240319579; Zbl 1169.60006
• [6] Bruss, F. T. and Swan, Y. (2009). A continuous-time approach to Robbins’ problem of minimizing the expected rank, J. Appl. Prob., Vol. 46, pp. 1-18. doi: 10.1239/jap/1238592113; MR 2508502; Zbl 05543690
• [7] Chow, Y. S., Moriguti, S., Robbins, H. and Samuels, S. M. (1964). Optimal selection based on relative ranks, Israel J. Math., 2 (2), 81-90. doi: 10.1007/bf02759948
• [8] Dendievel, R. (2013). New developments of the odds-theorem. Mathematical scientist, 38 (2), 111-123. MR 3184683
• [9] Gilbert, J. P. and Mosteller, F. (1966). Recognizing the Maximum of a Sequence. Journal of the American Statistical Association, 61 (313), 35-73. doi: 10.2307/2283044
• [10] Gnedin, A. V. (2007). Optimal Stopping with Rank-Dependent Loss, J. Appl. Prob., Vol. 44, pp. 996-1011. doi: 10.1239/jap/1197908820; MR 2382941; Zbl 1146.60038
• [11] Gnedin, A. V. and Iksanov, A. (2011). Moments of random sums and Robbins’ problem of optimal stopping, J. Appl. Prob., Vol. 48, pp. 1197-1199. doi: 10.1239/jap/1324046028; MR 2896677; Zbl 05994397
• [12] Meier, M. and Sögner, L. (2014). A New Upper Bound for Robbins’ problem. Available at SSRN 2408149. doi: 10.2139/ssrn.2408149
• [13] Swan, Y. C. (2011). A contribution to the study of Robbins’ Problem. Mémoire de l’Académie Royale des Sciences, des Lettres et des Beaux-Arts. Available at http://hdl.handle.net/2268/192589.

Uwagi

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