Jeg så på forelesning fra MIT om Skip List. Samlet sett forstår jeg materialet, men en ting. Hva er «med høy sannsynlighet»? Jeg får det ikke i det hele tatt. Jeg har sett forelesningsnotater , men fikk det fortsatt ikke.
De bare sa, «Hendelse $ E $ skjer med høy sannsynlighet (whp) hvis det for et $ \ alpha \ geq1 $ er et passende valg av konstanter som $ E $ opptrer med sannsynlighet minst $ 1 – O (1 / n ^ \ alpha) $ «.
Noe fra algoritmist.com hjalp heller ikke.
Hva er $ \ alpha $ og hva er $ 1 – O (1 / n ^ \ alpha) $? Å ikke forstå denne tingen gjør meg forvirret av analysen av hvorfor «Med stor sannsynlighet koster hvert søk i en $ n $ -elementhoppliste $ O (\ lg n) $».
Kommentarer
- Merk at randomiserte og sannsynlige algoritmer ikke er det samme .
Svar
En hendelse skjer med stor sannsynlighet med hensyn til en parameter $ n $ hvis det skjer med sannsynlighet $ p_n $ og $ \ lim_ {n \ to \ infty} p_n = 1 $. Vanligvis er parameteren $ n $ klar fra sammenhengen. I dette tilfellet er det for eksempel sannsynligvis antall elementer i listen.
Definisjonen av «med stor sannsynlighet» i forelesningsnotatene er enda mer spesifikk, og spesifiserer hvor raskt $ p_n $ skal konvergere til $ 1 $: en hendelse skjer med stor sannsynlighet hvis den skjer med sannsynlighet $ p_n \ geq C / n ^ \ alpha $ for noen $ C, \ alpha > 0 $. Hvis du for eksempel velger et tilfeldig tall fra $ \ {0, \ ldots, n \} $, er det ikke null med høy sannsynlighet siden sannsynligheten for at det ikke er null er $ 1-1 / (n + 1) \ geq 1-1 / n $ (så i dette tilfellet $ C = \ alpha = 1 $).
Kommentarer
- Grensekriteriet er også kalt " nesten sikkert ". Jeg har sett " stor sannsynlighet " brukt mest når det refereres til sannsynligheter som nærmer seg en med eksponentiell rate.
- Når jeg se " whp " det er vanligvis synonymt med " nesten sikkert ", og når jeg bruker den (uten å definere den) er dette alltid meningen jeg refererer til. Men mer generelt kan " whp " bety enten å nærme seg 1, nærme seg 1 polynomielt raskt, eller nærme seg 1 eksponentielt raskt. Hvis du bruker den i en av de sistnevnte forstandene, må du definere den eksplisitt.
- Virkelig, du ' kaller $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " med stor sannsynlighet "? 😉 Men ja: for å være trygg, definer hva du mener i din sammenheng uansett.
- Hva er en standard referanse (f.eks. Lærebøker) som definerer WHP formelt? Jeg prøvde å skrive en artikkel om WHP i wikipedia en.wikipedia.org/wiki/With_high_probability men det ble foreslått for sletting fordi det ikke er noen kilder, så jeg er leter etter kilder ..
- Du kan sjekke standardbøker for kompleksitet og algoritmer. Men selv om du finner en referanse, er ' bare den aktuelle læreboken ' s bruk av begrepet. Det ' er sannsynligvis best å bare definere det eksplisitt som en vanlig definisjon uten noe spesifikt " bevis ".