Asymptoticky jistá událost

Asymptoticky jistá událost je událost, jejíž pravděpodobnost závisí na nějakém parametru a směřuje k nekonečnu, to znamená, že pravděpodobnost této události může být libovolně vysoká zvýšením . Říká se, že taková událost nastane „ s vysokou pravděpodobností “ ( anglicky s vysokou pravděpodobností , obvykle zkráceno na whp ) nebo „ asymptoticky téměř jistě “ ( asymptoticky téměř jistě ). Každá téměř jistá událost (která se stane s pravděpodobností ) je asymptoticky jistá, obráceně to neplatí. $n$ $jeden$ $n$ $n$ $jeden$

Používá se v informatice při asymptotické analýze pravděpodobnostních algoritmů . Pokud například nějaký algoritmus pracuje na grafech s vrcholy a pravděpodobnost, že algoritmus dá správný výsledek, je , pak s dostatečně velkým počtem vrcholů v grafu se pravděpodobnost, že algoritmus dá správnou odpověď, bude blížit , to znamená, že můžeme říci, že „algoritmus je s vysokou pravděpodobností správný. $n$ $1-1/n$ $jeden$

Některé algoritmy používající pojem asymptotické jistoty jsou:

Miller-Rabinův test : pravděpodobnostní algoritmus pro kontrolu, zda je číslo prvočíslo nebo složené, pokud je složené, pak to algoritmus s vysokou pravděpodobností určí; $n$ $n$
Freivaldův algoritmus : randomizovaný algoritmus pro kontrolu maticového součinu, rychlejší než známé deterministické algoritmy s vysokou pravděpodobností;
kartézský strom : randomizovaný binární vyhledávací strom, jehož výška je s vysokou pravděpodobností logaritmická.

Ve strojovém učení se používá pravděpodobně přibližně správné schéma učení , ve kterém má sestrojená funkce nízkou chybu zobecnění s vysokou pravděpodobností.

Vyčleněna je třída složitosti BQP sestávající z problémů, pro které existují polynomiální kvantové algoritmy , které jsou s vysokou pravděpodobností správné.

Odkazy

Metivier, Y.; Robson, JM; Saheb-Djahromi, N.; Zemmari, A. Randomizovaný distribuovaný algoritmus MIS s optimální bitovou složitostí // Distributed Computing: journal. - 2010. - Sv. 23 , č. 5-6 . — S. 331 . - doi : 10.1007/s00446-010-0121-5 .
Principy distribuovaného počítání (přednáška 7) (odkaz není k dispozici) . ETH Curych. Získáno 21. února 2015. Archivováno z originálu 21. února 2015. (neurčitý)