Algoritmo de Montecarlo

En informática, un algoritmo de Monte Carlo es un algoritmo aleatorio cuya salida puede ser incorrecta con una probabilidad determinada (normalmente pequeña). Dos ejemplos de tales algoritmos son el algoritmo de Karger-Stein y el algoritmo de Monte Carlo para un conjunto de arco de retroalimentación mínimo.

El nombre hace referencia al casino Monte Carlo en el Principado de Mónaco, conocido en todo el mundo como un ícono del juego. El término "Montecarlo" Fue introducido por primera vez en 1947 por Nicholas Metropolis.

Los algoritmos de Las Vegas son una combinación de los algoritmos de Monte Carlo y nunca devuelven una respuesta incorrecta. Sin embargo, pueden tomar decisiones aleatorias como parte de su trabajo. Como resultado, el tiempo necesario puede variar entre ejecuciones, incluso con la misma entrada.

Si existe un procedimiento para verificar si la respuesta dada por un algoritmo de Monte Carlo es correcta, y la probabilidad de una respuesta correcta está limitada por encima de cero, entonces, con probabilidad uno, ejecutar el algoritmo repetidamente mientras se prueban las respuestas eventualmente dará una respuesta correcta. Si este proceso es un algoritmo de Las Vegas depende de si se considera que detenerse con probabilidad satisface la definición.

Error unilateral versus bilateral

Si bien siempre se espera que la respuesta devuelta por un algoritmo determinista sea correcta, este no es el caso de los algoritmos de Monte Carlo. Para problemas de decisión, estos algoritmos generalmente se clasifican como con sesgo falso o con sesgo verdadero. Un algoritmo de Monte Carlo con sesgo falso siempre es correcto cuando devuelve falso; un algoritmo con sesgo verdadero siempre es correcto cuando devuelve verdadero. Si bien esto describe algoritmos con errores unilaterales, otros pueden no tener sesgos; se dice que tienen errores bilaterales. La respuesta que proporcionen (ya sea verdadero o falso) será incorrecta o correcta, con cierta probabilidad limitada.

Por ejemplo, la prueba de primalidad de Solovay-Strassen se utiliza para determinar si un número dado es un número primo. Siempre responde verdadero para entradas de números primos; para entradas compuestas, responde false con una probabilidad de al menos 1⁄2 y true con probabilidad menor que 1⁄2. Por lo tanto, las respuestas falsas del algoritmo seguramente serán correctas, mientras que las respuestas verdaderas siguen siendo inciertas; se dice que esto es un 1⁄2< /span>-algoritmo correcto con sesgo falso.

Amplificación

Para un algoritmo de Monte Carlo con errores unilaterales, la probabilidad de falla se puede reducir (y la probabilidad de éxito se puede amplificar) ejecutando el algoritmo k veces. Consideremos nuevamente el algoritmo de Solovay-Strassen, que es 1⁄2-corregir sesgo falso. Se puede ejecutar este algoritmo varias veces y devolver una respuesta falsa si alcanza una respuesta falsa dentro de k iteraciones y, en caso contrario, devolver verdadero<. /b>. Por lo tanto, si el número es primo, entonces la respuesta siempre es correcta, y si el número es compuesto, entonces la respuesta es correcta con una probabilidad de al menos 1−(1−1⁄2)^k = 1−2^-k.

Para los algoritmos de decisión de Monte Carlo con error bilateral, la probabilidad de falla puede reducirse nuevamente ejecutando el algoritmo k veces y devolviendo la función mayoritaria de las respuestas.

Clases de complejidad

La clase de complejidad BPP describe problemas de decisión que pueden resolverse mediante algoritmos de Monte Carlo de tiempo polinomial con una probabilidad limitada de errores bilaterales, y la clase de complejidad RP describe problemas que pueden resolverse mediante un algoritmo de Monte Carlo con una probabilidad limitada probabilidad de error unilateral: si la respuesta correcta es falso, el algoritmo siempre lo dice, pero puede responder falso incorrectamente en algunos casos en los que la respuesta correcta es verdadero. Por el contrario, la clase de complejidad ZPP describe problemas que se pueden resolver mediante algoritmos de Las Vegas de tiempo esperado polinomial. ZPP ⊆ RP ⊆ BPP, pero no se sabe si alguna de estas clases de complejidad es distinta entre sí; es decir, los algoritmos de Monte Carlo pueden tener más poder computacional que los algoritmos de Las Vegas, pero esto no ha sido probado. Otra clase de complejidad, PP, describe problemas de decisión con un algoritmo de Monte Carlo de tiempo polinomial que es más preciso que lanzar una moneda al aire, pero donde la probabilidad de error no necesariamente puede acotarse fuera de <. abarcan clase="num">1⁄2.

Aplicaciones en teoría computacional de números

Los algoritmos de Monte Carlo conocidos incluyen la prueba de primalidad de Solovay-Strassen, la prueba de primalidad de Baillie-PSW, la prueba de primalidad de Miller-Rabin y ciertas variantes rápidas del algoritmo de Schreier-Sims en la teoría de grupos computacional.