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 [1] y el algoritmo de Monte Carlo para un conjunto de arco de retroalimentación mínimo . [2]
El nombre hace referencia al casino Montecarlo 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 . [3]
Los algoritmos de Las Vegas son duales 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.
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 de verdad siempre es correcto cuando devuelve verdadero . Si bien esto describe algoritmos con errores unilaterales , es posible que otros no tengan sesgos; se dice que tienen errores bilaterales . La respuesta que proporcionen (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 una probabilidad de al menos 1 ⁄ 2 y verdadero con una 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 algoritmo 1 ⁄ 2 correcto con sesgo falso .
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 tiene 1⁄2 correcto y falso sesgo . 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 . 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.
La clase de complejidad BPP describe problemas de decisión que pueden resolverse mediante algoritmos de Monte Carlo de tiempo polinómico 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 uno. Error unilateral: si la respuesta correcta es falsa , el algoritmo siempre lo dice, pero puede responder falsamente incorrectamente en algunos casos en los que la respuesta correcta es verdadera . [4] Por el contrario, la clase de complejidad ZPP describe problemas que se pueden resolver mediante algoritmos de Las Vegas de tiempo esperado polinómico. 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. [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 al aire, pero donde la probabilidad de error no necesariamente puede estar limitada a 1 ⁄ 2 . [4]
Los algoritmos aleatorios se dividen principalmente en dos tipos principales, Monte Carlo y Las Vegas; sin embargo, estos representan sólo la parte superior de la jerarquía y pueden clasificarse aún más. [4]
"Tanto Las Vegas como Montecarlo se enfrentan a decisiones, es decir, a problemas en su versión de decisión ". [4] "Sin embargo, esto no debería dar una impresión equivocada y limitar estos algoritmos a este tipo de problemas; ambos tipos de algoritmos aleatorios también se pueden usar en problemas numéricos, problemas donde el resultado no es simple 'sí'/'no', sino donde uno 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 , igualando así las probabilidades en el peor de los casos. [4]
Los algoritmos de Monte Carlo bien 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 computacional de grupos .
Para 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 dicho algoritmo "para tener ambos límites de probabilidad calculados de antemano y un componente de optimización estocástica." [4] "Un ejemplo de tal algoritmo es Ant Inspired Monte Carlo". [4] [5] De esta manera, "se ha mitigado el inconveniente de SO y se ha establecido confianza en una solución". [4] [5]
