Robbins problem

I sannolikhetsteorin hänvisas ibland till Robbins problem med optimalt stopp , uppkallat efter Herbert Robbins , som det fjärde sekreterarproblemet eller problemet med att minimera den förväntade rangen med full information. Dess uttalande är följande.

Låt X ₁ , ... , Xn _vara oberoende, identiskt fördelade stokastiska variabler , enhetliga på [0, 1]. Vi observerar X _k sekventiellt och måste stanna på exakt en av dem. Det är inte tillåtet att återkalla tidigare observationer. Vilken stoppregel minimerar den förväntade rangordningen för den valda observationen, och vad är dess motsvarande värde?

Den allmänna lösningen på detta förväntade rangproblem med fullständig information är okänd. Den stora svårigheten är att problemet är helt historiskt beroende, det vill säga den optimala regeln beror i varje skede på alla föregående värden, och inte bara på enklare tillräcklig statistik över dessa. Endast gränser är kända för gränsvärdet v när n går till oändlighet, nämligen 1,908 < v < 2,329. Det är känt att det finns ett visst utrymme att förbättra den nedre gränsen genom ytterligare beräkningar för en trunkerad version av problemet. Det är fortfarande inte känt hur man kan förbättra den övre gränsen som härrör från underklassen av minneslösa tröskelregler.

Betydelse

En av motiveringarna till att studera Robbins problem är att med dess lösning skulle alla klassiska (fyra) sekreterarproblem lösas. Men huvudskälet är att förstå hur man klarar av ett fullständigt historiaberoende i ett (bedrägligt lättskött) problem. På Ester's Book International Conference i Israel (2006) utsågs Robbins problem följaktligen till ett av de fyra viktigaste problemen inom området för optimal stoppning och sekventiell analys .

Historia

Herbert Robbins presenterade det ovan beskrivna problemet vid den internationella konferensen om sökning och urval i realtid i Amherst , 1990. Han avslutade sitt tal med orden Jag skulle vilja se detta problem löst innan jag dör . Forskare som arbetar inom området för optimal stopp har sedan dess kallat detta problem för Robbins problem .

Chow, YS; Moriguti, S.; Robbins, H.; Samuels, SM (1964). "Optimalt urval baserat på relativ rang" . Israel Journal of Mathematics . 2 (2): 81–90. doi : 10.1007/bf02759948 .
"Minimering av den förväntade rangordningen med fullständig information", F. Thomas Bruss och Thomas S. Ferguson , Journal of Applied Probability Volume 30 , #1 (1993), s. 616–626
Half-Prophets and Robbins' Problem of Minimizing the förväntad rang, FT Bruss och TS Ferguson, Springer Lecture Notes in Statistics Volume 1 in honour of JM Gani, (1996), s. 1–17
"Sekreterarproblemet; minimera den förväntade rangordningen med iid slumpvariabler", D. Assaf och E. Samuel-Cahn, Adv. Appl. Prob. Volym 28 , (1996), s. 828–852 Cat.Inist
"Vad är känt om Robbins problem?" F. Thomas Bruss , Journal of Applied Probability Volym 42 , #1 (2005), s. 108–120 Euclid
"A continuous-time approach to Robbins' problem of minimizing the expected rank", F. Thomas Bruss och Yves Caoimhin Swan, Journal of Applied Probability Volume 46 #1, 1–18, (2009).