Numeros Aleatorios
isabella201022 de Marzo de 2013
4.123 Palabras (17 Páginas)449 Visitas
3.- Generación de números aleatorios
Una vez construido un modelo, debemos experimentar sobre él y para poder ejecutarlo
necesitamos dar valores a las variables de tipo exógeno. De esta forma podremos obtener valores de
salida y pasaremos a realizar un análisis de los mismos. Algunas de las variables de entrada son de
tipo aleatorio por lo que se tendrán que generar valores que simulen dichas entradas. Para generar
variables aleatorias que sigan determinadas funciones de probabilidad necesitamos partir de series de
números que cumplan ciertas características de aleatoriedad. La generación de dichos números es lo
que se va a abordar en este tema.
3.1.- Introducción
Es grande la necesidad de usar números aleatorios y son muchas las aplicaciones que
requieren de ellos, tales como:
· Simulación: para simular las entradas de aquellas variables aleatorias (no
determinísticas).
· Juegos o teoría de decisiones.
· Cálculo numérico: por ejemplo en la resolución de integrales.
· Teoría del muestreo: aquellos casos en los que sea demasiado costoso realizar la
muestra.
· Programación: generación de entradas para realizar las pruebas de los algoritmos y
programas.
Antes se ha hecho referencia a “número aleatorio”, en realidad no se puede hablar de la
aleatoriedad o no aleatoriedad de un número aislado, sino de éste en relación con otros, es decir, la
aleatoriedad es una característica que posee o no una serie de números. A partir de esta aclaración
Generación de números aleatorios
52
siempre que nos refiramos a un número aleatorio estaremos hablando de un número perteneciente a
una serie aleatoria.
3.2.- Generadores de números. Tipos
Las características deseables para los generadores de números aleatorios son las siguientes:
· Los números generados no se deben repetir frecuentemente (en ciclos).
· Las series generadas deben ser reproducibles.
· Rapidez en la obtención de los números.
· Almacenamiento mínimo. Tanto el propio generador como los números por el
generados.
· Los números generados han de estar uniformemente distribuidos (todos deben tener la
misma probabilidad de salir).
· Los valores generados deben ser independientes unos de otros, es decir, que la
obtención de cierto valor no esté condicionado por los valores obtenidos anteriormente.
Vamos a ver distintos métodos y para cada uno evaluaremos cuáles de las características
descritas arriba cumple y cuáles no.
1) Manual. Por ejemplo , lanzar un dado o realizar extracciones con reemplazamiento de
bolas numeradas dentro de una urna.
Ventajas:
- Las series obtenidas son realmente aleatorias.
Inconvenientes:
- Lentitud.
- Las series obtenidas son irreproducibles.
- Requieren gran cantidad de almacenamiento ya que habría que almacenar la serie
obtenida.
2) Tablas. (De hasta 100000 números).
Ventajas:
- Las series obtenidas son reproducibles.
Inconvenientes:
- Lentitud.
- Requieren gran cantidad de almacenamiento.
Generación de números aleatorios
53
3) Computación analógica. Las series se obtienen mediante fenómenos físicos.
Ventajas:
- Las series obtenidas son realmente aleatorias.
- Rapidez.
Inconvenientes:
- Las series obtenidas son irreproducibles.
4) Computación digital. Dada una función y una semilla, se van generando los números
aleatorios.
Ventajas:
- Rapidez.
- Pocos requerimientos de almacenamiento.
- Las series obtenidas son reproducibles.
Inconvenientes:
- Los números obtenidos no son independientes.
Nosotros, nos vamos a centrar en la utilización de éstos últimos. Por tanto, vamos a entender
por Generador de números aleatorios, un código al que vamos a llamar cada vez que necesitemos una
aproximación a un número aleatorio.
En 1946, Von Neumann propuso un método para obtener números aleatorios de k-cifras, a
partir de una semilla. Dicho método es conocido como Método de los cuadrados centrales.
El método consiste en partir de una semilla y elevarla al cuadrado, el siguiente número de la
serie se obtendría como resultado de extraer las k-cifras centrales del cuadrado obtenido y así
sucesivamente.
El problema que presenta este método es que los ciclos se producen rápidamente.
3.3.- Generadores congruenciales lineales
Nos vamos, pues, a centrar en los métodos de computación digital. A los números obtenidos
mediante dichos métodos se les conoce como números pseudoaleatorios, dado que, como se ha
mencionado más arriba, los números obtenidos están uniformemente distribuidos pero no son
independientes. Vamos a generar números uniformemente distribuidos en el intervalo (0,1) (U(0,1)),
dado que es fácil pasar desde ellos a otros que estén en otro intervalo.
Generación de números aleatorios
54
3.3.1.- Introducción
Hacia 1949, Lehmer introduce un método de generación de números aleatorios mediante el
cual un término de la serie se obtiene como función del término inmediatamente anterior (xn=f(xn-1)).
La función aplicada es la siguiente:
x ax c m siendo x m n n n n = + £ < " + ( ) mod , 0 1
En el generador distinguimos cuatro elementos:
· x0, es el valor inicial o semilla.
· a, multiplicador, siendo 0 £ a < m.
· c, incremento, siendo 0 £ a < m.
· m, módulo.
Se llama periodo a la subcadena, dentro de la serie generada, en la que no hay repeticiones de
números y longitud de periodo al número de elementos de dicha subcadena.
La repetición de números en la serie puede ser aleatoria, pero dado el método utilizado para la
generación de las mismas, en el momento en el que se repite un valor ya empieza a repetirse todo el
periodo, por lo que interesan métodos que garanticen longitudes de periodo grandes.
3.3.2.- Tipos de Generadores congruenciales lineales
Podemos distinguir dos tipos de estos generadores que se diferencian en el valor del
incremento.
· G.C. Multiplicativos. En ellos el incremento, c, es 0. Este tipo de generadores fueron los
introducidos por Lehmer, aunque mencionó como posibilidad la idea de tomar c¹0.
x ax m n n mod 1 = +
· G.C. Mixtos. En ellos el incremento es distinto de 0. Fueron introducidos por Thomson
hacia 1958.
x ax c m n n ( ) mod 1 = + +
Los primeros presentan la ventaja de ser más rápidos, al tener que realizar menos operaciones
en el cálculo de los elementos. Sin embargo, la longitud de periodo que se alcanza en las series
generadas por ellos son menores que la alcanzadas en las series generadas por los segundos.
Los valores de a=0 y a=1, producen series no aleatorias.
Supongamos a=0, nos quedaría el generador de la forma x c m n mod 1 = + , es decir, que
siempre saldría la constante c.
Si a=1, el generador es x x c m n n ( ) mod 1 = + + .Desarrollando algunos de los elementos que se
van obteniendo, tenemos:
Generación de números aleatorios
55
x (x c) mod m 1 0 = +
x (x c) mod m ((x c) mod m) mod m (x 2c) mod m 2 1 0 0 = + = + = +
x (x 3c) mod m 3 0 = +
y así para todos los términos. Vamos obteniendo que un término es siempre la semilla más un múltiplo
de c y todo módulo m, y esta serie no es aleatoria.
Puede interesarnos dotar de más independencia a los valores obtenidos. Esto lo podemos
conseguir no obteniendo todos los valores consecutivos de una serie sino obteniendo valores de k en k
posiciones, es decir a partir de un elemento xn no obtenemos el elemento xn+1 sino el elemento xn+k.
Para ello tendremos que elegir:
x0
’=x0
a’=ak
c
a
a
c
k
1
1
'
-
-
=
m’=m
Demostración: tenemos que x ax c m n n ( ) mod 1 = + + , obteniendo nuevos
términos: x ax c m a ax c m c m a x ac c m n n n n ( ) mod (( ( )mod ) )mod ( 2 )mod
2 1 = + = + + = + + + +
a x a x ac c m
x ax c m a a ax c m c m c m
n n
n n n
( )mod
( ) mod (( ( ( )mod ) )mod ) )mod
3 2
3 2
= + + +
= + = + + + = + +
En general
x a x ak c ak c ac c m
n
k
n k = ( + -1 + -2 + + + )mod
+ L , operando queda : c m
a
a
x a x
k
n
k
n k )mod
1
1
(
-
-
= + + ,
Esto también se puede utilizar para paralelizar la obtención de los términos. Si tenemos un
ordenador con procesamiento paralelo, podemos, partiendo de la semilla asignar a cada procesador la
generación de una subsecuencia de términos. Por ejemplo con tres procesadores se irían generando los
términos de la siguiente forma:
x0
x1 x2 x3
x4 x5 x6 .........................
Generación de números aleatorios
56
Así a partir de un número
...