Descripción del comportamiento limitante en algoritmos probabilísticos
En matemáticas , un evento que ocurre con alta probabilidad (a menudo abreviado como whp o WHP ) es uno cuya probabilidad depende de un cierto número n y tiende a 1 cuando n tiende a infinito, es decir, la probabilidad de que ocurra el evento se puede hacer tan cercana a 1 como se desee haciendo n lo suficientemente grande.
Aplicaciones
El término WHP se utiliza especialmente en informática , en el análisis de algoritmos probabilísticos . Por ejemplo, considere un determinado algoritmo probabilístico en un gráfico con n nodos. Si la probabilidad de que el algoritmo devuelva la respuesta correcta es , entonces, cuando el número de nodos es muy grande, el algoritmo es correcto con una probabilidad muy cercana a 1. Este hecho se expresa brevemente diciendo que el algoritmo es correcto WHP.
Algunos ejemplos donde se utiliza este término son:
- Prueba de primalidad de Miller-Rabin : algoritmo probabilístico para comprobar si un número dado n es primo o compuesto. Si n es compuesto, la prueba detectará n como WHP compuesto. Existe una pequeña posibilidad de que tengamos mala suerte y la prueba piense que n es primo. Sin embargo, la probabilidad de error se puede reducir indefinidamente ejecutando la prueba muchas veces con diferentes aleatorizaciones.
- Algoritmo de Freivalds : un algoritmo aleatorio para verificar la multiplicación de matrices. Se ejecuta más rápido que los algoritmos deterministas WHP.
- Treap : un árbol de búsqueda binario aleatorio. Su altura es logarítmica WHP. El árbol de fusión es una estructura de datos relacionada.
- Códigos online : códigos aleatorios que permiten al usuario recuperar el mensaje original WHP.
- BQP : una clase de complejidad de problemas para los cuales existen algoritmos cuánticos de tiempo polinomial que son WHP correctos.
- Aprendizaje probablemente aproximadamente correcto : un proceso de aprendizaje automático en el que la función aprendida tiene un error de generalización WHP bajo.
- Protocolos de chismes : un protocolo de comunicación utilizado en sistemas distribuidos para entregar mensajes de manera confiable a todo el clúster utilizando una cantidad constante de recursos de red en cada nodo y garantizando que no haya un solo punto de falla.
Véase también
Referencias
- Métivier, Y.; Robson, JM; Saheb-Djahromi, N.; Zemmari, A. (2010). "Un algoritmo MIS distribuido aleatorio de complejidad de bits óptima". Computación distribuida . 23 (5–6): 331. doi :10.1007/s00446-010-0121-5.
- "Principios de computación distribuida (lección 7)" (PDF) . ETH Zurich . Consultado el 21 de febrero de 2015 .
