Problem Robbinsa

W teorii prawdopodobieństwa problem optymalnego zatrzymania Robbinsa , nazwany na cześć Herberta Robbinsa , jest czasami określany jako problem czwartego sekretarza lub problem minimalizacji oczekiwanej rangi przy pełnej informacji. Jej oświadczenie jest następujące.

Niech X ₁ , ... , X _n będą niezależnymi, identycznie rozłożonymi zmiennymi losowymi , jednorodnymi na [0, 1]. Obserwujemy X _k i musimy zatrzymać się dokładnie na jednym z nich. Niedozwolone jest przywoływanie poprzednich obserwacji. Jaka reguła stopu minimalizuje oczekiwaną rangę wybranej obserwacji i jaka jest jej odpowiadająca wartość?

Ogólne rozwiązanie tego problemu oczekiwanej rangi pełnej informacji jest nieznane. Główna trudność polega na tym, że problem jest w pełni zależny od historii, to znaczy, że optymalna reguła zależy na każdym etapie od wszystkich poprzednich wartości, a nie tylko od ich prostszych, wystarczających statystyk. Znane są tylko granice wartości granicznej v, gdy n dąży do nieskończoności, a mianowicie 1,908 < v < 2,329. Wiadomo, że istnieje możliwość poprawienia dolnej granicy poprzez dalsze obliczenia dla okrojonej wersji problemu. Nadal nie wiadomo, jak poprawić górną granicę, która wynika z podklasy bezpamięciowych reguł progowych.

Znaczenie

Jedną z motywacji do zbadania problemu Robbinsa jest to, że dzięki jego rozwiązaniu wszystkie klasyczne (cztery) problemy sekretarskie zostałyby rozwiązane. Ale głównym powodem jest zrozumienie, jak poradzić sobie z pełną zależnością historyczną w (pozornie łatwym) problemie. Na Międzynarodowej Konferencji Ester's Book w Izraelu (2006) problem Robbinsa został odpowiednio nazwany jednym z czterech najważniejszych problemów w dziedzinie optymalnego zatrzymania i analizy sekwencyjnej .

Historia

Herbert Robbins przedstawił wyżej opisany problem na Międzynarodowej Konferencji na temat Wyszukiwania i Selekcji w Czasie Rzeczywistym w Amherst w 1990 roku. Swoje wystąpienie zakończył słowami Chciałbym, aby ten problem został rozwiązany przed śmiercią . Naukowcy zajmujący się optymalnym zatrzymaniem od tego czasu nazwali ten problem problemem Robbinsa .

Chow, YS; Moriguti, S.; Robbins, H.; Samuels SM (1964). „Optymalny wybór na podstawie względnej rangi” . Izrael Journal of Mathematics . 2 (2): 81–90. doi : 10.1007/bf02759948 .
„Minimalizacja oczekiwanej rangi przy pełnej informacji”, F. Thomas Bruss i Thomas S. Ferguson , Journal of Applied Probability , tom 30 , nr 1 (1993), s. 616–626
Half-Prophets and Robbins 'Problem of Minimizing the oczekiwany stopień , FT Bruss i TS Ferguson, Springer Lecture Notes in Statistics Tom 1 na cześć JM Gani, (1996), s. 1–17
„Problem sekretarza; minimalizacja oczekiwanej rangi za pomocą zmiennych losowych iid”, D. Assaf i E. Samuel-Cahn, Adv. Aplikacja prawd. Tom 28 , (1996), s. 828–852 Cat.Inist
„Co wiadomo o problemie Robbinsa?” F. Thomas Bruss , Journal of Applied Probability , tom 42 , nr 1 (2005), s. 108–120 Euclid
„Podejście w czasie ciągłym do problemu Robbinsa polegającego na minimalizacji oczekiwanej rangi”, F. Thomas Bruss i Yves Caoimhin Swan, Journal of Applied Probability , tom 46 nr 1, 1–18, (2009).