algoritmo de Monte Carlo

En informática , un algoritmo de Monte Carlo es un algoritmo aleatorio cuyo resultado puede ser incorrecto con una cierta probabilidad (generalmente pequeña) . Dos ejemplos de estos algoritmos son el algoritmo de Karger-Stein ^{[ 1 ]} y el algoritmo de Monte Carlo para el conjunto mínimo de arcos de retroalimentación ^{[ 2 ]} .

El nombre hace referencia al casino de Montecarlo en el Principado de Mónaco , conocido mundialmente 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 una variante de los algoritmos de Monte Carlo y nunca devuelven una respuesta incorrecta. Sin embargo, pueden realizar elecciones aleatorias durante su funcionamiento. Por consiguiente, el tiempo empleado puede variar entre ejecuciones, incluso con los mismos datos de entrada.

Si existe un procedimiento para verificar si la respuesta proporcionada por un algoritmo de Monte Carlo es correcta, y la probabilidad de una respuesta correcta está acotada positivamente, entonces, con probabilidad uno, ejecutar el algoritmo repetidamente mientras se prueban las respuestas eventualmente dará como resultado una respuesta correcta. Que este proceso sea un algoritmo de Las Vegas depende de si se considera que detenerse con probabilidad uno cumple con la definición.

Si bien se espera que la respuesta devuelta por un algoritmo determinista sea siempre correcta, esto no ocurre con los algoritmos de Monte Carlo. Para problemas de decisión , estos algoritmos se clasifican generalmente como sesgados hacia lo falso o 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 proporcionan (ya sea verdadera o falsa ) será incorrecta o correcta con cierta probabilidad acotada.

Por ejemplo, la prueba de primalidad de Solovay-Strassen se utiliza para determinar si un número dado es primo . Siempre responde verdadero para números primos; para números compuestos, 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 son con certeza correctas, mientras que las respuestas verdaderas permanecen inciertas; se dice que este es un algoritmo con sesgo de falso con una probabilidad de 1/2 .

Para un algoritmo de Monte Carlo con errores unilaterales, la probabilidad de fallo se puede reducir (y la probabilidad de éxito se puede amplificar) ejecutando el algoritmo k veces. Consideremos de nuevo el algoritmo de Solovay-Strassen, que es 1 / 2 -correcto con sesgo falso . Se puede ejecutar este algoritmo varias veces, devolviendo una respuesta falsa si alcanza una respuesta falsa dentro de k iteraciones, y devolviendo verdadero en caso contrario. Por lo tanto, si el número es primo , la respuesta siempre es correcta, y si el número es compuesto , 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 fallo puede reducirse nuevamente ejecutando el algoritmo k veces y devolviendo la función de mayoría 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 acotada de errores bilaterales, y la clase de complejidad RP describe problemas que pueden resolverse mediante un algoritmo de Monte Carlo con una probabilidad acotada de error unilateral: si la respuesta correcta es falsa , el algoritmo siempre lo dice, pero puede responder falso incorrectamente para algunos casos en los que la respuesta correcta es verdadera . ^{[ 4 ]} En contraste, la clase de complejidad ZPP describe problemas resolubles 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 de las demás; es decir, los algoritmos de Monte Carlo pueden tener más potencia 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 dos tipos principales: Monte Carlo y Las Vegas; sin embargo, estos representan solo la parte superior de la jerarquía y pueden categorizarse aún más. ^{[ 4 ]}

• Las Vegas
  • Sherwood: "un caso especial de Las Vegas, con un gran desempeño y eficacia".
  • Numérico —"Las Vegas numérico"
• Montecarlo
  • Atlantic City — "caso especial de error limitado de Monte Carlo"
  • Numérico: "aproximación numérica Monte Carlo"

"Tanto Las Vegas como Monte Carlo se ocupan de decisiones, es decir, problemas en su versión de decisión ." ^{[ 4 ]} "Sin embargo, esto no debe dar una impresión equivocada ni limitar estos algoritmos a tales problemas; ambos tipos de algoritmos aleatorios también pueden usarse en problemas numéricos, problemas donde la salida no es un simple 'sí'/'no', sino donde se necesita obtener un resultado 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${\displaystyle <}$uno podría usar${\displaystyle \leq }$, haciendo así que las probabilidades en el peor de los casos sean iguales. ^{[ 4 ]}

Entre los algoritmos de Monte Carlo más conocidos se 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 .

Para algoritmos que forman parte del grupo de algoritmos de Optimización Estocástica (OE), donde la probabilidad no se conoce de antemano y se determina empíricamente, a veces es posible combinar Monte Carlo con dicho algoritmo "para tener tanto un límite de probabilidad calculado de antemano como un componente de Optimización Estocástica". ^{[ 4 ]} "Un ejemplo de tal algoritmo es Monte Carlo inspirado en hormigas ". ^{[ 4 ] [ 5 ]} De esta manera, "se ha mitigado la desventaja de OE y se ha establecido confianza en una solución". ^{[ 4 ] [ 5 ]}

• Métodos de Monte Carlo , algoritmos utilizados en simulación física y estadística computacional basados ​​en la toma de muestras aleatorias.
• Algoritmo de Atlantic City
• Algoritmo de Las Vegas