Jag såg föreläsning från MIT om Skip List. Sammantaget förstår jag materialet, men en sak. Vad är ”med hög sannolikhet”? Jag förstår verkligen inte det alls. Jag har sett föreläsningsanteckningarna men fick det ändå inte.
De bara sa, ”Händelse $ E $ inträffar med hög sannolikhet (whp) om det för varje $ \ alpha \ geq1 $ finns ett lämpligt val av konstanter för vilka $ E $ uppträder med sannolikhet minst $ 1 – O (1 / n ^ \ alpha) $ ”.
Något från algoritmist.com hjälpte inte heller.
Vad är $ \ alpha $ och vad är $ 1 – O (1 / n ^ \ alpha) $? Att inte förstå den här saken gör mig förvirrad över analysen av varför ”Med hög sannolikhet kostar varje sökning i en $ n $ -elementlista $ O (\ lg n) $”.
Kommentarer
- Observera att randomiserade och probabilistiska algoritmer inte är samma sak .
Svar
En händelse händer med hög sannolikhet med avseende på en parameter $ n $ om det händer med sannolikhet $ p_n $ och $ \ lim_ {n \ to \ infty} p_n = 1 $. Vanligtvis är parametern $ n $ tydlig från sammanhanget. I det här fallet är det till exempel antagligen antalet element i listan.
Definitionen av ”med hög sannolikhet” i föreläsningsanteckningarna är ännu mer specifik och anger hur snabbt $ p_n $ ska konvergera till $ 1 $: en händelse händer med hög sannolikhet om det händer med sannolikhet $ p_n \ geq C / n ^ \ alpha $ för vissa $ C, \ alpha > 0 $. Om du till exempel väljer ett slumpmässigt tal från $ \ {0, \ ldots, n \} $ så är det icke-noll med hög sannolikhet eftersom sannolikheten att det är icke-noll är $ 1-1 / (n + 1) \ geq 1-1 / n $ (så i det här fallet $ C = \ alpha = 1 $).
Kommentarer
- Gränskriteriet är kallas också " nästan säkert ". Jag har sett " hög sannolikhet " används mest när jag hänvisar till sannolikheter som närmar sig en med exponentialhastighet.
- När jag se " whp " det är vanligtvis synonymt med " nästan säkert ", och när jag använder det (utan att definiera det) är det alltid den meningen jag hänvisar till. Men mer allmänt kan " whp " betyda antingen att närma sig 1, närma sig 1 polynomiskt snabbt eller närma sig 1 exponentiellt snabbt. Om du använder den i någon av de senare betydelserna, var noga med att definiera den uttryckligen.
- Verkligen, du ' d ringer $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " med hög sannolikhet "? 😉 Men ja: för att vara säker, definiera vad du menar i ditt sammanhang i alla fall.
- Vad är en standardreferens (t.ex. läroböcker) som definierar WHP formellt? Jag försökte skriva en artikel om WHP i wikipedia sv.wikipedia.org/wiki/With_high_probability men det föreslogs att de skulle raderas eftersom det inte finns några källor, så jag är letar efter källor ..
- Du kan kontrollera standardböcker för komplexitet och algoritmer. Men även om du hittar en referens är att ' bara är den specifika lärobok ' som termen använder. Det ' är förmodligen bäst att bara definiera det uttryckligen som en vanlig definition utan något specifikt " bevis ".