METODOS GENERADORES DE NUMEROS ALEATORIOS

METODOS CONGRUENCIALES

Un Generador de números aleatorios es un componente o funcionalidad que crea números o símbolos para un programa software en una forma que carezca de un patrón evidente, y que así parezcan ser números aleatorios.

La mayor parte de los generadores de números aleatorios son, en realidad, pseudoaleatorios: se calcula (o introduce internamente) un valor X0, que llamaremos semilla, y, a partir de él, se van generando X1, X2, X3, ...

Siempre que se parta de la misma semilla, se obtendrá la misma secuencia de valores.

El algoritmo básico es el método congruencial123, que genera valores en el intervalo [0,1), mediante el siguiente esquema: Se fijan A, B, enteros positivos (deben tener ciertas propiedades para obtener un buen generador), y, a partir de una semilla X0 en el conjunto 0,1,...,(N-1), se generan X1 = A*X0+B (mod N) X2 = A*X1+B (mod N) X3 = A*X2+B (mod N) ... X(k+1) = A*Xk+B (mod N) ...

donde A*X+B (mod N) es el resto de la división entera de A*X+B entre N. Por ejemplo, 16 (mod 7) es 2.

A partir del método congruencial, es posible tomar valores pseudoaleatorios en el intervalo [0,1) como sigue: Se toma N, entero, muy grande, se toman A, B adecuados, y una semilla X0 en 0,1,..,(N-1). A partir de ella, se generan X1,X2,X3,... por el método congruencial, y a partir de ellos, Y0,Y1,Y2,Y3,... mediante la fórmula Yk = Xk /N

El método base es el método congruencial de generación de números en el conjunto

Para ello, se toman A,B enteros adecuados, se indica un valor inicial (semilla) X₀ en el conjunto , y se aplica el esquema recursivo

, , ,...,

donde por XmodN indica el resto de la división entera de X entre N. Por ejemplo, 12mod7 = 5

Si se conoce cómo generar valores en es posible generar valores en el intervalo [0,1), como sigue: Se toma N, muy grande, entero, se toma una semilla , y se construye la secuencia obtenida aplicando la expresión Y_k = X_k / N

METODOS ADITIVOS

Hasta ahora hemos visto generadores que producían números en los que cada término depende

del anterior. Ahora vamos a ver otro tipo de generadores en los que para generar un nuevo término se

utilizan dos elementos anteriores.

En este caso la longitud máxima de periodo que se puede alcanzar es mayor, dado que para

que se produzca un ciclo es necesario que se repitan parejas de números.

2

1 1longitud máx ima de periodo m

x x

x x

n n k

n n k Þ =

þ ý ü

=

=

- - +

+

El primer generador de este tipo fue creado en los años 1950 y es la sucesión de Fibonacci:

x x x m n n n ( )mod 1 1 = + + -

Ofrece una longitud de periodo mayor que m, pero los test han demostrado que los números

producidos no son satisfactoriamente aleatorios.

Green introdujo el siguiente generador:x x x m n n n k ( ) mod +1 - = +

Demostró que para k£15 dicho generador no pasaba bien los test de aleatoriedad pero que para

k³16 sí se portaba bien.

Mitchell y Moore (1958) introdujeron el siguiente generador:

( ) mod ; 55 1 24 55 = + ³ + - - x x x m n n n n

Se ha de cumplir:

Generación de números aleatorios

61· m debe ser par.

· Se han de generar de forma aleatoria 55 semillas, desde x0 hasta x54, de forma que todos

ellas no sean pares.

Este método tiene una longitud de periodo grande y al ser simplemente aditivo y no utilizar

multiplicadores, es rápido.

METODOS MIXTOS

Estos métodos generan series de números aleatorios a partir de otras dos series:

Z X Y m n n n = ( + ) mod .

Sea L1 la longitud de periodo de la serie Xn (Lp(Xn)) y L2 la longitud de periodo de la serie Yn,

si se cumple que mcd(L1 , L2)=±1Þ (Lp(Zn))= L1*L2.

Utilizando este método el hecho de que se repita un número no implica que la serie empiece a

ciclar, tal y como ocurría con los G.C.L., ya que ahora interviene otro número de otra serie.

No es conveniente utilizar el mismo método para generar las dos series de partida.