Los métodos de Monte Carlo , o experimentos de Monte Carlo , son una clase amplia de algoritmos computacionales que se basan en muestreos aleatorios repetidos para obtener resultados numéricos. El concepto subyacente es utilizar la aleatoriedad para resolver problemas que podrían ser en principio deterministas . El nombre proviene del Casino de Montecarlo en Mónaco, donde el principal desarrollador del método, el físico Stanislaw Ulam , se inspiró en los hábitos de juego de su tío.
Los métodos de Monte Carlo se utilizan principalmente en tres clases de problemas distintos: optimización, integración numérica y generación de sorteos a partir de una distribución de probabilidad. También se pueden utilizar para modelar fenómenos con una incertidumbre significativa en los datos de entrada, como calcular el riesgo de falla de una planta de energía nuclear. Los métodos de Monte Carlo a menudo se implementan mediante simulaciones por computadora y pueden proporcionar soluciones aproximadas a problemas que de otro modo serían intratables o demasiado complejos para analizar matemáticamente.
Los métodos de Monte Carlo se utilizan ampliamente en diversos campos de la ciencia, la ingeniería y las matemáticas, como la física, la química, la biología, la estadística, la inteligencia artificial, las finanzas y la criptografía. También se han aplicado a las ciencias sociales, como la sociología, la psicología y las ciencias políticas. Los métodos de Montecarlo han sido reconocidos como una de las ideas más importantes e influyentes del siglo XX y han permitido muchos avances científicos y tecnológicos.
Los métodos de Monte Carlo también tienen algunas limitaciones y desafíos, como el equilibrio entre precisión y costo computacional, la maldición de la dimensionalidad, la confiabilidad de los generadores de números aleatorios y la verificación y validación de los resultados.
Los métodos de Monte Carlo varían, pero tienden a seguir un patrón particular:
Por ejemplo, consideremos un cuadrante (sector circular) inscrito en un cuadrado unitario . Dado que la razón de sus áreas es π/4 , el valor de π se puede aproximar utilizando el método de Monte Carlo: [1]
En este procedimiento el dominio de las entradas es el cuadrado que circunscribe el cuadrante. Se pueden generar entradas aleatorias esparciendo granos sobre el cuadrado y luego realizar un cálculo en cada entrada (probar si se encuentra dentro del cuadrante). La suma de los resultados produce nuestro resultado final, la aproximación de π .
Hay dos consideraciones importantes:
Los usos de los métodos de Monte Carlo requieren grandes cantidades de números aleatorios, y su uso se benefició enormemente de los generadores de números pseudoaleatorios , que son mucho más rápidos de usar que las tablas de números aleatorios que se habían utilizado anteriormente para el muestreo estadístico.
Los métodos de Monte Carlo se utilizan a menudo en problemas físicos y matemáticos y son más útiles cuando es difícil o imposible utilizar otros enfoques. Los métodos de Monte Carlo se utilizan principalmente en tres clases de problemas: [2] optimización , integración numérica y generación de sorteos a partir de una distribución de probabilidad .
En problemas relacionados con la física, los métodos de Monte Carlo son útiles para simular sistemas con muchos grados de libertad acoplados , como fluidos, materiales desordenados, sólidos fuertemente acoplados y estructuras celulares (ver modelo celular de Potts , sistemas de partículas que interactúan , procesos de McKean-Vlasov , modelos cinéticos de gases ).
Otros ejemplos incluyen fenómenos de modelado con incertidumbre significativa en los datos de entrada, como el cálculo del riesgo en los negocios y, en matemáticas, la evaluación de integrales definidas multidimensionales con condiciones de contorno complicadas . En su aplicación a problemas de ingeniería de sistemas (espacio, exploración petrolera , diseño de aeronaves, etc.), las predicciones de fallas, sobrecostos y cronogramas basadas en Monte Carlo son rutinariamente mejores que la intuición humana o los métodos alternativos "blandos". [3]
En principio, los métodos de Monte Carlo se pueden utilizar para resolver cualquier problema que tenga una interpretación probabilística. Según la ley de los grandes números , las integrales descritas por el valor esperado de alguna variable aleatoria se pueden aproximar tomando la media empírica ( también conocida como "media muestral") de muestras independientes de la variable. Cuando se parametriza la distribución de probabilidad de la variable, los matemáticos suelen utilizar un muestreador Monte Carlo de cadena de Markov (MCMC). [4] [5] [6] La idea central es diseñar un modelo de cadena de Markov juicioso con una distribución de probabilidad estacionaria prescrita . Es decir, en el límite, las muestras generadas por el método MCMC serán muestras de la distribución deseada (objetivo). [7] [8] Según el teorema ergódico , la distribución estacionaria se aproxima mediante las medidas empíricas de los estados aleatorios del muestreador MCMC.
En otros problemas, el objetivo es generar extracciones a partir de una secuencia de distribuciones de probabilidad que satisfagan una ecuación de evolución no lineal. Estos flujos de distribuciones de probabilidad siempre pueden interpretarse como las distribuciones de los estados aleatorios de un proceso de Markov cuyas probabilidades de transición dependen de las distribuciones de los estados aleatorios actuales (ver Procesos de McKean-Vlasov , ecuación de filtrado no lineal ). [9] [10] En otros casos, surge un flujo de distribuciones de probabilidad con un nivel creciente de complejidad de muestreo (modelos de espacios de trayectoria con un horizonte temporal creciente, medidas de Boltzmann-Gibbs asociadas con parámetros de temperatura decrecientes y muchos otros). Estos modelos también pueden verse como la evolución de la ley de los estados aleatorios de una cadena de Markov no lineal. [10] [11] Una forma natural de simular estos sofisticados procesos no lineales de Markov es muestrear múltiples copias del proceso, reemplazando en la ecuación de evolución las distribuciones desconocidas de los estados aleatorios por las medidas empíricas muestreadas . A diferencia de las metodologías tradicionales de Monte Carlo y MCMC, estas técnicas de partículas de campo medio se basan en muestras secuenciales que interactúan. La terminología del campo medio refleja el hecho de que cada una de las muestras ( también conocidas como partículas, individuos, caminantes, agentes, criaturas o fenotipos) interactúa con las medidas empíricas del proceso. Cuando el tamaño del sistema tiende al infinito, estas medidas empíricas aleatorias convergen a la distribución determinista de los estados aleatorios de la cadena de Markov no lineal, de modo que la interacción estadística entre partículas desaparece.
A pesar de su simplicidad conceptual y algorítmica, el costo computacional asociado con una simulación de Monte Carlo puede ser asombrosamente alto. En general, el método requiere muchas muestras para obtener una buena aproximación, lo que puede generar un tiempo de ejecución total arbitrariamente grande si el tiempo de procesamiento de una sola muestra es alto. [12] Aunque esto es una limitación severa en problemas muy complejos, la naturaleza vergonzosamente paralela del algoritmo permite reducir este gran costo (quizás a un nivel factible) a través de estrategias de computación paralela en procesadores locales, clusters, computación en la nube, GPU, FPGA, etc. [13] [14] [15] [16]
Antes de que se desarrollara el método Monte Carlo, las simulaciones probaban un problema determinista previamente comprendido y se utilizaba muestreo estadístico para estimar las incertidumbres en las simulaciones. Las simulaciones de Monte Carlo invierten este enfoque, resolviendo problemas deterministas utilizando metaheurísticas probabilísticas (ver recocido simulado ).
Se ideó una primera variante del método de Monte Carlo para resolver el problema de las agujas de Buffon , en el que π se puede estimar dejando caer agujas sobre un suelo hecho de tiras paralelas equidistantes. En la década de 1930, Enrico Fermi experimentó por primera vez con el método de Montecarlo mientras estudiaba la difusión de neutrones, pero no publicó este trabajo. [17]
A finales de la década de 1940, Stanislaw Ulam inventó la versión moderna del método Monte Carlo de la Cadena de Markov mientras trabajaba en proyectos de armas nucleares en el Laboratorio Nacional de Los Álamos . En 1946, los físicos de armas nucleares de Los Álamos estaban investigando la difusión de neutrones en el núcleo de un arma nuclear. [17] A pesar de tener la mayoría de los datos necesarios, como la distancia promedio que viajaría un neutrón en una sustancia antes de chocar con un núcleo atómico y cuánta energía era probable que emitiera el neutrón después de una colisión, los físicos de Los Álamos estaban incapaz de resolver el problema utilizando métodos matemáticos deterministas convencionales. Ulam propuso utilizar experimentos aleatorios. Él relata su inspiración de la siguiente manera:
Los primeros pensamientos e intentos que hice para practicar [el Método Monte Carlo] fueron sugeridos por una pregunta que se me ocurrió en 1946 mientras estaba convaleciente de una enfermedad y jugaba solitarios. La pregunta era ¿cuáles son las posibilidades de que un solitario Canfield dispuesto con 52 cartas tenga éxito? Después de pasar mucho tiempo tratando de estimarlos mediante cálculos combinatorios puros, me pregunté si un método más práctico que el "pensamiento abstracto" no sería exponerlo, digamos, cien veces y simplemente observar y contar el número de jugadas exitosas. Esto ya era posible prever con el comienzo de la nueva era de las computadoras rápidas, e inmediatamente pensé en los problemas de la difusión de neutrones y otras cuestiones de la física matemática y, más en general, en cómo cambiar los procesos descritos por ciertas ecuaciones diferenciales a una forma equivalente interpretable. como una sucesión de operaciones aleatorias. Más tarde [en 1946], le describí la idea a John von Neumann y comenzamos a planificar cálculos reales. [18]
Al ser secreto, el trabajo de von Neumann y Ulam requirió un nombre en clave. [19] Un colega de von Neumann y Ulam, Nicholas Metropolis , sugirió usar el nombre Monte Carlo , que se refiere al Casino Monte Carlo en Mónaco donde el tío de Ulam pedía prestado dinero a sus familiares para apostar. [17] Los métodos de Monte Carlo fueron fundamentales para las simulaciones necesarias para un mayor desarrollo de armas nucleares en la posguerra, incluido el diseño de la bomba H, aunque gravemente limitados por las herramientas computacionales de la época. Von Neumann, Nicholas Metropolis y otros programaron la computadora ENIAC para realizar los primeros cálculos Monte Carlo totalmente automatizados, de un núcleo de arma de fisión , en la primavera de 1948. [20] En la década de 1950 se utilizaron métodos Monte Carlo en Los Alamos para el desarrollo de la bomba de hidrógeno , y se popularizó en los campos de la física , la química física y la investigación de operaciones . La Rand Corporation y la Fuerza Aérea de EE. UU. fueron dos de las principales organizaciones responsables de financiar y difundir información sobre los métodos de Monte Carlo durante este tiempo, y comenzaron a encontrar una amplia aplicación en muchos campos diferentes.
La teoría de los métodos Monte Carlo de partículas de tipo campo medio más sofisticados ciertamente comenzó a mediados de la década de 1960, con el trabajo de Henry P. McKean Jr. sobre las interpretaciones de Markov de una clase de ecuaciones diferenciales parciales parabólicas no lineales que surgen en la mecánica de fluidos. [21] [22] Un artículo pionero anterior de Theodore E. Harris y Herman Kahn, publicado en 1951, utilizó métodos Monte Carlo de tipo genético de campo medio para estimar las energías de transmisión de partículas. [23] Las metodologías Monte Carlo de tipo genético de campo medio también se utilizan como algoritmos heurísticos de búsqueda natural (también conocidos como metaheurísticos ) en la computación evolutiva. Los orígenes de estas técnicas computacionales de campo medio se remontan a 1950 y 1954 con el trabajo de Alan Turing sobre máquinas de aprendizaje de selección de mutaciones de tipos genéticos [24] y los artículos de Nils Aall Barricelli en el Instituto de Estudios Avanzados de Princeton, Nueva York. Jersey . [25] [26]
Quantum Monte Carlo , y más específicamente los métodos de difusión Monte Carlo, también pueden interpretarse como una aproximación de Monte Carlo de partículas de campo medio de las integrales de trayectoria de Feynman - Kac . [27] [28] [29] [30] [31] [32] [33] Los orígenes de los métodos Quantum Monte Carlo a menudo se atribuyen a Enrico Fermi y Robert Richtmyer , quienes desarrollaron en 1948 una interpretación de partículas de campo medio de los neutrones. reacciones en cadena, [34] pero el primer algoritmo de partículas de tipo heurístico y genético (también conocido como métodos de Monte Carlo de Reconfiguración o Resampled) para estimar las energías del estado fundamental de sistemas cuánticos (en modelos de matriz reducida) se debe a Jack H. Hetherington en 1984. [33] En química molecular, el uso de metodologías genéticas de partículas similares a heurísticas (también conocidas como estrategias de poda y enriquecimiento) se remonta a 1955 con el trabajo fundamental de Marshall N. Rosenbluth y Arianna W. Rosenbluth . [35]
El uso de Sequential Monte Carlo en procesamiento avanzado de señales e inferencia bayesiana es más reciente. Fue en 1993 que Gordon et al. publicaron en su trabajo fundamental [36] la primera aplicación de un algoritmo de remuestreo de Monte Carlo en la inferencia estadística bayesiana. Los autores llamaron a su algoritmo "filtro de arranque" y demostraron que, en comparación con otros métodos de filtrado, su algoritmo de arranque no requiere ninguna suposición sobre ese espacio de estados o el ruido del sistema. Otro artículo pionero en este campo fue el de Genshiro Kitagawa, sobre un "filtro de Monte Carlo" relacionado, [37] y los de Pierre Del Moral [38] y Himilcon Carvalho, Pierre Del Moral, André Monin y Gérard Salut [39] sobre partículas . filtros publicados a mediados de la década de 1990. Los filtros de partículas también fueron desarrollados en el procesamiento de señales en 1989-1992 por P. Del Moral, JC Noyer, G. Rigal y G. Salut en el LAAS-CNRS en una serie de informes de investigación restringidos y clasificados con STCAN (Service Technique des Constructions). et Armes Navales), la empresa informática DIGILOG y el LAAS-CNRS (Laboratorio de Análisis y Arquitectura de Sistemas) sobre problemas de procesamiento de señales de radar/sonar y GPS. [40] [41] [42] [43] [44] [45] Estas metodologías Sequential Monte Carlo pueden interpretarse como un muestreador de aceptación-rechazo equipado con un mecanismo de reciclaje interactivo.
De 1950 a 1996, todas las publicaciones sobre metodologías de Monte Carlo secuencial, incluidos los métodos de Monte Carlo de poda y remuestreo introducidos en la física computacional y la química molecular, presentan algoritmos naturales y de tipo heurístico aplicados a diferentes situaciones sin una sola prueba de su consistencia, ni una discusión sobre el sesgo de las estimaciones y sobre algoritmos basados en árboles genealógicos y ancestrales. Los fundamentos matemáticos y el primer análisis riguroso de estos algoritmos de partículas fueron escritos por Pierre Del Moral en 1996. [38] [46]
Dan Crisan, Jessica Gaines y Terry Lyons, [47] [48] [49] y Dan Crisan, Pierre Del Moral y Terry Lyons también desarrollaron metodologías de partículas de tipo ramificado con diferentes tamaños de población a finales de la década de 1990. [50] P. Del Moral, A. Guionnet y L. Miclo describieron otros avances en este campo entre 1999 y 2001. [28] [51] [52]
No hay consenso sobre cómo debería definirse Montecarlo . Por ejemplo, Ripley [53] define la mayoría de los modelos probabilísticos como simulación estocástica , reservando Monte Carlo para la integración de Monte Carlo y las pruebas estadísticas de Monte Carlo. Sawilowsky [54] distingue entre una simulación , un método de Monte Carlo y una simulación de Monte Carlo: una simulación es una representación ficticia de la realidad, un método de Monte Carlo es una técnica que puede usarse para resolver un problema matemático o estadístico, y un método de Monte Carlo es una técnica que puede usarse para resolver un problema matemático o estadístico. La simulación Monte Carlo utiliza muestreos repetidos para obtener las propiedades estadísticas de algún fenómeno (o comportamiento).
Aquí están los ejemplos:
Kalos y Whitlock [55] señalan que tales distinciones no siempre son fáciles de mantener. Por ejemplo, la emisión de radiación de los átomos es un proceso estocástico natural. Puede simularse directamente o su comportamiento promedio puede describirse mediante ecuaciones estocásticas que a su vez pueden resolverse utilizando métodos de Monte Carlo. "De hecho, el mismo código informático puede considerarse simultáneamente como una 'simulación natural' o como una solución de ecuaciones mediante muestreo natural."
La convergencia de la simulación de Monte Carlo se puede comprobar con el estadístico de Gelman-Rubin .
La idea principal detrás de este método es que los resultados se calculan basándose en muestreos aleatorios repetidos y análisis estadístico. La simulación de Monte Carlo son, de hecho, experimentos aleatorios, en el caso de que los resultados de estos experimentos no sean bien conocidos. Las simulaciones de Monte Carlo suelen caracterizarse por muchos parámetros desconocidos, muchos de los cuales son difíciles de obtener experimentalmente. [56] Los métodos de simulación de Monte Carlo no siempre requieren números verdaderamente aleatorios para ser útiles (aunque, para algunas aplicaciones como las pruebas de primalidad , la imprevisibilidad es vital). [57] Muchas de las técnicas más útiles utilizan secuencias pseudoaleatorias deterministas , lo que facilita probar y volver a ejecutar simulaciones. La única cualidad normalmente necesaria para realizar buenas simulaciones es que la secuencia pseudoaleatoria parezca "suficientemente aleatoria" en cierto sentido.
Lo que esto significa depende de la aplicación, pero normalmente deben pasar una serie de pruebas estadísticas. Probar que los números están distribuidos uniformemente o siguen otra distribución deseada cuando se considera un número suficientemente grande de elementos de la secuencia es una de las más simples y comunes. Las correlaciones débiles entre muestras sucesivas también suelen ser deseables/necesarias.
Sawilowsky enumera las características de una simulación Monte Carlo de alta calidad: [54]
Los algoritmos de muestreo de números pseudoaleatorios se utilizan para transformar números pseudoaleatorios distribuidos uniformemente en números que se distribuyen de acuerdo con una distribución de probabilidad determinada .
A menudo se utilizan secuencias de baja discrepancia en lugar de muestreo aleatorio de un espacio, ya que garantizan una cobertura uniforme y normalmente tienen un orden de convergencia más rápido que las simulaciones de Monte Carlo que utilizan secuencias aleatorias o pseudoaleatorias. Los métodos basados en su uso se denominan métodos cuasi-Montecarlo .
En un esfuerzo por evaluar el impacto de la calidad de los números aleatorios en los resultados de la simulación de Monte Carlo, los investigadores astrofísicos probaron números pseudoaleatorios criptográficamente seguros generados mediante el conjunto de instrucciones RDRAND de Intel , en comparación con los derivados de algoritmos, como el Mersenne Twister , en simulaciones de radio de Monte Carlo. llamaradas de enanas marrones . No se encontraron diferencias estadísticamente significativas entre los modelos generados con generadores de números pseudoaleatorios típicos y RDRAND para los ensayos que consistieron en la generación de 10 7 números aleatorios. [58]
Hay formas de utilizar probabilidades que definitivamente no son simulaciones de Monte Carlo; por ejemplo, modelos deterministas que utilizan estimaciones de un solo punto. A cada variable incierta dentro de un modelo se le asigna una estimación de "mejor estimación". Se eligen escenarios (como el mejor, el peor o el más probable) para cada variable de entrada y se registran los resultados. [59]
Por el contrario, las simulaciones de Monte Carlo toman muestras de una distribución de probabilidad para cada variable para producir cientos o miles de resultados posibles. Los resultados se analizan para obtener probabilidades de que ocurran diferentes resultados. [60] Por ejemplo, una comparación de un modelo de construcción de costos en una hoja de cálculo ejecutado utilizando escenarios tradicionales de "qué pasaría si" y luego ejecutando la comparación nuevamente con simulación de Monte Carlo y distribuciones de probabilidad triangulares muestra que el análisis de Monte Carlo tiene un rango más estrecho que el " análisis "qué pasaría si". [ ejemplo necesario ] Esto se debe a que el análisis "qué pasaría si" da igual peso a todos los escenarios (ver cuantificación de la incertidumbre en las finanzas corporativas ), mientras que el método de Monte Carlo apenas toma muestras en las regiones de muy baja probabilidad. Las muestras en dichas regiones se denominan "eventos raros".
Los métodos de Monte Carlo son especialmente útiles para simular fenómenos con incertidumbre significativa en entradas y sistemas con muchos grados de libertad acoplados . Las áreas de aplicación incluyen:
Los métodos de Monte Carlo son muy importantes en física computacional , química física y campos aplicados relacionados, y tienen diversas aplicaciones, desde complicados cálculos de cromodinámica cuántica hasta el diseño de escudos térmicos y formas aerodinámicas , así como en el modelado del transporte de radiación para cálculos de dosimetría de radiación. [61] [62] [63] En física estadística , el modelado molecular de Monte Carlo es una alternativa a la dinámica molecular computacional , y los métodos de Monte Carlo se utilizan para calcular teorías de campos estadísticos de sistemas simples de partículas y polímeros. [35] [64] Los métodos cuánticos de Monte Carlo resuelven el problema de muchos cuerpos para los sistemas cuánticos. [9] [10] [27] En la ciencia de los materiales de radiación , la aproximación de colisión binaria para simular la implantación de iones generalmente se basa en un enfoque de Monte Carlo para seleccionar el siguiente átomo en colisión. [65] En física de partículas experimental , los métodos de Monte Carlo se utilizan para diseñar detectores , comprender su comportamiento y comparar datos experimentales con la teoría. En astrofísica , se utilizan de maneras tan diversas como para modelar tanto la evolución de las galaxias [66] como la transmisión de radiación de microondas a través de una superficie planetaria rugosa. [67] Los métodos de Monte Carlo también se utilizan en los modelos de conjunto que forman la base de la predicción meteorológica moderna .
Los métodos de Monte Carlo se utilizan ampliamente en ingeniería para análisis de sensibilidad y análisis probabilístico cuantitativo en el diseño de procesos . La necesidad surge del comportamiento interactivo, colineal y no lineal de las simulaciones de procesos típicas. Por ejemplo,
El Panel Intergubernamental sobre Cambio Climático se basa en los métodos de Monte Carlo en el análisis de la función de densidad de probabilidad del forzamiento radiativo . [71]
Los métodos de Monte Carlo se utilizan en diversos campos de la biología computacional , por ejemplo para la inferencia bayesiana en filogenia , o para estudiar sistemas biológicos como genomas, proteínas [72] o membranas. [73] Los sistemas se pueden estudiar en los marcos de grano grueso o ab initio dependiendo de la precisión deseada. Las simulaciones por computadora permiten monitorear el entorno local de una molécula en particular para ver si, por ejemplo, está ocurriendo alguna reacción química . En los casos en los que no sea factible realizar un experimento físico, se pueden realizar experimentos mentales (por ejemplo: romper enlaces, introducir impurezas en sitios específicos, cambiar la estructura local/global o introducir campos externos).
El trazado de trayectoria , en ocasiones denominado trazado de rayos Monte Carlo, representa una escena 3D trazando aleatoriamente muestras de posibles trayectorias de luz. El muestreo repetido de cualquier píxel determinado eventualmente hará que el promedio de las muestras converja en la solución correcta de la ecuación de renderizado , lo que lo convierte en uno de los métodos de renderizado de gráficos 3D físicamente más precisos que existen.
Sawilowsky estableció los estándares para los experimentos de Monte Carlo en estadística. [74] En la estadística aplicada, los métodos de Monte Carlo pueden utilizarse para al menos cuatro propósitos:
Los métodos de Monte Carlo también son un compromiso entre las pruebas de aleatorización aproximada y de permutación. Una prueba de aleatorización aproximada se basa en un subconjunto específico de todas las permutaciones (lo que implica una limpieza potencialmente enorme de las permutaciones que se han considerado). El enfoque de Monte Carlo se basa en un número específico de permutaciones extraídas al azar (intercambiando una pequeña pérdida de precisión si una permutación se extrae dos veces, o con más frecuencia, por la eficiencia de no tener que rastrear qué permutaciones ya han sido seleccionadas).
Los métodos de Monte Carlo se han convertido en una técnica llamada búsqueda de árbol de Monte-Carlo que es útil para buscar el mejor movimiento en un juego. Los posibles movimientos se organizan en un árbol de búsqueda y se utilizan muchas simulaciones aleatorias para estimar el potencial a largo plazo de cada movimiento. Un simulador de caja negra representa los movimientos del oponente. [78]
El método de búsqueda de árboles de Monte Carlo (MCTS) tiene cuatro pasos: [79]
El efecto neto, en el transcurso de muchos juegos simulados, es que el valor de un nodo que representa un movimiento aumentará o disminuirá, con suerte correspondiente a si ese nodo representa o no un buen movimiento.
Monte Carlo Tree Search se ha utilizado con éxito para jugar juegos como Go , [80] Tantrix , [81] Battleship , [82] Havannah , [83] y Arimaa . [84]
Los métodos de Monte Carlo también son eficientes para resolver ecuaciones diferenciales integrales acopladas de campos de radiación y transporte de energía y, por lo tanto, estos métodos se han utilizado en cálculos de iluminación global que producen imágenes fotorrealistas de modelos virtuales 3D, con aplicaciones en videojuegos , arquitectura y diseño. , películas generadas por computadora y efectos especiales cinematográficos. [85]
La Guardia Costera de EE. UU. utiliza métodos Monte Carlo dentro de su software de modelado por computadora SAROPS para calcular las ubicaciones probables de los buques durante las operaciones de búsqueda y rescate . Cada simulación puede generar hasta diez mil puntos de datos que se distribuyen aleatoriamente en función de las variables proporcionadas. [86] Luego se generan patrones de búsqueda basados en extrapolaciones de estos datos para optimizar la probabilidad de contención (POC) y la probabilidad de detección (POD), que juntas equivaldrán a una probabilidad general de éxito (POS). En última instancia, esto sirve como una aplicación práctica de la distribución de probabilidad para proporcionar el método de rescate más rápido y conveniente, salvando vidas y recursos. [87]
La simulación Monte Carlo se utiliza comúnmente para evaluar el riesgo y la incertidumbre que afectarían el resultado de diferentes opciones de decisión. La simulación Monte Carlo permite al analista de riesgos empresariales incorporar los efectos totales de la incertidumbre en variables como el volumen de ventas, los precios de las materias primas y de la mano de obra, los tipos de interés y de cambio, así como el efecto de distintos eventos de riesgo como la cancelación de un contrato o el cambio de una ley tributaria.
Los métodos de Monte Carlo en finanzas se utilizan a menudo para evaluar inversiones en proyectos a nivel de unidad de negocio o corporativa, u otras valoraciones financieras. Se pueden utilizar para modelar cronogramas de proyectos , donde las simulaciones agregan estimaciones para las duraciones del peor de los casos, el mejor de los casos y la más probable para cada tarea para determinar los resultados del proyecto general. [88] Los métodos de Monte Carlo también se utilizan en la fijación de precios de opciones y en el análisis del riesgo de incumplimiento. [89] [90] Además, se pueden utilizar para estimar el impacto financiero de las intervenciones médicas. [91]
Se utilizó un enfoque Monte Carlo para evaluar el valor potencial de un programa propuesto para ayudar a las peticionarias de Wisconsin a tener éxito en sus solicitudes de órdenes de restricción por acoso y abuso doméstico . Se propuso ayudar a las mujeres a tener éxito en sus peticiones brindándoles una mayor defensa, reduciendo así potencialmente el riesgo de violación y agresión física . Sin embargo, había muchas variables en juego que no podían estimarse perfectamente, incluida la efectividad de las órdenes de restricción, la tasa de éxito de los peticionarios con y sin defensa, y muchas otras. El estudio realizó pruebas que variaron estas variables para obtener una estimación general del nivel de éxito del programa propuesto en su conjunto. [92]
El enfoque de Monte Carlo también se utilizó para simular el número de publicaciones de libros según el género del libro en Malasia. La simulación de Monte Carlo utilizó datos de publicación de libros nacionales publicados anteriormente y el precio del libro según el género del libro en el mercado local. Los resultados de Monte Carlo se utilizaron para determinar qué tipo de género de libro les gusta a los malasios y se utilizaron para comparar las publicaciones de libros entre Malasia y Japón . [93]
Nassim Nicholas Taleb escribe sobre los generadores de Montecarlo en su libro de 2001 Fooled by Randomness como un ejemplo real de la prueba de Turing inversa : un ser humano puede ser declarado poco inteligente si su escritura no puede diferenciarse de la generada.
En general, los métodos de Monte Carlo se utilizan en matemáticas para resolver diversos problemas generando números aleatorios adecuados (ver también Generación de números aleatorios ) y observando aquella fracción de los números que obedece a alguna propiedad o propiedades. El método es útil para obtener soluciones numéricas a problemas demasiado complicados para resolverlos analíticamente. La aplicación más común del método Monte Carlo es la integración de Monte Carlo.
Los algoritmos de integración numérica determinista funcionan bien en un número pequeño de dimensiones, pero encuentran dos problemas cuando las funciones tienen muchas variables. Primero, el número de evaluaciones de funciones necesarias aumenta rápidamente con el número de dimensiones. Por ejemplo, si 10 evaluaciones proporcionan una precisión adecuada en una dimensión, entonces se necesitan 10.100 puntos para 100 dimensiones, demasiados para calcularlos. Esto se llama la maldición de la dimensionalidad . En segundo lugar, el límite de una región multidimensional puede ser muy complicado, por lo que puede no ser factible reducir el problema a una integral iterada . [94] 100 dimensiones no es nada inusual, ya que en muchos problemas físicos, una "dimensión" equivale a un grado de libertad .
Los métodos de Monte Carlo proporcionan una salida a este aumento exponencial del tiempo de cálculo. Siempre que la función en cuestión se comporte razonablemente bien , se puede estimar seleccionando aleatoriamente puntos en un espacio de 100 dimensiones y tomando algún tipo de promedio de los valores de la función en estos puntos. Según el teorema del límite central , este método muestra convergencia, es decir, cuadriplicar el número de puntos muestreados reduce a la mitad el error, independientemente del número de dimensiones. [94]
Un refinamiento de este método, conocido como muestreo de importancia en estadística, implica muestrear los puntos al azar, pero con mayor frecuencia cuando el integrando es grande. Para hacer esto precisamente, habría que conocer ya la integral, pero se puede aproximar la integral mediante una integral de una función similar o utilizar rutinas adaptativas como el muestreo estratificado , el muestreo estratificado recursivo , el muestreo paraguas adaptativo [95] [96] o el Algoritmo VEGAS .
Un enfoque similar, el método cuasi-Monte Carlo , utiliza secuencias de baja discrepancia . Estas secuencias "llenan" mejor el área y toman muestras de los puntos más importantes con más frecuencia, por lo que los métodos cuasi-Monte Carlo a menudo pueden converger en la integral más rápidamente.
Otra clase de métodos para muestrear puntos en un volumen es simular paseos aleatorios sobre él ( cadena de Markov Monte Carlo ). Dichos métodos incluyen el algoritmo Metropolis-Hastings , el muestreo de Gibbs , el algoritmo de Wang y Landau y metodologías MCMC de tipo interactivo, como los muestreadores secuenciales de Monte Carlo . [97]
Otra aplicación poderosa y muy popular para números aleatorios en simulación numérica es la optimización numérica . El problema es minimizar (o maximizar) funciones de algún vector que suele tener muchas dimensiones. Muchos problemas pueden formularse de esta manera: por ejemplo, se podría considerar que un programa de ajedrez por computadora intenta encontrar el conjunto de, digamos, 10 movimientos que produce la mejor función de evaluación al final. En el problema del viajante el objetivo es minimizar la distancia recorrida. También existen aplicaciones al diseño de ingeniería, como la optimización del diseño multidisciplinario . Se ha aplicado con modelos cuasi unidimensionales para resolver problemas de dinámica de partículas explorando eficientemente un gran espacio de configuración. La referencia [98] es una revisión exhaustiva de muchas cuestiones relacionadas con la simulación y la optimización.
El problema del viajante es lo que se llama un problema de optimización convencional. Es decir, se conocen con certeza todos los hechos (distancias entre cada punto de destino) necesarios para determinar el camino óptimo a seguir y el objetivo es analizar las posibles opciones de viaje para encontrar el que tenga la menor distancia total. Si el objetivo en lugar de minimizar la distancia total recorrida para visitar cada destino deseado sino minimizar el tiempo total necesario para llegar a cada destino, esto va más allá de la optimización convencional ya que el tiempo de viaje es inherentemente incierto (embotellamientos, hora del día, etc.) .). Como resultado, para determinar el camino óptimo se requiere una simulación diferente: optimización para comprender primero el rango de tiempos potenciales que podría llevar ir de un punto a otro (representado por una distribución de probabilidad en este caso en lugar de una distancia específica) y luego optimice las decisiones de viaje para identificar el mejor camino a seguir teniendo en cuenta esa incertidumbre.
La formulación probabilística de problemas inversos conduce a la definición de una distribución de probabilidad en el espacio modelo. Esta distribución de probabilidad combina información previa con información nueva obtenida midiendo algunos parámetros observables (datos). Como, en el caso general, la teoría que vincula los datos con los parámetros del modelo no es lineal, la probabilidad posterior en el espacio del modelo puede no ser fácil de describir (puede ser multimodal, algunos momentos pueden no estar definidos, etc.).
Cuando se analiza un problema inverso, normalmente no es suficiente obtener un modelo de máxima verosimilitud, ya que normalmente se desea información sobre el poder de resolución de los datos. En el caso general se modelan muchos parámetros y una inspección de las densidades de probabilidad marginal de interés puede resultar poco práctica o incluso inútil. Pero es posible generar pseudoaleatoriamente una gran colección de modelos de acuerdo con la distribución de probabilidad posterior y analizar y mostrar los modelos de tal manera que se transmita al espectador información sobre las probabilidades relativas de las propiedades del modelo. Esto se puede lograr mediante un método de Monte Carlo eficiente, incluso en los casos en que no se dispone de una fórmula explícita para la distribución a priori .
El método de muestreo de importancia más conocido, el algoritmo Metropolis, puede generalizarse, lo que proporciona un método que permite el análisis de problemas inversos (posiblemente altamente no lineales) con información compleja a priori y datos con una distribución de ruido arbitraria. [99] [100]
McCracken dirigió una exposición popular del Método Montecarlo. [101] La filosofía general del método fue discutida por Elishakoff [102] y Grüne-Yanoff y Weirich. [103]
Monografías sobre estadística y probabilidad aplicada.
Serie: Probabilidad y Aplicaciones
Informe desclasificado Archivo Los Alamos