Algoritmo de Montecarlo

No debe confundirse con el método de Monte Carlo.

En informática, un algoritmo de Monte Carlo es un procedimiento probabilista cuya salida puede ser incorrecta con un valor de probabilidad (normalmente pequeño). Dos ejemplos de estos algoritmos son el algoritmo de Karger-Stein^[1] y el algoritmo de Monte Carlo para un conjunto de arcos de retroalimentación mínimo.^[2]

El nombre hace referencia al Casino de Montecarlo, situado en el Principado de Mónaco, conocido mundialmente 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 un 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 de 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 finalmente arrojará una respuesta correcta. Que este proceso sea un algoritmo de Las Vegas depende de si se considera que detenerse con probabilidad uno cumple la definición.

Error unilateral frente a error bilateral

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 un problema de decisión, estos algoritmos generalmente se clasifican como con sesgo de falso o verdadero. Un algoritmo de Monte Carlo con sesgo de falso siempre es correcto cuando devuelve falso; un algoritmo con sesgo de verdadero siempre es correcto cuando devuelve verdadero. Si bien esto describe algoritmos con errores unilaterales, otros podrían no tener sesgo, y se dice que estos tienen errores bilaterales. La respuesta que proporcionan (ya sea verdadero o falso) será incorrecta o correcta, con una probabilidad limitada.

Por ejemplo, el algoritmo para el test 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 igual o superior a ¹⁄₂ y verdadero con una probabilidad menor que ¹⁄₂. Por lo tanto, las respuestas falsas del algoritmo son correctas con certeza, mientras que las respuestas verdaderas permanecen inciertas. Se dice que este es un algoritmo ¹⁄₂-correcto con sesgo falso.

Amplificación

Para un algoritmo de Monte Carlo con errores unilaterales, la probabilidad de fallo se puede reducir (y la probabilidad de éxito amplificar) ejecutando el algoritmo k veces. Considérese de nuevo el algoritmo de Solovay-Strassen, que es ¹⁄₂-correcto con sesgo falso. Este algoritmo se puede ejecutar varias veces, devolviendo la respuesta falso si se obtiene una respuesta falso en 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µ¹⁄₂)^k=1µ2^−k.

Para algoritmos de decisión de Monte Carlo con error bilateral, la probabilidad de fallo se puede reducir ejecutando el algoritmo k veces y devolviendo la función mayorante de las respuestas.

Clases de complejidad

La clase de complejidad de un polinomio probabilístico de error acotado (BPP) describe problemas de decisión que pueden ser resueltos por 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 ser resueltos por 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 donde la respuesta correcta es verdadero.^[4] Por el contrario, la clase de complejidad ZPP describe problemas solucionables por 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 polinómico que es más preciso que lanzar una moneda, pero donde la probabilidad de error no puede necesariamente limitarse a ¹⁄₂.^[4]

Clases de algoritmos de Monte Carlo y de Las Vegas

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 pueden categorizarse aún más.^[4]

• Las Vegas
  • Sherwood: caso especial de Las Vegas eficaz y eficiente
  • Numérico: Las Vegas numérico
• Monte Carlo
  • Atlantic City: caso especial de Monte Carlo con error acotado
  • Numérico: Monte Carlo de aproximación numérica

"Tanto Las Vegas como Monte Carlo abordan decisiones, es decir, problemas en su versión de decisión."^[4] "Sin embargo, esto no debe dar una impresión errónea ni limitar estos algoritmos a este tipo de problemas. Ambos tipos de algoritmos probabilistas también pueden utilizarse en problemas numéricos, problemas donde la salida no es simplemente 'sí'/'no', sino donde se necesita obtener un resultado de naturaleza numérica."^[4]

Comparación de los algoritmos de Las Vegas y Montecarlo

	Eficiencia	Óptimo	Fallo (LV) / Error (MC)
Las Vegas (LV)	Probabilístico	Certero	${\displaystyle <{\tfrac {1}{2}}}$
Sherwood	Certero o probabilístico de Sherwood (límite más fuerte que el LV regular)	Certero	${\displaystyle 0}$
Numérico	Probabilístico, cierto o probabilístico de Sherwood	Certero	${\displaystyle <{\tfrac {1}{2}}}$ o ${\displaystyle 0}$
Monte Carlo (MC)	Certero	Probabilístico	${\displaystyle <1}$ (probabilidad que, tras repeticiones, crece subexponencialmente, y podría inhibir la utilidad del algoritmo; un caso típico es ${\displaystyle <{\tfrac {1}{2}}}$)
Atlantic City	Certero	Probabilístico	${\displaystyle <{\tfrac {1}{4}}}$
Numérico	Certero	Probabilístico	${\displaystyle <1}$ (depende del tipo de algoritmo)

La tabla anterior representa un marco general para algoritmos aleatorios de Monte Carlo y de Las Vegas.^[4] En lugar del símbolo matemático ${\displaystyle <}$, se podría usar ${\displaystyle \leq }$, igualando así las probabilidades en el peor de los casos.^[4]

Aplicaciones en teoría de números computacionales y otras áreas

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

Para algoritmos que forman parte del grupo de optimización estocástica (SO), donde la probabilidad no se conoce de antemano y se determina empíricamente, a veces es posible combinar Monte Carlo con dicho algoritmo para calcular previamente el límite de probabilidad y un componente de optimización estocástica.^[4] Un ejemplo de este tipo de algoritmo es el algoritmo de la colonia de hormigas basado en el algoritmo de Monte Carlo.^[4][5] De esta manera, se ha mitigado la desventaja de la optimización estocástica y se ha establecido la confianza de la solución.^[4][5]

Véase también

• Método de Montecarlo, 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