Asymptoottisesti varma tapahtuma

Asymptoottisesti varma tapahtuma on tapahtuma, jonka todennäköisyys riippuu jostain parametrista ja pyrkii äärettömyyteen , eli tämän tapahtuman todennäköisyys voidaan tehdä mielivaltaisen suureksi lisäämällä . Tällaisen tapahtuman sanotaan tapahtuvan " suurella todennäköisyydellä " ( eng. suurella todennäköisyydellä , yleensä lyhennettynä whp ) tai " asymptoottisesti melkein varmasti " ( asymptoottisesti melkein varmasti ) . Jokainen lähes varma tapahtuma (joka tapahtuu todennäköisyydellä ) on asymptoottisesti varma, päinvastoin ei pidä paikkaansa. $n$ $yksi$ $n$ $n$ $yksi$

Käytetään tietojenkäsittelytieteessä todennäköisyyspohjaisten algoritmien asymptoottisessa analyysissä . Esimerkiksi, jos jokin algoritmi toimii graafisilla pisteillä ja todennäköisyys, että algoritmi antaa oikean tuloksen, on , niin riittävän suurella pistemäärällä graafissa on todennäköisyys, että algoritmi antaa oikean vastauksen. , eli voimme sanoa, että "algoritmi on oikea suurella todennäköisyydellä. $n$ ${\näyttötyyli 1-1/n}$ $yksi$

Jotkut algoritmit, jotka käyttävät asymptoottisen varmuuden käsitettä, ovat:

Miller-Rabin-testi : todennäköisyyspohjainen algoritmi, jolla tarkistetaan, onko luku alkuluku vai yhdistelmä, jos se on yhdistelmä, niin algoritmi määrittää tämän suurella todennäköisyydellä; $n$ $n$
Freivalds-algoritmi : satunnaistettu algoritmi matriisitulon tarkistamiseksi, nopeampi kuin tunnetut deterministiset algoritmit suurella todennäköisyydellä;
karteesinen puu : satunnaistettu binäärihakupuu, jonka korkeus on logaritminen suurella todennäköisyydellä.

Koneoppimisessa käytetään todennäköisesti suunnilleen oikeaa oppimismallia , jossa konstruoidulla funktiolla on pieni yleistysvirhe suurella todennäköisyydellä.

BQP:n kompleksisuusluokka on eritelty , joka koostuu ongelmista, joille on olemassa polynomisia kvanttialgoritmeja , jotka ovat oikein suurella todennäköisyydellä.

Linkit

Metivier, Y.; Robson, JM; Saheb-Djahromi, N.; Zemmari, A. Optimaalisen bittikompleksisuuden satunnaistettu hajautettu MIS-algoritmi // Distributed Computing : Journal. - 2010. - Vol. 23 , ei. 5-6 . - s. 331 . - doi : 10.1007/s00446-010-0121-5 .
Hajautetun laskennan periaatteet (luento 7) (linkki ei saatavilla) . ETH Zürich. Haettu 21. helmikuuta 2015. Arkistoitu alkuperäisestä 21. helmikuuta 2015. (määrätön)