Método Montecarlo(Métodos de Monte Carlo, MMC) es el nombre general de un grupo de métodos numéricos basados ​​en la obtención de un gran número de realizaciones de un proceso estocástico (aleatorio), que se forma de tal manera que sus características probabilísticas coinciden con valores similares. del problema que se está resolviendo. Se utiliza para resolver problemas en diversos campos de la física, química, matemáticas, economía, optimización, teoría de control, etc.

Historia

Algoritmo de Buffon para determinar Pi

Las variables aleatorias se han utilizado para resolver diversos problemas aplicados durante bastante tiempo. Un ejemplo es el método para determinar el número Pi, propuesto por Buffon en 1777. La esencia del método era lanzar una aguja de largo l sobre un plano dibujado por líneas paralelas ubicadas a una distancia r unos de otros (ver Fig. 1).

Foto 1. El método de Buffon.

Probabilidad (como puede verse en el contexto adicional, no estamos hablando de probabilidad, sino de la expectativa matemática del número de intersecciones en un experimento; esto se convierte en probabilidad solo si r>l) que el segmento interseque a la recta está relacionado con el número Pi:

, Dónde

A- la distancia desde el inicio de la aguja hasta la línea recta más cercana;

θ es el ángulo de la aguja con respecto a las líneas rectas.

Es fácil tomar esta integral: (siempre que r>l), por lo tanto, al contar la proporción de segmentos que cruzan líneas, podemos determinar aproximadamente este número. A medida que aumente el número de intentos, aumentará la precisión del resultado obtenido.

En 1864, el Capitán Fox, mientras se recuperaba de una lesión, para entretenerse de alguna manera, llevó a cabo un experimento lanzando una aguja. Los resultados se presentan en la siguiente tabla:

	Número de lanzamientos	Número de intersecciones	Longitud de la aguja	Distancia entre líneas	Rotación	valor pi
Primer intento					ausente
Segundo intento					presente
Tercer intento					presente

Comentarios:

Se utilizó la rotación del plano (y, como muestran los resultados, con éxito) para reducir el error sistemático.

En el tercer intento, la longitud de la aguja fue mayor que la distancia entre las líneas, lo que permitió, sin aumentar el número de lanzamientos, aumentar efectivamente el número de eventos y mejorar la precisión.

Relación entre procesos estocásticos y ecuaciones diferenciales.

La creación del aparato matemático de métodos estocásticos se inició a finales del siglo XIX. En 1899, Lord Rayleigh demostró que un paseo aleatorio unidimensional sobre una red infinita podría dar una solución aproximada a una ecuación diferencial parabólica. Andrei Kolmogorov en 1931 dio un gran impulso al desarrollo de enfoques estocásticos para resolver diversos problemas matemáticos, ya que pudo demostrar que las cadenas de Markov están relacionadas con ciertas ecuaciones integrodiferenciales. En 1933, Ivan Petrovsky demostró que el paseo aleatorio que forma una cadena de Markov está asintóticamente relacionado con la solución de una ecuación diferencial parcial elíptica. Después de estos descubrimientos, quedó claro que los procesos estocásticos pueden describirse mediante ecuaciones diferenciales y, en consecuencia, estudiarse utilizando métodos matemáticos bien desarrollados para resolver estas ecuaciones en ese momento.

Nacimiento del método Montecarlo en Los Álamos

Primero, Enrico Fermi en la década de 1930 en Italia, y luego John von Neumann Stanislaw Ulam en la década de 1940 en Los Álamos, sugirieron que era posible utilizar la conexión entre procesos estocásticos y ecuaciones diferenciales “en la dirección opuesta”. Propusieron utilizar un enfoque estocástico para aproximar integrales multidimensionales en las ecuaciones de transporte que surgieron en relación con el problema del movimiento de neutrones en un medio visotrópico.

La idea fue desarrollada por Ulam, quien, irónicamente, al igual que Fox, estaba luchando contra la inactividad forzada mientras convalecía de una enfermedad y, mientras jugaba al solitario, se preguntaba cuál era la probabilidad de que el juego de solitario "funcionara". Se le ocurrió la idea de que, en lugar de utilizar las consideraciones habituales de la combinatoria para este tipo de problemas, podría simplemente realizar el "experimento" un gran número de veces y, así, contando el número de resultados exitosos, estimar su probabilidad. También propuso utilizar computadoras para los cálculos de Montecarlo.

La llegada de las primeras computadoras electrónicas, que podían generar números pseudoaleatorios a alta velocidad, amplió dramáticamente la gama de problemas para los cuales el enfoque estocástico resultó ser más efectivo que otros métodos matemáticos. Después de esto, se produjo un gran avance y el método de Monte Carlo se utilizó en muchos problemas, pero su uso no siempre estuvo justificado debido a la gran cantidad de cálculos necesarios para obtener una respuesta con una precisión determinada.

Se considera que el año de nacimiento del método Montecarlo es 1949, cuando se publicó el artículo de Metropolis y Ulam “El método Montecarlo”. El nombre del método proviene del nombre de la ciudad del Principado de Mónaco, muy conocida por sus numerosos casinos, ya que la ruleta es uno de los generadores de números aleatorios más conocidos. Stanislaw Ulam escribe en su autobiografía Las aventuras de un matemático que el nombre fue sugerido por Nicolás Metrópolis en honor a su tío, que era jugador.

Esta publicación te ayudará a salir de una situación bastante complicada. Digamos que estás encerrado en una habitación, tienes un ovillo de hilo y una aguja y te piden persistentemente que calcules el valor aproximado de un número. Pi, usando sólo estos objetos, bueno, cualquier cosa puede pasar, ya sabes. Entonces, hoy, mientras escuchaba un curso sobre matan en la Universidad de Pensilvania, de repente aprendí cómo hacer esto. Lo que ni siquiera podía imaginar era que el número Pi Se esconde aquí también. Resultó que las raíces de esta cuestión se remontan al siglo XVIII, cuando Georges-Louis Leclerc de Buffon se propuso la siguiente tarea: “supongamos que el suelo está hecho de listones de madera de dos colores, se alternan; ¿Cuál es la probabilidad de que una aguja lanzada caiga de tal manera que cruce la línea donde se unen las dos tiras? Debajo del corte encontrará una simulación de este proceso y la respuesta a la pregunta.

Simulación

Para no estropear la intriga, comencemos con un experimento. Entonces, tenemos muchas agujas de longitud. l y un ovillo de hilo verde. Apliquemos un cierto número de segmentos paralelos de igual longitud a la superficie a una distancia l de cada uno.

Arrojemos 100 agujas a este campo.

Quizás no sea suficiente. Sumemos otros 900 y marquemos en rojo aquellas agujas que cruzan los hilos.

Supongamos que no lanzamos todas las agujas a la vez, sino una a la vez, y en cada paso registramos la relación entre el número de agujas que aterrizaron en los hilos y el número total de agujas lanzadas, obteniendo así una aproximación cada vez mayor de la probabilidad de que la aguja, al caer, cruce el hilo.

Si lanzas 10.000 agujas, la imagen será más precisa.

Ahora hagamos la siguiente transformación: divida dos por cada número de la serie resultante.

Para 10.000 agujas ya es más preciso.

Si encontramos el promedio de los últimos cinco mil términos de la serie obtenemos 3.141685 , mientras que pi es igual a 3.141593 .

En general, para nadie ya es un secreto que la última serie converge al número Pi. ¿Pero cómo pudo pasar esto? Aprendí sobre esto cuando tenía 28 años en el curso anterior. Sumerjámonos en el matan.

Teoría

Consideraremos la aguja y la línea más cercana a ella a la derecha. Denotamos la distancia desde el extremo izquierdo de la aguja. h, ángulo de desviación de la línea - a.

Obviamente, la longitud del cateto opuesto al ángulo A será igual al seno del ángulo multiplicado por la longitud de la hipotenusa. Entonces podemos afirmar que si h menor o igual que el cateto opuesto al ángulo A, luego la aguja cruza el hilo. Dibujemos un gráfico:

Si contamos por cada aguja lanzada h Y a y marca estos puntos en el gráfico anterior, la imagen quedará de la siguiente manera:

Por lo tanto, la probabilidad de que la aguja cruce el hilo será igual a la relación entre el área de la figura debajo del gráfico y el área del rectángulo, es decir Pi, multiplicado por la longitud de la aguja.

De aquí obtenemos la aproximación deseada del número. Pi, como lo demostró la experiencia de la primera parte.

El avión está lleno de líneas paralelas. La distancia entre dos líneas rectas adyacentes es igual a 1. Una aguja de longitud fija cae sobre un plano. yo (yo ≤ 1).

Encontrar la probabilidad con la que la aguja cruza al menos una de las líneas (es decir, tiene puntos comunes con al menos una de las líneas).
Suponemos que la aguja no tiene espesor (es sólo un segmento) y que cae y queda plana sobre el plano, y no se clava en él.

Pista 1

¿Qué se entiende por probabilidad de un evento?

1. Primero, pongámonos de acuerdo sobre lo que queremos decir con evento. Realicemos una serie de experimentos idénticos: pruebas, en cada una de las cuales se utilizan las mismas condiciones iniciales y el resultado de la siguiente prueba no depende de los resultados de las anteriores. Ejemplos de libros de texto: lanzar una moneda “perfecta”, lanzar un dado “perfecto”. O, como en nuestro problema, arrojar una aguja a un plano alineado.

Cada prueba tiene diferentes resultados elementales. Por ejemplo, lanzar un número del 1 al 6 en el ejemplo de los dados. Evento se llama algún subconjunto del conjunto de resultados elementales. Por ejemplo, "tira 2". O “sacar un número impar” (es decir, sacar un 1, 3 o 5). Puedes considerar pruebas más complejas, como lanzar cinco monedas. Aquí los resultados elementales serán: “cayeron cinco cabezas”, “cayeron cuatro cabezas y una cola”, etc. Como suceso podemos considerar, por ejemplo, lo siguiente: “al menos tres cabezas cayeron”.

En nuestro problema, una prueba es lanzar una aguja y el evento que necesitamos es la intersección de al menos una línea.

2. Bajo probabilidad de un evento se puede comprender la relación entre el número de resultados favorables para este evento y el número de todos los resultados posibles (de ahí que resulte que la probabilidad es siempre un número de 0 a 1). Por ejemplo, la probabilidad del evento "obtener un número impar" al lanzar un dado es 1/2, porque exactamente la mitad de todos los resultados posibles coinciden. La probabilidad del evento "al menos tres caras" al lanzar 5 monedas también es 1/2.

Esta definición de probabilidad funciona bien cuando el conjunto de resultados posibles es finito. Pero en nuestro problema hay infinitos resultados: las posiciones de la aguja caída. Y también hay infinitos resultados adecuados. ¿Cómo ser? Ajustemos un poco nuestra “definición”: probabilidad de un evento- esta es la proporción que “ocupan” los resultados favorables en el conjunto de todos los resultados. Con esta “definición” ya es posible calcular la probabilidad requerida en el problema.

Para ser honesto, todo lo dicho anteriormente es una explicación “práctica” y no puede considerarse con todo rigor matemático. Pero para nuestros propósitos este enfoque es más que suficiente.

3. Sólo un ejemplo más para mayor claridad. Consideremos un cuadrado y conectemos los puntos medios de dos lados adyacentes con un segmento, cortando así una esquina. Después de esto, introduciremos la aguja al azar en el cuadrado. ¿Con qué probabilidad vamos a llegar al interior de la esquina? Aquí, el resultado de cada prueba es dónde aterriza el extremo de la aguja, es decir, un punto dentro del cuadrado. Está claro que hay infinitos resultados y que también hay infinitos resultados adecuados para nuestro evento: llegar a la esquina. Por tanto, ya no tiene sentido hablar del número de resultados para calcular la probabilidad. Pero la fracción se puede calcular: es simplemente la relación entre las áreas de la esquina y el cuadrado. Es igual a 1/8. Ten en cuenta que los límites de las figuras tienen área cero, por lo que no tienes que pensar en ellos. En particular, la aguja golpeará el segmento que cortó la esquina con probabilidad 0.

Pista 2

El último ejemplo de la primera pista puede dar una idea de una posible forma de resolver el problema. Es necesario ingresar parámetros que determinarían la posición de la aguja y nos permitirían describir todos los casos en los que cruza las líneas. Aquí dos parámetros son suficientes. Después de esto, debemos comprender qué valores pueden tomar estos parámetros y qué valores describen nuestro evento. Si eliges bien los parámetros, entonces estas condiciones serán bastante simples e incluso podrás “representarlas”: toma un plano de coordenadas cuyos ejes correspondan a los parámetros y dibuja una región cuyos puntos satisfagan las condiciones obtenidas. Después de esto solo queda calcular el área de toda la región y el área de esa parte de ella que corresponde a la intersección de la aguja y las líneas. Y luego encuentre la proporción de estas áreas.

Solución

Acordemos que las líneas rectas de la condición van horizontalmente. Entonces tiramos la aguja al avión. ¿Cómo describir su ubicación para que sea conveniente tener en cuenta la intersección con líneas rectas? Observemos una simetría peculiar: no es tan importante para nosotros en qué franja (o cuál, si hay dos) franjas entre las líneas rectas caerá la aguja: las franjas son todas iguales. También está claro que los desplazamientos horizontales tampoco tienen ningún efecto. Pero lo realmente importante es qué tan "lejos" está la aguja de las líneas rectas y en qué ángulo está inclinada respecto a ellas. Por tanto, como parámetros de la segunda sugerencia, se puede tomar el ángulo de inclinación α de la aguja con respecto a las rectas y la distancia d desde el centro de la aguja hasta más cercano recto (Fig. 1). Por tanto, utilizamos otra "simetría" que surgió en el problema.

¿Qué valores pueden tomar estos parámetros? La medida en radianes del ángulo α varía de 0 a π, y d toma valores de 0 (si el centro de la aguja está en línea recta) a 1/2 (el centro de la aguja no puede estar más lejos de una línea recta). En el plano con coordenadas (α, d) estas restricciones definen un rectángulo (Fig. 2).

De la Figura 3 queda claro bajo qué condiciones en α y d la aguja cruza al menos una línea recta: la proyección de la mitad de la aguja en la dirección perpendicular a las líneas rectas debe ser mayor d. Es decir, se debe satisfacer la desigualdad.

Entonces tenemos una descripción de todos los casos en los que la aguja cruza al menos una línea (habrá una intersección con dos líneas solo si las igualdades α = π/2 y d= 1/2, lo que puede dar solo un punto en nuestro rectángulo: un conjunto infinito de todos los valores posibles de un par de parámetros). Queda por calcular el área bajo el gráfico sinusoide y dividirla por el área de todo el rectángulo, que es igual a π/2 (Fig. 4).

Como se sabe, el área bajo la gráfica de una función es igual a una determinada integral de esta función en el intervalo requerido: .

Como resultado, encontramos que la probabilidad deseada es igual a .

Epílogo

Se cree que este problema fue planteado y estudiado por primera vez por el científico francés del siglo XVIII, el Conde de Buffon, una persona bastante extraordinaria con una gama muy amplia de intereses que hizo muchas cosas útiles en diversos campos del conocimiento. Por lo tanto, a menudo se le llama el problema de las agujas de Buffon. Al parecer, este fue el primer problema sobre la llamada probabilidad geométrica. Como hemos visto, la esencia de este enfoque es representar el conjunto de resultados elementales de alguna prueba en forma de figura geométrica y reducir la cuestión de encontrar la probabilidad de un evento particular al cálculo de la relación de las áreas de figuras adecuadas. . De esta manera, puede resolver varios problemas más bastante conocidos; quizás conozca algunos de ellos más adelante aquí en "Elementos". Por ello, presentaremos sólo una tarea más sencilla a modo de ejercicio:

¿Cuál es la probabilidad de que una moneda redonda de diámetro d, lanzada sobre un plano cuadriculado (dividido en cuadrados unitarios), no cubra ninguna de las líneas de la cuadrícula, es decir, termine completamente dentro de uno de los cuadrados?

Tenga en cuenta que al resolver el problema de Buffon, se puede razonar de manera un poco diferente. El curso de tal decisión se describe en detalle (aunque en inglés).

Ahora un poco sobre el significado de la respuesta que recibimos. En yo = 1 la respuesta es aproximadamente 0,6366197... ¿Qué representa exactamente este número? Como es habitual, en teoría de la probabilidad esto debería entenderse de la siguiente manera. Digamos que hicimos una serie muy larga de pruebas. Digamos que tuvimos la paciencia de lanzar una aguja un millón de veces en cada prueba y recordar cuántas veces cruzó líneas rectas en un avión. Y también realizamos un millón de pruebas de este tipo. Resulta que en la mayoría de ellos (muy probablemente, la abrumadora cantidad) el número de intersecciones se acerca a 636 619. Y cuantas más pruebas de este tipo realicemos, más cercana será la proporción de resultados exitosos (cuando la aguja cruzó la línea). a. Y, de hecho, por supuesto, no importa en absoluto cómo se dividen las pruebas en series; lo único importante es el número total. En realidad, no hay suficiente paciencia para realizar una serie de pruebas tan larga. Pero puedes escribir un programa (o usar programas existentes como este) que realice operaciones de rutina y proporcione solo el número de intersecciones para una gran cantidad de tiros.

Lo dicho en el párrafo anterior da un enfoque inusual al importante problema de calcular con precisión el número π = 3,1415926... Recordemos que este número se define como la relación entre la longitud de un círculo y su diámetro (para todos los círculos esta relación es la misma). El número π es una de las principales constantes en matemáticas y física. Esto puede explicarse en parte por el hecho de que los círculos y elipses aparecen en matemáticas y física en una variedad de problemas y modelos, desde los puramente geométricos hasta los prácticos, como los cálculos de las órbitas de planetas y satélites. Por tanto, es importante poder calcular con precisión el valor del número π. Se sabe que este número es irracional, es decir, no se puede representar como una fracción racional (la proporción de dos números enteros), pero hay fracciones cercanas con denominadores pequeños. Arquímedes también sabía que la fracción 22/7 = 3,(142,857) se aproxima a π con una precisión de milésimas. Alrededor del siglo V d.C. mi. la aproximación 355/113 = 3,14159292... ya se conocía: el error es inferior a una millonésima.

¿Qué tiene que ver la aguja de Buffon con esto? Como ya sabemos, en una larga serie de pruebas, la proporción de intersecciones respecto del número total de lanzamientos de aguja será aproximadamente igual a 2/π. Por tanto, podemos encontrar empíricamente esta fracción y calcular un valor aproximado. Cuantos más lanzamientos, más precisa será la fracción y, por tanto, el valor de π. En el siglo XIX había héroes que estaban dispuestos a dedicar varias tardes a tal actividad. Obtuvieron valores diferentes alrededor de 3,14. Puede leer más en esta página de la Wikipedia en inglés.

Ahora, por supuesto, nadie está lanzando una aguja, y el número π ya se ha calculado mucho más allá de los 10 billones de dígitos. Es curioso que tal precisión no sea necesaria para los cálculos prácticos: se estima que es suficiente conocer π hasta aproximadamente el 40º decimal para calcular con precisión el volumen del Universo visible con una precisión de un átomo. Por lo tanto, calcular π con tanta precisión es más bien una carrera por récords y una competencia entre supercomputadoras.

Los cálculos exactos se basan en diferentes fórmulas. Básicamente, se utilizan secuencias que convergen a π y suma de series; se pueden encontrar muchos algoritmos en Wikipedia. Aquí presentamos sólo una fórmula maravillosa.

lo que le permite calcular cualquier dígito de π sin calcular los dígitos restantes.