Historia de los métodos Monte Carlo

Universidad de Roma, años 30

– ¿Ya tenemos los resultados?

– Sí, y de nuevo Fermi ha acertado.

– Pero, ¿cómo demonios lo hace?

– Él dice que es una simple cuestión de estadística e insomnio.

Enrico Fermi realizaba una investigación sobre neutrones y sus noches de insomnio las dedicaba a intentar predecir el resultado de los próximos experimentos para sorprender a sus colegas. Para ello utilizaba dos herramientas: muestreo estadístico y un pequeño dispositivo mecánico para realizar sumas. En esa época, el muestreo estadístico era una técnica poco usada por el incordio que suponía la multitud de cálculos a realizar, pero Enrico tenía poco sueño y mucha curiosidad. No sabía que estaba usando lo que en un futuro se denominaría un método Monte Carlo.

Permitidme un pequeño salto en el tiempo y en el espacio. Nos trasladamos a 1945. La Segunda Guerra Mundial está próxima a terminar, se había completado con éxito la prueba de la bomba nuclear en Alamogordo, mientras los científicos de Los Álamos seguían trabajando en la bomba sin cesar y Estados Unidos comenzaba a mirar hacia Rusia como el nuevo enemigo.

BEHOLD!!! THE ENIAC!!!

Pero no solo Los Álamos tuvieron una actividad frenética durante la guerra. John Mauchly y Presper Eckert, de la Universidad de Pennsylvania, habían convencido al Laboratorio de Investigación Balística en Aberdeen de la posibilidad de crear una máquina de cálculo con circuitos electrónicos que les permitiera calcular las tediosas tablas de trayectoria de proyectiles, ya que, hasta la fecha, los cálculos eran realizados por un grupo de mujeres especializadas en la resolución de ecuaciones diferenciales con la ayuda de una simple -pero enorme- calculadora de escritorio. Este proyecto dio lugar a la creación del ENIAC, considerado por algunos como el primer computador de la historia.

ENIAC ocupaba una habitación entera. Ahora tenemos ordenadores mucho más potentes en la palma de la mano.

La máquina contaba con unos 18.000 tubos de vacío en un sistema con unas 500.000 uniones soldadas. Su tamaño era gigantesco, ocupando una habitación entera, y la velocidad de procesamiento rondaba los 100 kHz.

Comparativa de la velocidad de procesamiento de ENIAC respecto a otros dispositivos más actuales, como el primer 8086, el primer Pentium y uno de los procesadores con los que funciona el iPhone5.

100 kHz no es prácticamente nada si lo comparamos con la velocidad de los procesadores actuales; un solo microprocesador del iPhone 5 tiene una velocidad de operación de 1,3GHz, 13.000 veces más que el ENIAC.

Pero la velocidad de operación del ENIAC era muy superior a la que se podía conseguir por los métodos convencionales de la época. Las herramientas disponibles eran mecanismos analógicos y grupos de operarios especializados en cálculo.

ENIAC y Los Álamos

Aberdeen tenía algo en común con Los Álamos: John Von Neumann, el genial matemático húngaro. Y cuando Johnny andaba por medio, siempre aparecían nuevas ideas.

Los Álamos, 1945

– Así que han conseguido poner en marcha… ¿cómo se llamaba?

– ENIAC. Lo tienen casi listo para hacer la primera prueba, tablas de trayectorias de proyectiles… ¡qué desperdicio Nicko!

– Pero seguro que ya tienes algo en mente, Johnny.

– Sí, me gustaría que Stan Frankel y tú prepararáis un modelo de una reacción termonuclear para probar de verdad el ENIAC.

La guerra terminó antes de que Nicko Metropolis y Stan Frankel acabaran de diseñar los programas que deberían ejecutarse en ENIAC, pero la carrera nuclear seguía siendo prioritaria. Hacía tiempo que el enemigo había dejado de ser Alemania o Japón y el peligro ahora estaba en Rusia.

En primavera de 1946, llegó la revisión de los resultados del experimento: eran positivos respecto a la creación de una bomba termonuclear y, lo más importante, demostraban la importante capacidad de cálculo del ENIAC. En esa reunión se encontraba Stanislav Ulam, quien enseguida se dio cuenta de que la potencia de cálculo del ENIAC podía permitir la resurrección de las técnicas de muestreo estadístico que habían quedado en desuso debido al gran número de cálculos que requerían.

En Los Álamos estaban gran parte de las mentes más brillantes del mundo de la ciencia en EEUU, así que la chispa que encendió Ulam prendió rápidamente y se empezaron a definir los cimientos de los que acabaron llamándose métodos Monte Carlo. El nombre tuvo su origen en la metodología utilizada, ya que la aleatoriedad necesaria recordaba al juego en un casino y, en gran parte, a un tío de Ulam que cuando iba a pedir dinero a la familia, iba a Monte Carlo.

¿En qué consiste un método Monte Carlo?

Existe un ejemplo bastante simple que se usa siempre para describir este método. Imaginemos que tenemos una circunferencia inscrita en un cuadrado y tenemos una forma de marcar puntos en el cuadrado aleatoriamente. Unos puntos quedarán fuera del círculo y otros quedarán dentro. Pues bien, si generamos el número suficiente de puntos, podremos calcular el número π de la siguiente forma:

Suponemos que el cuadrado tiene un lado de tamaño 2r y por tanto la circunferencia inscrita tiene un radio r. El área del cuadrado será

A_{cuadrado} = (2r)^2 = 4r^2

y el área del círculo será

A_{circulo} = \pi r^2

Si dividimos el área del círculo por el área del cuadrado tendremos:

\frac{A_{circulo}}{A_{cuadrado}} = \frac{\pi r^2}{4 r^2} = \pi/4

Si realizamos la división del número total de puntos que tenemos dentro del círculo respecto al número total de puntos que se han señalado en toda la área del cuadrado, tendremos una aproximación del valor de π

\frac{puntos dentro circulo}{puntos totales} \approx \pi/4

A continuación puede verse una simulación en la que se generan 9.990 puntos para intentar calcular el valor de π:

Ejecución de un método Monte Carlo para cálculo del número π. En este caso, se usa solo la cuarta sección de un círculo, pero el razonamiento es análogo al que realizaríamos al usar el círculo entero. Para ver cómo se ha hecho esta animación mediante el uso de Geogebra y python, podéis visitar mi entrada al respecto en el escriba matemático.

Para obtener una buena aproximación de π, necesitaríamos un gran número de puntos, por lo que este ejemplo es muy útil para dar una idea general del funcionamiento de un método de Monte Carlo, pero poco eficiente para el cálculo para el que ha sido diseñado.

No obstante, la verdadera potencia de los métodos de Monte Carlo la encontramos cuando tratamos problemas cuyo desarrollo se ajusta a una cadena de Markov.

Cadenas de Markov

Las cadenas de Markov son eventos encadenados cuya probabilidad de ocurrencia depende del estado producido por el evento anterior.

Por ejemplo, si yo tiro un dado tengo una posibilidad de 1/6 de obtener un 6. Si saco un 6 y tiro otro dado, mi probabilidad de sacar un 6 vuelve a ser de 1/6. Es decir, no depende del evento anterior y, por tanto, no estaríamos ante una cadena de Markov, sino ante eventos totalmente independientes entre sí.

Pero el cálculo que querían realizar en Los Álamos era bastante más complicado. Consideremos un núcleo esférico de material fisible, rodeado de un escudo de material que atenúe el momento de los neutrones. Asumimos una distribución inicial de neutrones en el espacio y una velocidad. La idea es seguir el desarrollo de un gran número de neutrones como consecuencia de dispersión, absorción, fisión y escape del núcleo esférico. En cada etapa, una serie de decisiones tienen que tomarse en base a probabilidades estadísticas acordes con los factores físicos y geométricos. Las dos primeras decisiones se realizarían en t = 0, cuando a un neutrón se le asigna cierta posición y velocidad. La siguiente decisión será la posición de la primera colisión del neutrón y la naturaleza de esa colisión. Si ocurre una fisión, debe decidirse el número de neutrones que se generarán y sobre cada uno de ellos su posición y velocidad inicial. Si la colisión resulta en una dispersión, debe calcularse el nuevo momento del neutrón en base a modelos estadísticos apropiados. Cuando el neutrón cruza la frontera de un material, se toma en cuenta la característica de este material. La historia de cada neutrón es generada y el proceso se repite continuamente hasta obtener los datos suficientes para generar una estadística apropiada de las probabilidades de comportamiento del sistema completo.

La importancia de un buen generador de números aleatorios

El éxito de un método Monte Carlo se basa sobre todo en la calidad de la simulación del modelo físico a comprobar, pero hay un punto importante a la hora de realizar las pruebas, y éste es el generador de números aleatorios usados. Si usamos un generador totalmente aleatorio, los resultados no serán todo lo buenos que podemos esperar, por lo que, en lugar de este tipo de generadores, se usa un generador de números pseudoaleatorios. La diferencia consiste en que un generador de números pseudoaleatorios generará la misma cadena de números siempre a partir de un número inicial dado, es decir, es determinista. La ventaja estriba en la posibilidad de hacer que estas secuencias cumplan ciertas distribuciones estadísticas.

En los inicios del método Monte Carlo, se usó un generador de números pseudoaleatorios ideado por Von Neumann que consisitía en elevar al cuadrado un número de n digitos y luego se seleccionaban los n dígitos centrales como el siguiente número de la secuencia. Para obtener otro número se repetía la operación. Un ejemplo sencillo simplificado a números de 3 cifras sería este:

N_0: 235
235 * 235 = 55225
N_1:  522
522*522 = 272484
N_2: 248
...

Traslado del ENIAC y aparición del FERMIAC

En 1947, ENIAC se trasladó a su sede definitiva en un laboratorio de la Marina en Maryland. Ese tiempo fue aprovechado por Enrico Fermi para recordar sus viejos tiempos en Roma y enseñar a sus colegas cómo se podían hacer los cálculos estadísticos que necesitaban a la vieja usanza. Enrico estaba también en Los Álamos y, al ver el revuelo que se estaba montando con el desarrollo de los métodos Monte Carlo, quiso aprovechar el parón forzoso provocado por el traslado del ENIAC y desarrolló junto a Percy King un instrumento analógico para avanzar en los cálculos que necesitaban para el desarrollo de la bomba termonuclear. El resultado fue FERMIAC, al que podemos ver en funcionamiento en la foto:

FERMIAC en funcionamiento

FERMIAC se colocaba encima de una hoja de papel que representaba los distintos elementos del núcleo fisible y se configuraba según el material que estaba cruzando para calcular la siguiente colisión. Cuando se producía una colisión, había una serie de elementos mecánicos que permitían seleccionar una nueva dirección. Al final se obtenían gráficos como el que puede verse en la foto, que daban una idea de las posibles trayectorias de los neutrones.

El primer test

El ENIAC llegó a su nueva casa, pero el tiempo dedicado al viaje y ensamblaje de semejante monstruo no fue en balde y se diseñaron unos nuevos controles para manejar a la bestia. Se sustituyó el gigantesco tablero de cables -a modo de  centralita- por una forma de cargar los programas en base a un conjunto de 60 instrucciones. Con este nuevo modelo, el concepto de programación empezaba a acercarse más al actual.

El primer test de Monte Carlo se realizó para varias configuraciones de material y simplificando los modelos que no incluían efectos radiactivos e hidrodinámicos. Los resultados fueron comparados con los obtenidos mediante otros métodos más clásicos y el éxito fue total.

La llegada de más computadoras y el conocimiento del método por parte de otros laboratorios y universidades hicieron que el desarrollo de Monte Carlo tuviera una velocidad vertiginosa. En 1949, Ulam y Metropolis ya habían publicado la descripción del método (N. Metropolis and S.Ulam 1949. The Monte Carlo method. Journal of the American Statistical Association) y a mitad del mismo año realizaban conferencias dedicadas exclusivamente a los métodos de Monte Carlo.

¿Y esto se usa?

No os imagináis cuánto. Los métodos Monte Carlo, una vez publicados, corrieron como la pólvora entre los físicos y se convirtieron en una herramienta imprescindible para realizar simulaciones de sistemas reales. Con el paso de los años, el ámbito de estos métodos se extendió y ahora son una herramienta muy útil en todo tipo de estudios científicos y en ámbitos tan dispares como la economía, cálculos estadísticos de juegos de azar y deportivos o incluso gestión de proyectos, donde son una herramienta importante para la gestión de riesgos en proyectos de gran envergadura (aquí podéis ver un ejemplo simple).

Referencias

N. Metropolis 1987. The begining of the Monte Carlo Method. Los Alamos Science Special Issue.

N. Metropolis and S.Ulam 1949. The Monte Carlo method. Journal of the American Statistical Association

También podéis comprobar como hice el ejemplo del método Monte Carlo usando la última versión beta de GeoGebra y su integración con python: GeoGebra 5 y Python

Y por supuesto debes visitar el viaje locuelo a otras dimensiones con Monte Carlo.

Anuncios

Publicado el 17 noviembre, 2012 en Historia de la ciencia y etiquetado en , , , , , , , . Guarda el enlace permanente. 18 comentarios.

  1. Hay un error acerca de los números aleatorios. Los ordenadores usan números pseudoaleatorios no porque se prefieran, sino porque una máquina determinista no puede generar números aleatorios de verdad. Sencillamente, un ordenador no puede “inventarse” números, tiene que seguir un procedimiento. Si quisiéramos generar números que realmente no se puedan repetir, se puede usar, por ejemplo, el ruido captado por un micrófono, o cualquier otro aparato analógico. En unos pocos casos, puede ser interesante la replicabilidad, es decir, tener la misma secuencia de números para diferentes ejecuciones del programa (si estamos haciendo pruebas, o algo así), pero yo es algo que no he necesitado nunca, y he hecho unos cuantos MC.

    Por otro lado, un generador, cuanto mejor sea, más fiables serán los resultados, y de hecho, el método de Jonny es muy malo. Muy pronto surgieron otros algoritmos que generan los números de una forma más aleatoria (es decir, sin seguir patrones, cubriendo todo el recorrido, etc). La mayoría de generadores parten de una distribución uniforme (todos los números en un intervalo son igualmente probables), y desde ahí se pueden generar números siguiendo la distribución que sea.

    La calidad del generador no es una cosa trivial. Los resultados de un Monte Carlo sólo pueden llegar a ser tan buenos como tu generador de aleatrios. Y hay por ahí muchos resultados que deben ser puestos en duda por la sencilla razón que su generador de números no es bueno, produce patrones que pueden afectar al resultado. Por poner un ejemplo simplificado, imaginemos un algoritmo que produce números entre -1 y 1, y siempre que produzca un número positivo, el siguiente va a ser negativo y viceversa. Si en cada paso usamos el primer número para la posición y el segundo para el tiempo, en vez de estar muestreando todo el espacio y todo el tiempo, estaremos tomando la mitad de cada uno: un cuarto del total. Por supuesto, los algoritmos reales son mucho mejores que este, pero los fallos pueden ser igualmente flagrantes.

    • La verdad es que tienes razón en todo, el ordenador nunca podrá generar números aleatorios “reales” sin un periférico que consiga esa aleatoriedad, por ejemplo truecrypt lo intenta haciendo que el usuario mueva el ratón por la pantalla cuando va a generar las claves de encriptado. El método de Von Neumann era bastante malo, pero es el primero que se les ocurrió en ese momento y por su sencillez lo incluí en la explicación, meterse en explicar un método que obtiene una distribución gaussiana hubiera sido demasiado pesado.

      Tengo pendiente publicar un post en http://elescribamatematico.wordpress.com en el que comparo el uso de un generador “estandar” de python de números aleatorios y uno que sigue la secuencia de Sobol, espero que puedas echarle un vistazo cuando lo publique, porque se agradecen estos comentarios.

    • Estoy de acuerdo en todo lo que dices, sólo una puntualización: Para que el ruido de un aparato se pueda utilizar como aleatorio tiene que ser ruido blanco, cualquier otro tipo de ruido tendrá un patrón distinto al de la distribución normal y no se conseguiría el objetivo aquí descrito.

      Muy buena la entrada y los comentarios.

  2. Hola,

    me ha gustado tanto la entrada sobre el uso del ENIAC y su motivación, que la he referenciado desde la plataforma virtual de mi asignatura en la UBU. Los métodos de Monte Carlo quedan un poco lejos pero espero que algún alumno se anime a leer esta entrada y le guste.

    Un saludo.

  1. Pingback: GeoGebra 5, Python y Monte Carlo « El escriba matemático

  2. Pingback: El método Monte Carlo, la primera computadora y la bomba

  3. Pingback: Dr. Strangelove, Peter Sellers, Von Neumann y la teoría de juegos « El zombi de Schrödinger

  4. Pingback: Bitacoras.com

  5. Pingback: El poder de una estrella « El zombi de Schrödinger

  6. Pingback: Salinas, ¡la vida puede ser maravillosa! « El zombi de Schrödinger

  7. Pingback: Nueva temporada | El zombi de Schrödinger

  8. Pingback: El dragón diferencial | El zombi de Schrödinger

  9. Pingback: El lado débil de la física (I): el inicio | El zombi de Schrödinger

  10. Pingback: GeoPy: Estudi de les posicions relatives de rectes en el pla | EduLogiX

  11. Pingback: Como aprendí a dejar de preocuparme y amar la bomba | El zombi de Schrödinger

  12. Pingback: Dr. Strangelove, Peter Sellers, Von Neumann y la teoría de juegos | Del Mundo, Desde Parla

¡Un comentario para un ex-leproso!

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: