Asymptotisk sikker begivenhed

En asymptotisk sikker hændelse er en hændelse, hvis sandsynlighed afhænger af en eller anden parameter og har tendens til , da den tenderer mod uendelig, det vil sige, at sandsynligheden for denne hændelse kan gøres vilkårligt høj ved at øge . En sådan hændelse siges at forekomme " med høj sandsynlighed " ( eng. med høj sandsynlighed , normalt forkortet til whp ) eller " asymptotisk næsten sikkert " ( asymptotisk næsten sikkert ). Hver næsten sikker begivenhed (som sker med sandsynlighed ) er asymptotisk sikker, det omvendte er ikke sandt. $n$ $en$ $n$ $n$ $en$

Anvendes i datalogi i den asymptotiske analyse af probabilistiske algoritmer . For eksempel, hvis en algoritme virker på grafer med toppunkter og sandsynligheden for at algoritmen giver det rigtige resultat er , så vil sandsynligheden for at algoritmen giver det rigtige svar med et tilstrækkeligt stort antal toppunkter i grafen være tæt på , det vil sige, vi kan sige, at "algoritmen korrekt med stor sandsynlighed. $n$ $1-1/n$ $en$

Nogle algoritmer, der bruger begrebet asymptotisk sikkerhed, er:

Miller-Rabin test : en probabilistisk algoritme til at kontrollere om et tal er primtal eller sammensat, hvis det er sammensat, så vil algoritmen bestemme dette med stor sandsynlighed; $n$ $n$
Freivalds algoritme : en randomiseret algoritme til kontrol af matrixproduktet, hurtigere end kendte deterministiske algoritmer med høj sandsynlighed;
kartesisk træ : et randomiseret binært søgetræ, hvis højde er logaritmisk med høj sandsynlighed.

I machine learning anvendes et sandsynligvis nogenlunde korrekt indlæringsskema , hvor den konstruerede funktion har en lav generaliseringsfejl med stor sandsynlighed.

BQP kompleksitetsklassen er udskilt , bestående af problemer, for hvilke der er polynomielle kvantealgoritmer , korrekt med høj sandsynlighed.

Asymptotisk sikker begivenhed

Links