Am urmărit prelegeri de la MIT despre Skip List. În general, înțeleg materialul, dar un lucru. Ce este „cu probabilitate mare”? Chiar nu-l primesc deloc. Am „văzut notele de curs , dar încă nu le-am primit.
Ei doar a spus, „Evenimentul $ E $ are loc cu probabilitate mare (whp) dacă, pentru orice $ \ alpha \ geq1 $, există o alegere adecvată de constante pentru care $ E $ apare cu probabilitate de cel puțin $ 1 – O (1 / n ^ \ alpha) $ „.
Ceva din algorithmist.com nici nu a ajutat.
Ce este $ \ alpha $ și ce este $ 1 – O (1 / n ^ \ alpha) $? Nu înțeleg acest lucru mă face să mă confund cu analiza de ce „Cu probabilitate ridicată, fiecare căutare dintr-o listă de omiteri cu elemente de $ n $ costă $ O (\ lg n) $”.
Comentarii
- Rețineți că algoritmii randomizați și probabilistici nu sunt același lucru .
Răspuns
Un eveniment se întâmplă cu probabilitate ridicată în ceea ce privește un parametru $ n $ dacă se întâmplă cu probabilitatea $ p_n $ și $ \ lim_ {n \ to \ infty} p_n = 1 $. De obicei, parametrul $ n $ este clar din context. În acest caz, de exemplu, este probabil numărul de elemente din listă.
Definiția „cu probabilitate ridicată” în notele de curs este și mai specifică, specificând cât de rapid ar trebui să convergă $ p_n $ la $ 1 $: un eveniment se întâmplă cu probabilitate ridicată dacă se întâmplă cu probabilitatea $ p_n \ geq C / n ^ \ alpha $ pentru unele $ C, \ alpha > 0 $. De exemplu, dacă alegeți un număr aleatoriu din $ \ {0, \ ldots, n \} $, atunci acesta este diferit de zero, cu probabilitate ridicată, deoarece probabilitatea ca acesta să fie diferit de zero este $ 1-1 / (n + 1) \ geq 1-1 / n $ (deci în acest caz $ C = \ alpha = 1 $).
Comentarii
- Criteriul limită este numit și " aproape sigur ". Am văzut " probabilitate mare " folosită mai ales atunci când mă refer la probabilitățile care se apropie de una cu o rată exponențială.
- Când vezi " whp " este de obicei sinonim cu " aproape sigur ", iar când îl folosesc (fără a-l defini) acesta este întotdeauna sensul la care mă refer. Dar mai general, " whp " ar putea însemna fie apropierea de 1, apropierea de 1 polinomial rapid, fie apropierea de 1 exponențial de rapid. Dacă îl utilizați în oricare din ultimul sens, asigurați-vă că îl definiți în mod explicit.
- Într-adevăr, ' ați apelat $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " cu probabilitate mare "? 😉 Dar da: pentru a fi în siguranță, definiți la ce vă referiți în context, în orice caz.
- Ce este o referință standard (de exemplu, manuale) care definește WHP în mod formal? Am încercat să scriu un articol despre WHP în Wikipedia en.wikipedia.org/wiki/With_high_probability , dar a fost sugerat pentru ștergere deoarece nu există surse, așa că sunt căutarea surselor ..
- Puteți verifica manualele standard de complexitate și algoritmi. Dar chiar dacă găsiți o referință, ' este doar manualul respectiv ' pentru utilizarea termenului. Este ' probabil cel mai bine să o definiți în mod explicit ca o definiție comună, fără nicio " dovadă specifică ".