Robbinsův problém - Robbins problem - Wikipedia

Tento článek je o Robbinsově problému optimálního zastavení. Problém Robbins na booleovských algebrách viz Robbinsova algebra.

v teorie pravděpodobnosti, Robbinsův problém optimální zastavení, pojmenoval podle Herbert Robbins, se někdy označuje jako čtvrtý sekretářka problém nebo problém minimalizace očekávaný pozice s úplnými informacemi. Jeho prohlášení je následující.

Nechat X1, ... , Xn být nezávislý, identicky distribuovaný náhodné proměnné, jednotný na [0, 1]. Pozorujeme XkPostupně a musí se zastavit přesně na jednom z nich. Není povoleno odvolání předchozích pozorování. Jaké pravidlo zastavení minimalizuje očekávané hodnocení vybraného pozorování a jaká je jeho odpovídající hodnota?

Obecné řešení tohoto plně očekávaného problému s hodnocením informací není známo. Hlavní obtíž spočívá v tom, že problém je plně závislý na historii, to znamená, že optimální pravidlo závisí v každé fázi na všech předchozích hodnotách, a nejen na jejich jednodušších statistikách. Pro mezní hodnotu jsou známy pouze hranice proti tak jako n jde do nekonečna, konkrétně 1,908 <proti <2,329. Je známo, že existuje prostor pro zlepšení dolní meze dalšími výpočty pro zkrácenou verzi problému. Stále není známo, jak zlepšit horní mez, která vychází z podtřídy prahových pravidel bez paměti.

Důležitost

Jednou z motivací ke studiu Robbinova problému je, že s jeho řešením jsou všechny klasické (čtyři) problémy se sekretářkou bude vyřešen. Hlavním důvodem však je pochopit, jak zvládnout úplnou závislost na historii v (klamně snadno vypadajícím) problému. Na mezinárodní konferenci Ester's Book International Conference v Izraeli (2006) byl Robbinsův problém podle toho pojmenován jako jeden ze čtyř nejdůležitějších problémů v pole optimální zastavení a sekvenční analýza.

Dějiny

Herbert Robbins představil výše popsaný problém na Mezinárodní konference o vyhledávání a výběru v reálném čase v Amherst, 1990. Svůj projev zakončil slovy Rád bych viděl tento problém vyřešit, než zemřu. Vědci pracující v oblasti optimálního zastavení od té doby tento problém nazývají Robbinsův problém.

Reference

  • Chow, Y.S .; Moriguti, S .; Robbins, H .; Samuels, S.M. (1964). Msgstr "Optimální výběr na základě relativního hodnocení". Israel Journal of Mathematics. 2 (2): 81–90. doi:10.1007 / bf02759948.
  • "Minimalizace očekávané pozice s úplnými informacemi", F. Thomas Bruss a Thomas S. Ferguson, Journal of Applied Probability Objem 30, # 1 (1993), str. 616–626
  • Poloviční proroci a Robbinův problém minimalizace očekávané hodnosti, F. T. Bruss a T. S. Ferguson, Springerova přednáška ve statistice Objem 1 na počest J. M. Ganiho, (1996), s. 1–17
  • „Problém sekretářky; minimalizace očekávaného hodnocení pomocí náhodných proměnných i.i.d.“, D. Assaf a E. Samuel-Cahn, Adv. Appl. Prob. Objem 28, (1996), str. 828–852 Cat.Inist
  • „Co je známo o Robbinsově problému?“ F. Thomas Bruss, Journal of Applied Probability Objem 42, # 1 (2005), s. 108–120 Euklid
  • „Kontinuální přístup k Robbinovu problému minimalizace očekávané pozice“, F. Thomas Bruss a Yves Caoimhin Swan, Journal of Applied Probability Svazek 46 #1, 1–18, (2009).