Ik heb een lezing van MIT over Skip List bekeken. Over het algemeen begrijp ik het materiaal, maar één ding. Wat is “met hoge waarschijnlijkheid”? Ik snap het helemaal niet. Ik heb de dictaten gezien, maar snapte het nog steeds niet.
Ze zei: “Gebeurtenis $ E $ vindt plaats met een hoge waarschijnlijkheid (whp) als, voor elke $ \ alpha \ geq1 $, er een geschikte keuze is van constanten waarvoor $ E $ optreedt met een waarschijnlijkheid van ten minste $ 1 – O (1 / n ^ \ alpha) $ “.
Iets van algoritmist.com hielp ook niet.
Wat is $ \ alpha $ en wat is $ 1 – O (1 / n ^ \ alpha) $? Als ik dit niet begrijp, ben ik in de war van de analyse van waarom “Met grote waarschijnlijkheid kost elke zoekopdracht in een $ n $ -element overslaan-lijst $ O (\ lg n) $”.
Opmerkingen
- Merk op dat gerandomiseerde en probabilistische algoritmen niet hetzelfde zijn .
Answer
Een gebeurtenis vindt met grote waarschijnlijkheid plaats met betrekking tot een parameter $ n $ als het gebeurt met waarschijnlijkheid $ p_n $ en $ \ lim_ {n \ to \ infty} p_n = 1 $. Gewoonlijk is de parameter $ n $ duidelijk uit de context. In dit geval is het bijvoorbeeld waarschijnlijk het aantal elementen in de lijst.
De definitie van “met hoge waarschijnlijkheid” in de dictaten is nog specifieker en specificeert hoe snel $ p_n $ zou moeten convergeren tot $ 1 $: een gebeurtenis vindt plaats met een hoge waarschijnlijkheid als het gebeurt met waarschijnlijkheid $ p_n \ geq C / n ^ \ alpha $ voor een paar $ C, \ alpha > 0 $. Als u bijvoorbeeld een willekeurig getal kiest uit $ \ {0, \ ldots, n \} $, is de kans groot dat het niet nul is, aangezien de kans dat het niet-nul is $ 1-1 / (n + 1) is \ geq 1-1 / n $ (dus in dit geval $ C = \ alpha = 1 $).
Reacties
- Het limietcriterium is ook wel " genoemd, bijna zeker ". Ik heb " hoge waarschijnlijkheid " vooral gebruikt om te verwijzen naar waarschijnlijkheden die een met exponentiële snelheid naderen.
- Wanneer ik zie " whp " het is meestal synoniem met " vrijwel zeker ", en wanneer ik het gebruik (zonder het te definiëren) is dit altijd de betekenis waarnaar ik verwijs. Maar meer in het algemeen zou " whp " kunnen betekenen dat u 1 nadert, 1 polynoom snel nadert of 1 exponentieel snel nadert. Als je het in een van de laatste zin gebruikt, zorg er dan voor dat je het expliciet definieert.
- Echt, je ' noemt $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " met een hoge waarschijnlijkheid "? 😉 Maar ja: voor de zekerheid, definieer in ieder geval wat je bedoelt in je context.
- Wat is een standaardreferentie (bijv. Leerboeken) die WHP formeel definieert? Ik heb geprobeerd een artikel over WHP te schrijven in wikipedia en.wikipedia.org/wiki/With_high_probability , maar het werd voorgesteld om te verwijderen omdat er geen bronnen zijn, dus ik ben zoeken naar bronnen ..
- U kunt de handboeken over standaardcomplexiteit en algoritmen bekijken. Maar zelfs als je een referentie vindt, is dat ' alleen dat specifieke tekstboek ' s gebruik van de term. Het ' is waarschijnlijk het beste om het gewoon expliciet te definiëren als een algemene definitie zonder enig specifiek " bewijs ".