¿Cuándo resuelve un algoritmo Monte Carlo?

Question

¿Cuándo podemos decir que un algoritmo de Monte Carlo resuelve un problema?

para citar de Wikipedia en Monte Carlo Algorithms

Por ejemplo, la prueba de primalidad Solovay-Strassen se usa para determinar si un número dado es un número primo.Siempre responde a las entradas de prime número;Para las entradas compuestas, responde False con probabilidad al menos ½ y verdadera con probabilidad menor que ½.

¿Qué pasaría si la prueba Sólovay-Strassen respondería verdadera por solo el 1% de las entradas compuestas?

¿Seguiríamos decidimos que resuelve el problema de la prueba de la primaria?

¿O hay algún requisito como ese un algoritmo Monte Carlo tiene que responder verdadero por más de la mitad de los casos?

Answer 1

En general Monte Carlo se utiliza para resolver una amplia variedad de diferentes tipos de problemas. En este caso particular, desea aprender si una variable aleatoria es la constante 1, o no. La idea es sencilla, muestre la variable aleatoria varias veces, (cada muestra independientemente de la muestra anterior para evitar el sesgo) y verifique si todos los resultados fueron 1. Si al menos algunos del resultado fue 0, sabemos de seguro que la variable aleatoria no es Constante 1 (en el contexto de prueba Sólovay-Strassen, el número es compuesto).

Es importante enfatizar, ya que Monte Carlo es un algoritmo aleatorio, que se dice que resuelve el problema si la probabilidad de devolver la respuesta incorrecta está por debajo del umbral (un pequeño número, llamaremos $ \ Epsilon $ ).

¿Qué pasa si todo resultado fuera 1? Existe la posibilidad de que sea la constante 1, pero también existe la posibilidad de que no teníamos suerte y todos los resultados fueron 1 cuando también puedan ser 0. Si la probabilidad de muestrear un 1 es $ P <1 $ , luego después de $ n $ muestras La probabilidad de conseguir el todo 1 es $ p_n= P ^ n $ . Tenga en cuenta que mientras $ n $ aumente $ p_n \ judowarrow 0 $ . Podemos especificar un umbral, digamos $ \ epsilon= 10 ^ {- 10} $ , de modo que si $ p_n < \ Epsilon $ (es decir, la probabilidad de tener un falso positivo es menor que $ \ epsilon $ ) estamos bien con ese resultado.

---

Ahora la respuesta a su pregunta. $ \ forall p <1, \ epsilon> 0 \ space \ existe n \ space p ^ n <\ epsilon $ . ¿Qué te dice esto exactamente?

Cualquiera que sea la probabilidad de éxito, por lo que es menos que $ 1 $ (por ejemplo, $ p= 0.99 $ o $ p= 0.01 $ o $ p= 0.5 $ ) y umbral $ \ Epsilon $ Existen un $ n $ de modo que si ejecutamos el experimento $ n $ veces (muestra $ n $ veces la variable aleatoria de forma independiente) Vamos a fallar con probabilidad en la mayoría de $ \ Epsilon $ . Así que Monte Carlo se puede aplicar para valores no degenerados de $ p $ , simplemente el número $ n $ de la muestra debe ajustarse para satisfacer el $ \ epsilon $ requisito de umbral.