Jeg så foredrag fra MIT om Skip List. Alt i alt forstår jeg materialet, men en ting. Hvad er “med høj sandsynlighed”? Jeg får det overhovedet ikke. Jeg har set forelæsningsnotater men fik det stadig ikke.
De bare sagde, “Begivenhed $ E $ opstår med høj sandsynlighed (whp), hvis der for enhver $ \ alpha \ geq1 $ er et passende valg af konstanter, for hvilke $ E $ forekommer med sandsynlighed mindst $ 1 – O (1 / n ^ \ alpha) $ “.
Noget fra algoritmist.com hjalp heller ikke.
Hvad er $ \ alpha $ og hvad er $ 1 – O (1 / n ^ \ alpha) $? At ikke forstå denne ting gør mig forvirret over analysen af hvorfor “Med stor sandsynlighed koster enhver søgning i en $ n $ -element-overspringliste $ O (\ lg n) $”.
Kommentarer
- Bemærk, at randomiserede og probabilistiske algoritmer ikke er de samme .
Svar
En begivenhed sker med stor sandsynlighed med hensyn til en parameter $ n $ hvis det sker med sandsynlighed $ p_n $ og $ \ lim_ {n \ to \ infty} p_n = 1 $. Normalt er parameteren $ n $ klar fra sammenhængen. I dette tilfælde er det for eksempel sandsynligvis antallet af elementer på listen.
Definitionen af “med stor sandsynlighed” i forelæsningsnoterne er endnu mere specifik, idet det angives, hvor hurtigt $ p_n $ skal konvergere til $ 1 $: en begivenhed sker med stor sandsynlighed, hvis den sker med sandsynlighed $ p_n \ geq C / n ^ \ alpha $ for nogle $ C, \ alpha > 0 $. Hvis du f.eks. Vælger et tilfældigt tal fra $ \ {0, \ ldots, n \} $, er det ikke-nul med stor sandsynlighed, da sandsynligheden for, at det ikke er nul, er $ 1-1 / (n + 1) \ geq 1-1 / n $ (så i dette tilfælde $ C = \ alpha = 1 $).
Kommentarer
- Grænsekriteriet er også kaldet " næsten sikkert ". Jeg har set " høj sandsynlighed " bruges mest, når jeg henviser til sandsynligheder, der nærmer sig en med eksponentiel sats.
- Når jeg se " whp " det er normalt synonymt med " næsten sikkert ", og når jeg bruger det (uden at definere det) er det altid den betydning, jeg henviser til. Men mere generelt kan " whp " betyde enten at nærme sig 1, nærme sig 1 polynomisk hurtigt eller nærme sig 1 eksponentielt hurtigt. Hvis du bruger det i en af sidstnævnte forstand, skal du sørge for at definere det eksplicit.
- Virkelig, du ' kalder $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " med stor sandsynlighed "? 😉 Men ja: for at være sikker skal du under alle omstændigheder definere, hvad du mener i din sammenhæng.
- Hvad er en standardreference (f.eks. Lærebøger), der definerer WHP formelt? Jeg forsøgte at skrive en artikel om WHP i wikipedia da.wikipedia.org/wiki/With_high_probability men det blev foreslået til sletning, fordi der ikke er nogen kilder, så jeg er på udkig efter kilder ..
- Du kan kontrollere standardbøger med kompleksitet og algoritmer. Men selvom du finder en reference, er ' kun den pågældende lærebog ' s brug af udtrykket. ' er sandsynligvis bedst at bare definere det eksplicit som en almindelig definition uden nogen specifik " bevis ".