En informática , un algoritmo de Monte Carlo es un algoritmo aleatorio cuyo resultado puede ser incorrecto con una probabilidad determinada (normalmente pequeña) . Dos ejemplos de dichos algoritmos son el algoritmo de Karger-Stein [1] y el algoritmo de Monte Carlo para el conjunto de arcos de retroalimentación mínimos [2] .
El nombre hace referencia al casino de Montecarlo en el Principado de Mónaco , conocido en todo el mundo como un icono del juego. El término "Monte Carlo" fue introducido por primera vez en 1947 por Nicholas Metropolis . [3]
Los algoritmos de Las Vegas son una versión dual 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 empleado 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 una probabilidad de 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 una probabilidad de uno satisface la definición.
Si bien se espera que la respuesta devuelta por un algoritmo determinista siempre sea correcta, este no es el caso de los algoritmos de Monte Carlo. Para los problemas de decisión , estos algoritmos generalmente se clasifican como sesgados hacia lo falso o sesgados hacia lo verdadero . Un algoritmo de Monte Carlo sesgado hacia lo falso siempre es correcto cuando devuelve falso ; un algoritmo sesgado hacia lo verdadero siempre es correcto cuando devuelve verdadero . Si bien esto describe algoritmos con errores unilaterales , otros pueden no tener sesgo; se dice que estos tienen errores bilaterales . La respuesta que brindan (ya sea verdadera o falsa ) 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 falso con probabilidad de al menos 1 ⁄ 2 y verdadero 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 este es un algoritmo con sesgo falso con 1 ⁄ 2 de corrección .
Para un algoritmo de Monte Carlo con errores unilaterales, la probabilidad de falla se puede reducir (y la probabilidad de éxito amplificar) ejecutando el algoritmo k veces. Considere nuevamente el algoritmo de Solovay-Strassen que es 1 ⁄ 2 -correcto con sesgo falso . Uno puede ejecutar este algoritmo varias veces devolviendo una respuesta falsa si llega a una respuesta falsa dentro de k iteraciones, y devolviendo verdadero en caso contrario . 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 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 se puede reducir nuevamente ejecutando el algoritmo k veces y devolviendo la función mayoritaria de las respuestas.
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 de error unilateral: si la respuesta correcta es falso , el algoritmo siempre lo dice, pero puede responder falso incorrectamente para algunos casos en los que la respuesta correcta es verdadero . [4] Por el contrario, la clase de complejidad ZPP describe problemas solucionables 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 se ha demostrado. [4] 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, pero donde la probabilidad de error no necesariamente puede estar acotada lejos de 1 ⁄ 2 . [4]
Los algoritmos aleatorios se dividen principalmente en sus dos tipos principales, Monte Carlo y Las Vegas, sin embargo, estos representan solo la parte superior de la jerarquía y se pueden clasificar aún más. [4]
"Tanto Las Vegas como Monte Carlo tratan con decisiones, es decir, problemas en su versión de decisión ". [4] "Sin embargo, esto no debería dar una impresión errónea y confinar estos algoritmos a tales problemas: ambos tipos de algoritmos aleatorios se pueden utilizar también en problemas numéricos, problemas en los que el resultado no es simplemente 'sí'/'no', sino en los que se necesita recibir un resultado que sea de naturaleza numérica". [4]
La tabla anterior representa un marco general para los algoritmos aleatorios de Monte Carlo y Las Vegas. [4] En lugar del símbolo matemático se podría utilizar , haciendo así que las probabilidades en el peor de los casos sean iguales. [4]
Los algoritmos de Monte Carlo más 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 Schreier-Sims en la teoría de grupos computacionales .
En el caso de los algoritmos que forman parte del grupo de algoritmos de optimización estocástica (SO), donde la probabilidad no se conoce de antemano y se determina empíricamente, a veces es posible fusionar Monte Carlo y un algoritmo de este tipo "para tener tanto el límite de probabilidad calculado de antemano como un componente de optimización estocástica". [4] "Un ejemplo de un algoritmo de este tipo es Ant Inspired Monte Carlo". [4] [5] De esta manera, "se ha mitigado el inconveniente de SO y se ha establecido la confianza en una solución". [4] [5]
