¿Son todos los métodos de simulación alguna forma de Monte Carlo?

35

¿Existe un método de simulación que no sea Monte Carlo? Todos los métodos de simulación implican la sustitución de números aleatorios en la función para encontrar un rango de valores para la función. Entonces, ¿todos los métodos de simulación son esencialmente métodos de Monte Carlo?

Víctor
fuente
2
Creo que "Stan" era solo el primer nombre de Ulam, no el apellido de nadie más.
Nick Cox
Stan es la abreviatura de Stanislas , de hecho. Es por eso que Andrew Gelman eligió STAN para su nuevo lenguaje de simulación.
Xi'an
Dado un pequeño problema, quizás marginal, trivial, combinacional, ¿una búsqueda exhaustiva seguiría siendo "Monte Carlo"?
Nick T
3
Lo que recuerdo de mi conferencia sobre algoritmos aleatorizados es que los métodos de Monte Carlo tienen resultados estocásticos con tiempos de ejecución conocidos, en contraste con los métodos de Las Vegas que tienen tiempos de ejecución estocásticos pero resultados correctos. No hay referencia para esto, excepto un guión escrito a mano de cinco años en mi cajón. Editar: Las páginas de wikipedia sobre monte carlo y las vegas parecen estar de acuerdo con esto.
bayerj
Una búsqueda exhaustiva probablemente sería un cálculo de fuerza bruta. Los métodos de Monte Carlo se extraen de un espacio muestral. Esta muestra suele ser un pequeño subconjunto del universo de resultados, lo que hace que el análisis estadístico sea manejable.
Alex Reynolds

Respuestas:

41

Hay simulaciones que no son Monte Carlo. Básicamente, todos los métodos de Monte Carlo usan la ley (débil) de grandes números: la media converge a su expectativa.

Luego están los métodos Cuasi Monte Carlo. Estos se simulan con un compromiso de números aleatorios y cuadrículas igualmente espaciadas para producir una convergencia más rápida.

Las simulaciones que no son Monte Carlo son, por ejemplo utilizado en dinámica de fluidos computacional. Es fácil modelar la dinámica de fluidos en una "escala micro" de porciones individuales del fluido. Estas porciones tienen una velocidad inicial, la presión y el tamaño y se ven afectados por las fuerzas de las porciones vecinas o por cuerpos sólidos. Simulaciones calcular todo el comportamiento del fluido mediante el cálculo de todas las porciones y su interacción. Hacer esto de manera eficiente hace que esta ciencia. No se necesitan allí números aleatorios.

En meteorología o el clima de investigación, las cosas se hacen de manera similar. Pero ahora, los valores iniciales no son exactamente conocidos: Usted sólo tiene los datos meteorológicos en algunos puntos en los que se han medido. Una gran cantidad de datos tienen que ser adivinado.

Como estos problemas complicados a menudo no son continuos en sus datos de entrada, ejecuta las simulaciones con diferentes conjeturas. El resultado final será elegido entre los resultados más frecuentes. Así es como en principio se simulan algunas predicciones meteorológicas.

Horst Grünbusch
fuente
55
Una ligera corrección: las simulaciones monte-carlo pueden usar cálculos no aleatorios. Es válido llamar a una simulación "monte-carlo" si varía las condiciones iniciales, y luego aplica cálculos no aleatorios a partir de ahí. Muchas situaciones de CFD requieren monte-carlo porque las condiciones de contorno están definidas estadísticamente.
Cort Ammon - Restablece a Mónica el
14

El método Monte Carlo fue el primer enfoque para utilizar la simulación por computadora para problemas estadísticos. Fue desarrollado por el equipo John von Neumann, Stanisław Ulam y Nicholas Metropolis de los laboratorios de Los Alamos que estaban trabajando en el proyecto de Manhattan durante la Segunda Guerra Mundial. Fue descrito por primera vez en 1949 por Metropolis & Ulam , y fue la primera vez que el nombre apareció impreso. Fue posible porque los científicos que lo descubrieron también pudieron usar una de las primeras computadoras en las que estaban trabajando. En su trabajo, utilizaron los métodos de Monte Carlo para simular problemas físicos, y la idea era que se pudiera simular un problema complicado al muestrear algunos ejemplos de este proceso. Hay varios artículos interesantes sobre la historia de Montecarlo, por ejemploMetrópolis o algo más reciente, por ejemplo, de Robert y Casella .

Entonces "Monte Carlo" fue el nombre del primer método descrito con el propósito de simulación por computadora para resolver problemas estadísticos. Luego, el nombre se convirtió en un nombre general para toda una familia de métodos de simulación y se usa comúnmente de esta manera.

Existen métodos de simulación que no se consideran Monte Carlo , sin embargo, aunque Monte Carlo fue el primer uso de la simulación por computadora, es común que la "simulación por computadora" y "Monte Carlo" se usen indistintamente.

Hay diferentes definiciones de lo que es "simulación", es decir

Diccionario Merriam-Webster :

3 a: la representación imitativa del funcionamiento de un sistema o proceso mediante el funcionamiento de otro b: examen de un problema a menudo no sujeto a experimentación directa mediante un dispositivo de simulación

Diccionario Cambridge :

hacer o hacer algo que se comporte o parezca algo real pero que no sea real

Wikipedia :

imitación de la operación de un proceso o sistema del mundo real a lo largo del tiempo

Lo que la simulación necesita para funcionar es la capacidad de imitar algún sistema o proceso. Esto no necesita ninguna aleatoriedad involucrada (como con Monte Carlo), sin embargo, si se prueban todas las posibilidades, entonces el procedimiento es más bien una búsqueda exhaustiva o, en general, un problema de optimización . Si el elemento aleatorio está involucrado y se usa una computadora para ejecutar una simulación de algún modelo, entonces esta simulación se asemeja al espíritu del método Monte Carlo inicial (por ejemplo, Metropolis y Ulam, 1949). El elemento aleatorio como parte crucial de la simulación es mencionado, por ejemplo, por Ross (2006, Simulación. Elsevier). Sin embargo, la respuesta a la pregunta depende en gran medida de la definición de simulación que asuma. Por ejemplo, si supone que los algoritmos deterministas que utilizan la optimización o la búsqueda exhaustiva son, de hecho, simulaciones, entonces debemos considerar una gran variedad de algoritmos para ser simulaciones y esto hace que la definición de simulación per se sea muy borrosa.

Literalmente, cada procedimiento estadístico emplea algún modelo o aproximación de la realidad, que se "prueba" y evalúa. Esto es consistente con las definiciones de simulación del diccionario. Sin embargo, no consideramos que todas las estadísticas estén basadas en simulaciones. La pregunta y la discusión parecen surgir de la falta de la definición precisa de "simulación". Monte Carlo parece ser un ejemplo arquetípico (y primer) de simulación, sin embargo, si consideramos una definición muy general de simulación, muchos métodos que no son de Monte Carlo caen en la definición. Por lo tanto, existen simulaciones que no son de Monte Carlo, pero todos los métodos claramente basados ​​en la simulación se asemejan al espíritu de Monte Carlo, se relacionan con él de alguna manera o se inspiraron en él. Esa es la razón por la cual "Monte Carlo" se usa a menudo como sinónimo de "simulación".

Tim
fuente
3
Creo que "Stan" era solo el primer nombre de Ulam, no el apellido de nadie más.
Nick Cox
1
Stan es la abreviatura de Stanislas , de hecho. Es por eso que Andrew Gelman eligió STAN para su nuevo lenguaje de simulación.
Xi'an
Dado un pequeño problema, quizás marginal, trivial, combinacional, ¿una búsqueda exhaustiva seguiría siendo "Monte Carlo"?
Nick T
66
No lo entiendo: ¿cómo responde esto a la pregunta?
o0 '.
1
@ Xi'an es Stanisław escrito con "Ł" (leído como "woo" en inglés).
Tim
13

Todos los métodos de simulación implican la sustitución de números aleatorios en la función para encontrar un rango de valores para la función.

Nunca he oído hablar de esa definición de simulación. Por ejemplo, los artículos de Wikipedia sobre simulación y simulaciones por computadora mencionan términos como aleatorio y estocástico solo brevemente.

Un ejemplo simple de una simulación que no involucra ninguna aleatoriedad y, por lo tanto, claramente no es una simulación de Monte Carlo sería el siguiente:

Quiero simular el comportamiento de un péndulo simple y hacer algunas suposiciones simplificadoras (cordón sin masa, masa puntual, sin fricción, sin fuerzas externas como la fuerza de Coriolis). Luego obtengo un péndulo matemático y puedo escribir ecuaciones diferenciales que describan su movimiento. Entonces puedo usar algún solucionador para ecuaciones diferenciales como un método Runge-Kutta para simular su trayectoria para condiciones iniciales dadas. (Teóricamente, también puedo argumentar que no necesito considerar otras condiciones iniciales).

De esta manera obtengo una simulación bastante buena de un péndulo real sin usar nunca un número aleatorio. Por lo tanto, esta no es una simulación de Monte-Carlo.

En otro ejemplo, considere el mapa logístico , que es un modelo de población simple sin ninguna aleatoriedad.

Wrzlprmft
fuente
7

No. La simulación de una partícula bajo una fuerza se puede hacer usando Runge-Kutta u otro algoritmo determinista, que no es Monte Carlo.

Monte Carlo se usa para calcular integrales (puede llamarlo una simulación, pero al final solo calcula una aproximación numérica de un estimador). Nuevamente, podría usar un método determinista para hacer eso (por ejemplo, regla trapezoidal).

En términos generales, puede separar algoritmos para calcular integrales en deterministas y no deterministas. Monte Carlo es un método no determinista. Cuasi-Monte Carlo es otro. La regla trapezoidal es un algoritmo determinista.

Jorge Leitao
fuente
4

Permítanme probar una explicación simplificada. Un modelo de "qué pasaría si" es una simulación (determinista). Digamos que tiene un sistema complejo, como una planta de procesamiento de widgets. Desea poder estimar algunos parámetros de rendimiento, por ejemplo, el costo. Construye un modelo matemático de la planta y luego selecciona varios supuestos para factores específicos en el modelo, como qué tan rápido se mueven los widgets a través de diferentes operaciones, o qué porcentajes fluyen en varias direcciones, o cuántos widgets procesará. El modelo es una simulación de la planta y cada conjunto de supuestos le proporciona una estimación de ese parámetro de rendimiento.

Ahora introduce incertidumbre. No sabe cuál será la demanda de widgets el próximo mes, pero necesita estimar el costo. Entonces, en lugar de decir que la demanda será de 1,000 widgets, estima una distribución de probabilidad para la demanda. Luego, muestra aleatoriamente los valores de demanda de esa distribución y los utiliza para su suposición. Mientras lo hace, también puede usar distribuciones de probabilidad para otros supuestos. Utiliza el modelo una y otra vez, conectando supuestos muestreados de las diversas distribuciones de probabilidad. El resultado será una distribución de estimaciones de costos. Ese es el aspecto de Monte Carlo.

Monte Carlo es una "característica" o "motor" que se depositó en la superficie de un modelo de simulación. En lugar de simular con un único conjunto de supuestos para una sola estimación, se realiza una colección de simulaciones utilizando supuestos seleccionados al azar.

fijador1234
fuente
2

En la teoría de juegos, sobre todo, acerca de que el uso aleatoriedad en las simulaciones se llaman técnicas de Monte Carlo. Normalmente se utiliza como parte de Monte Carlo árbol de búsqueda (MCTS) en los programas modernos.

(La pregunta original no hizo una distinción entre " Monte Carlo algoritmo " y " método de Monte Carlo ", lo que puede explicar el desacuerdo sobre algunas de las respuestas aquí.)

Por ejemplo, en el juego de Go (y todos los demás juegos soy consciente de que el uso de MCTS), las simulaciones se llaman playouts. playouts azar utilizan el conjunto de reglas más pelado. playouts de luz son ya sea un sinónimo de playouts al azar o filtrar los unos malos mueve fácilmente detectados. playouts pesados ​​utilizan más heurística de filtrar muchos más movimientos. (Por cierto, la reproducción siempre va al final de la partida, por lo que cada emisión tiene más o menos la misma cantidad de tiempo.) Pero todo se refiere como simulaciones de "Monte Carlo".

Darren Cook
fuente