Evento asintóticamente cierto

Un evento asintóticamente cierto es un evento cuya probabilidad depende de algún parámetro y tiende a infinito, es decir, la probabilidad de este evento puede hacerse arbitrariamente alta aumentando . Se dice que tal evento ocurre " con alta probabilidad " ( es decir , con alta probabilidad , generalmente abreviado como whp ) o " asintóticamente casi seguro " ( asintóticamente casi seguro ). Todo evento casi seguro (que ocurre con probabilidad ) es asintóticamente cierto, lo contrario no es cierto. $norte$ $una$ $norte$ $norte$ $una$

Utilizado en informática en el análisis asintótico de algoritmos probabilísticos . Por ejemplo, si algún algoritmo funciona en gráficos con vértices y la probabilidad de que el algoritmo dé el resultado correcto es , entonces con un número suficientemente grande de vértices en el gráfico, la probabilidad de que el algoritmo dé la respuesta correcta será cercana a , es decir, podemos decir que "el algoritmo corrige con alta probabilidad. $norte$ ${\ estilo de visualización 1-1/n}$ $una$

Algunos algoritmos que utilizan la noción de certeza asintótica son:

Prueba de Miller-Rabin : un algoritmo probabilístico para verificar si un número es primo o compuesto, si es compuesto, entonces el algoritmo lo determinará con una alta probabilidad; $norte$ $norte$
Algoritmo de Freivalds : un algoritmo aleatorio para verificar el producto de matrices, más rápido que los algoritmos deterministas conocidos con alta probabilidad;
árbol cartesiano : un árbol de búsqueda binario aleatorio cuya altura es logarítmica con alta probabilidad.

En el aprendizaje automático , se utiliza un esquema de aprendizaje probablemente aproximadamente correcto , en el que la función construida tiene un error de generalización bajo con una alta probabilidad.

Se destaca la clase de complejidad BQP , que consiste en problemas para los cuales existen algoritmos cuánticos polinómicos , correctos con alta probabilidad.

Enlaces

Métivier, Y.; Robson, JM; Saheb-Djahromi, N.; Zemmari, A. Un algoritmo MIS distribuido aleatorio de complejidad de bits óptima // Computación distribuida: revista. - 2010. - Vol. 23 , núm. 5-6 . — Pág. 331 . -doi : 10.1007/ s00446-010-0121-5 .
Principios de Computación Distribuida (lección 7) (enlace no disponible) . ETH Zúrich. Consultado el 21 de febrero de 2015. Archivado desde el original el 21 de febrero de 2015. (indefinido)