Universidad Nacional de Ingeniería Facultad de Ciencias

Física Computacional CC063

Aleatoriedad Deterministica Aplicaciones MC Prof: J. Solano 2012-I Fisica Computacional - CC063

Introducción

Algunos son atraídos a la informática, por su naturaleza determinista. Salvo errores de la máquina al azar o variables no definidas, se debe obtener el mismo resultado si se suministra la misma entrada. Sin embargo, muchos ciclos de ordenador se utilizan para cálculos Monte Carlo (MC) que en esencia se esfuerzan por ser al azar. Estos son cálculos en que números aleatorios generados por ordenador se utilizan para simular procesos aleatorios de forma natural, tales como el movimiento térmico o la desintegración radiactiva, o para resolver las ecuaciones de la media. Gran parte del reconocimiento de la física computacional surge de la capacidad de las computadoras para resolver problemas previamente intratables de termodinámica y mecánica cuántica usando técnicas de MC. Exploraremos cómo las computadoras pueden generar números aleatorios Para comprobar si realmente funciona, simularemos algunos procesos físicos sencillos y evaluaremos algunas integrales multidimensionales. Fisica Computacional - CC063 2

Secuencias aleatorias (1) Secuencia de números r1,r2,... es aleatoria, si no hay correlación entre los números de la secuencia. Al azar no significa necesariamente que todos los números de la secuencia tienen la misma probabilidad de ocurrir. Si todos tienen la misma probabilidad de ocurrir, entonces la secuencia es uniforme. Por ejemplo, 1,2,3,4,... es uniforme, pero no al azar, mientras que 3,1,4,2,3,1,3,2,4,... puede ser al azar, pero no parece uniforme. Además, es posible, tener una secuencia de números que, en cierto sentido, son aleatorios, pero tienen correlaciones de muy corto alcance, por ej: r1(1-r1)r2(1-r2)r3(1-r3) ... Matemáticamente, la probabilidad de que se produzca un número aleatorio es descrito por una función de distribución P(r). Esto significa que la probabilidad de encontrar r1 en el intervalo [r,r+dr] es P(x)dx. El generador estándar de números aleatorios en equipos genera distribuciones uniformes (p=1) entre 0 y 1. En otras palabras, la salida del generador estándar de números aleatorios genera números de salida en este intervalo, c/u con una igual probabilidad pero independiente del número anterior. Los números pueden generarse no uniformemente y aún así ser al azar. Fisica Computacional - CC063 3

Secuencias aleatorias (2) Las computadoras son deterministas, por lo que no puede realmente crear una secuencia aleatoria. Aunque puede ser un poco trabajoso, si sabemos rm y sus elementos anteriores, siempre es posible calcular r m+1. Por esto, las computadoras generan numeros "pseudo"-aleatorios. Por la naturaleza misma de su creación, los números aleatorios generados deben contener correlaciones, por lo que no son realmente aleatorios. (Por pereza no diremos "pseudo" todo el tiempo.) Generadores más sofisticados hacen un mejor trabajo en esconder las correlaciones, pero la experiencia muestra que si se busca lo suficiente, o se usa estos números bastante, se notaran las correlaciones. Una alternativa primitiva a la generación de números aleatorios es leer en una tabla de números aleatorios verdaderos, es decir, números determinados por los procesos naturales aleatorios, tales como la desintegración radiactiva. Puede proporcionar una comparación valiosa. Fisica Computacional - CC063

4

MÉTODO: generadores de números pseudo-aleatorios (1) La congruencia lineal, o método de potencia de residuos, es la forma más común de generar una secuencia de números aleatorios, {r1,r2,...,rk} en el intervalo [0,M-1]. Se multiplica el número aleatorio anterior r i-1 por la constante a, añadir en otra constante c, tomar el módulo de M, y a continuación, guardar sólo la parte fraccionaria (el resto) como el siguiente número aleatorio ri:

El valor de r1 (semilla) es frecuentemente dado por el usuario, y mod es una función integrada en el equipo para dar el residuo (amod o dmod). Esencialmente es una operación de corrimiento de bits que termina con la parte menos significativa del número de entrada, y por lo tanto cuenta con la aleatoriedad de los errores de redondeo para producir una secuencia aleatoria. Fisica Computacional - CC063

5

MÉTODO: generadores de números pseudo-aleatorios (2) Por ejemplo, si c=1, a=4, M=9, y se suministra r1=3, entonces se obtiene la secuencia

Es una secuencia de longitud M=9, después de lo cual se repite la secuencia completa. Si queremos los números en intervalo [0,1], debemos dividir estos r valores por M=9. Aun sería una secuencia de longitud 9, pero ya no de enteros.

Fisica Computacional - CC063

6

MÉTODO: generadores de números pseudo-aleatorios (3) Esta regla produce enteros en rango [0,M-1]. Cuando un entero se repite, el ciclo entero tambien se repite. M y a deberian ser grandes pero no demasiado para que a.ri-1 no produzca overflow. En un computador de 48 bits M puede ser 248~3x1014. De 32 bits, M=231~2x109. Si tu program usa esta cantidad aproximada de numeros aleatorios entonces hay que “re-semillar” la secuencia. Se recomienda usar generadores drand48 y srand48, que generanr numeros aleatorios en rango [0,1] usando artimetica de enteros de 48 bits. M=248, a=5DEECE66D16=2736731631558 c=B16=138. Esto generara ri valores en rango [0,M], o [0,1] si se divide por M. Si se necesitan numeros aleatorios en rango [A,B], solo hay que escalar: xi = A + (B-A) ri, 0 ≤ ri ≤ 1, produce A ≤ xi ≤ B.

Fisica Computacional - CC063

7

EVALUACIÓN: secuencias aleatorias Para trabajo científico se recomienda utilizar un generador de números aleatorios de potencia industrial. 1. Escribir un programa sencillo para generar números aleatorios utilizando el método lineal congruente. 2. Por razones pedagógicas, tratar la elección: (a,c,M,r1)=(57,1,256,10). Determinar el periodo, cuántos números se generan antes que la secuencia se repite. 3. Tome la secuencia pedagógica de números aleatorios y buscar correlaciones mediante observación de agrupaciones en un plot de pares sucesivos (xi,yi)=(r2i-1,r2i), i=1,2,... (No conecte los puntos con líneas.) Al igual que en la figura anterior, se puede "ver" correlaciones, lo que significa que usted no debe utilizar esta secuencia para un trabajo serio. 4. Pruebe el generador integrado (built-in) de números aleatorios en el ordenador para correlaciones, ploteando los mismos pares que el anterior. (Esto debería ser bueno para el trabajo serio.) 5. Pruebe el método congruente lineal de nuevo con constantes razonables como las del slide anterior. Comparar el scatterplot que se obtiene con el del generador integrado de números aleatorios. (Esto también debe ser bueno para trabajo serio.) Fisica Computacional - CC063

8

random.c

Fisica Computacional - CC063

9

call.c

Fisica Computacional - CC063

10

EVALUACIÓN: La aleatoriedad y la uniformidad Como números aleatorios del ordenador se generan de acuerdo con una regla definida, los números en la secuencia son correlacionados con el resto. Esto puede afectar na simulación que asume eventos al azar. Es prudente probar el generador de números aleatorios antes de jugar tu reputación científica en los resultados obtenidos con ella. Algunos tests son bastante simples que es buen hábito ejecutarlos de manera simultánea con la simulación. En los ejemplos a seguir, hacemos el test, ya sea para probar el azar o la uniformidad. 1. Un test de uniformidad evalúa el kmo momento de la distribución de números N aleatorios: 1 k k

〈 x 〉= ∑ xi N i=1

Si los numeros aleatorios estan con distribucion uniforme de probabilidad P(x), entonces la formula anterior es aproximadamente el momento de P(x): 1 N

N

1 k i

∑x ≃ i=1

k

∫ dx x P (x)+O(1/ √ N ) ≃ 0

1 k +1

Si este resultado funciona en tu generador entonces significa que es uniforme. Si la desviacion varia como 1/ √ N , entonces tambien sabes que la distribucion es al azar. Fisica Computacional - CC063

11

EVALUACIÓN: secuencias aleatorias Para trabajo científico se recomienda utilizar un generador de números aleatorios de potencia industrial. 1. Escribir un programa sencillo para generar números aleatorios utilizando el método lineal congruente. 2. Por razones pedagógicas, tratar la elección: (a,c,M,r1)=(57,1,256,10). Determinar el periodo, cuántos números se generan antes que la secuencia se repite. 3. Tome la secuencia pedagógica de números aleatorios y buscar correlaciones mediante observación de agrupaciones en un plot de pares sucesivos (xi,yi)=(r2i-1,r2i), i=1,2,... (No conecte los puntos con líneas.) Al igual que en la figura anterior, se puede "ver" correlaciones, lo que significa que usted no debe utilizar esta secuencia para un trabajo serio. 4. Pruebe el generador integrado (built-in) de números aleatorios en el ordenador para correlaciones, ploteando los mismos pares que el anterior. (Esto debería ser bueno para el trabajo serio.) 5. Pruebe el método congruente lineal de nuevo con constantes razonables como las del slide anterior. Comparar el scatterplot que se obtiene con el del generador integrado de números aleatorios. (Esto también debe ser bueno para trabajo serio.) Fisica Computacional - CC063

12

PROBLEMA: camino aleatorio (1) Hay muchos procesos físicos (ejs: movimiento browniano, y transporte de electrones a través de metales), en el que la partícula parece moverse al azar. Por ej: un átomo de perfume lanzado en medio del salón de clases. Choca al azar con otros átomos en el aire y, finalmente, llega a la nariz del profesor. El probl. es calcular cuantas colisiones, en media, el átomo debe hacer para viajar la distancia radial R. En una simulación de paseo aleatorio, como en la fig., un caminante artificial lleva muchos pasos, por lo general con la dirección de cada paso independiente de la dirección del anterior. Esto se ilustra en la fig. Para nuestro modelo, comenzamos en el origen y tomamos N pasos en el plano x-y de longitudes (no coordenadas) (x1,y1), (x2,y2), (x3,y3),.....,(xN,yN). La distancia radial R, al punto de partida, despues de N pasos es R2 = (x1+ x2 + … + xN)2 + (y1+ y2 + … + yN)2 = x12 + x22 + … + xN2 + 2x1x2 + 2x1x3 + 2x2x1 + … = (x y). Fisica Computacional - CC063

13

PROBLEMA: camino aleatorio (2) La ec. anterior es valida para cualquier camino. Si es aleatorio la particula puede ir en cualquier direccion en cada paso. En promedio, para una gran numero de pasos aleatorios, todos los terminos cruzados se cancelaran y nos quedamos con R2 ≈ x12 + x22 + … + xN2 + y12 + y22 + … + yN2 = N, => R ≈ √N rrms. Aquí rrms es el (raíz cuadrática media) el tamaño promedio del paso

Fisica Computacional - CC063

14

MÉTODO: camino aleatorio numerico Al simular numericamente una caminata al azar, sólo se espera obtener R≈√N rrms, como el desplazamiento medio después de muchas pruebas, no necesariamente como la respuesta para cada ensayo. Además, puede obtener respuestas diferentes en función de cómo está tomando sus pasos aleatorios. Algunas formas de generar paseos aleatorios 2D: 1. Elegir un ángulo  aleatorio en el rango [0,2]. Establecer x = cos y y = sen. (Si bien esto parece muy razonable, se encuentran algunos problemas que pueden deberse a que una distribucion uniforme en , dxdy = cos send no es uniforme en x e y. 2. Escoger x aleatorio en [-√2,√2] y por separado y aleatorio en [-√2,√2]. De esta forma pasos postivos y negativos en cada direccion son igualmente posibles. 3- Escoger valores aleatorios x en [-1,1] y y = ±√(1-x2) (escoger el signo al azar)

Fisica Computacional - CC063

15

MÉTODO: camino aleatorio numerico

Fisica Computacional - CC063

16

Aplicaciones MC Problema: Decaimiento radiactivo Vimos la desintegración radiactiva espontánea en el cap. de ajuste de datos, donde hicimos el fit de una función exponencial a un espectro de decaimiento. El probl. ahora es simular cómo un pequeño número de partículas radiactivas decaen. En particular, debe determinar cuándo la desintegración radiactiva se ve exponencial y cuando se ve estocástica (es decir, determinado por el azar). Como se ve en la fig., porque la ley de decaimiento exponencial es sólo una aproximación a un gran número de procesos naturales, nuestra simulación debe estar más cerca de la naturaleza que la ley de decaimiento exponencial.

Fisica Computacional - CC063

17

Teoria: Decaimiento expontaneo Desintegración espontánea es un proceso natural en el que una partícula, sin ningún estímulo externo, en un instante en el tiempo, decae en otras partículas. Debido a que el momento exacto cuando una partícula decae es al azar, no importa el tiempo que la partícula ha estado ahi o lo que está sucediendo con las otras partículas. En otras palabras, la probabilidad P de cualquier partícula decayendo por unidad de tiempo es una constante, y cuando esa partícula decae, se ha ido para siempre. Por supuesto, como el número de partículas disminuye con el tiempo, también lo hará el número de desintegraciones. La probabilidad que cualquier partícula decaiga en un intervalo de tiempo es siempre la misma, siempre que la particula exista todavia.

Fisica Computacional - CC063

18

MODELO: Decaimiento discreto Imagine tener N(t) partículas radiactivas en instante t. Sea N ser el número de partículas que se desintegran en pequeño intervalo de tiempo t. Convertimos la instrucción "la probabilidad P de cualquier partícula una descomposición por unidad de tiempo es una constante" en una ecuación observando que la probabilidad de decaimiento por partícula, N/N, es proporcional a la longitud del intervalo de tiempo durante el cual se observa la partícula P = N(t)/N(t) = -t

=> N(t)/N(t)t = -

 = cte = tasa constante de decaimiento por partícula La ec. anterior es una ec. en diferencias finitas en el que N(t) y t son observables experimentales. Aunque no se puede integrar de la forma que una ecuación diferencial puede, se puede resolver numéricamente o algebraicamente. Debido a que el proceso de descomposición es al azar, no podemos predecir un valor exacto para N(t). En su lugar, podemos pensar en N(t) como el número promedio de decaimientos cuando se hacen observaciones de muchos sistemas idénticos de N partículas radiactivas. Convertimos la ec. En una ec. en diferencias finitas para la tasa de desintegración multiplicando ambos lados por N (t): N(t)/t = -N(t) La tasa absoluta de decaimiento N(t)/t se llama actividad, y es proporcional al numero de particulas radiactivas presentes (que decrecen en t), por lo que tambien decrece en el tiempo. Fisica Computacional - CC063

19

MODELO: Decaimiento continuo Cuando el número de partículas N → ∞ y el intervalo de tiempo de observación se aproxima a cero, resulta una forma aproximada de la ley de desintegración radiactiva: N(t)/t → dN(t)/dt = -N(t) Esta puede ser integrada para obtener la ley de decaimiento exponencial para el número y para la actividad: N (t)=N (0)e−ƛ t =N (0)e−t /T dN (t) dN (0) −ƛ t −ƛ t =−ƛ N (0)e = e dt dt En este límite se obtiene decaimiento exponencial. Identificamos la tasa de decaimiento  con la inversa de la vida media:  = 1/T Vemos de su derivación que decaimiento exponencial es una buena descripción de la naturaleza sólo en promedio, y sólo para un gran número de partículas. La ley básica de la naturaleza (cte de decaimiento) es siempre válida, pero, como veremos en la simulación, la ec. obtenida al final se torna en cada vez menos precisa a medida que el número de partículas se hace más y más pequeño.

Fisica Computacional - CC063

20

MÉTODO: Simulacion de decaimiento (1)

Fisica Computacional - CC063

21

MÉTODO: Simulacion de decaimiento (2) Input N(0), l N = Nleft = N(0)

Inicializar

Do hasta que Nleft = 0

Do hasta que todos los nucleos decayeron

Do para N

Ir a traves de todos los nucleos por un periodo t

0