Sledoval jsem přednášku MIT o Přeskočit seznam. Celkově materiálu rozumím, ale jedna věc. Co je „s vysokou pravděpodobností“? Opravdu to vůbec nechápu. Viděl jsem poznámky k přednášce , ale přesto jsem je nedostal.
Prostě jen řekl: „Událost $ E $ nastává s vysokou pravděpodobností (whp), pokud pro libovolný $ \ alpha \ geq1 $ existuje vhodný výběr konstant, pro které se $ E $ vyskytuje s pravděpodobností alespoň $ 1 – O (1 / n ^ \ alpha) $ „.
Něco z algorithmist.com také nepomohlo.
Co je $ \ alpha $ a co je $ 1 – O (1 / n ^ \ alpha) $? Nerozumění této věci mě zmátlo z analýzy, proč „S vysokou pravděpodobností stojí každé hledání v seznamu přeskočených prvků $ n $ -el $ O (\ lg n) $“.
Komentáře
- Pamatujte, že randomizované a pravděpodobnostní algoritmy nejsou to samé .
Odpověď
Událost se stane s vysokou pravděpodobností vzhledem k parametru $ n $, pokud k ní dojde s pravděpodobností $ p_n $ a $ \ lim_ {n \ to \ infty} p_n = 1 $. Obvykle je parametr $ n $ z kontextu jasný. V tomto případě například jde pravděpodobně o počet prvků v seznamu.
Definice „s vysokou pravděpodobností“ v poznámkách k přednášce je ještě konkrétnější a určuje, jak rychle se má $ p_n $ sbíhat do $ 1 $: událost se stane s vysokou pravděpodobností, pokud se stane s pravděpodobností $ p_n \ geq C / n ^ \ alpha $ za nějaké $ C, \ alpha > 0 $. Například pokud vyberete náhodné číslo z $ \ {0, \ ldots, n \} $, pak je nenulové s vysokou pravděpodobností, protože pravděpodobnost, že je nenulové, je $ 1-1 / (n + 1) \ geq 1-1 / n $ (v tomto případě tedy $ C = \ alpha = 1 $).
Komentáře
- Kritérium limitu je také téměř jistě " ". Viděl jsem " vysokou pravděpodobnost " použitou většinou při odkazování na pravděpodobnosti blížící se jedné s exponenciální rychlostí.
- Když jsem viz " whp " obvykle je synonymem " téměř jistě ", a když ji použiji (aniž bych ji definoval), vždy je to význam, na který odkazuji. Obecněji však " whp " může znamenat buď přiblížení k 1, přiblížení k 1 polynomiálně rychlému, nebo přiblížení k 1 exponenciálně rychlému. Používáte-li jej v některém z uvedených významů, nezapomeňte jej explicitně definovat.
- Opravdu ' zavoláte $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " s vysokou pravděpodobností "? 😉 Ale ano: pro jistotu v každém případě definujte, co máte na mysli ve svém kontextu.
- Co je to standardní odkaz (např. Učebnice), který formálně definuje WHP? Pokusil jsem se napsat článek o WHP na wikipedia en.wikipedia.org/wiki/With_high_probability , ale bylo navrženo jej smazat, protože neexistují žádné zdroje, takže jsem hledají zdroje ..
- Můžete zkontrolovat standardní učebnice složitosti a algoritmů. Ale i když najdete odkaz, ' používá pouze tento konkrétní výraz v učebnici '. ' Je pravděpodobně nejlepší definovat ji explicitně jako běžnou definici bez konkrétního " proof ".