Generación de números aleatorios

Carlos Javier Uribe Martes

Ingenierı́a Industrial
Universidad de la Costa

Febrero 11, 2020

C.J. Uribe-Martes (CUC) Generación de números aleatorios 1/36

Contenido

1 Propiedades de los números aleatorios

2 Técnicas de generación de números aleatorios

3 Pruebas estadı́sticas para números aleatorios

Pruebas de uniformidad
Pruebas de independencia

C.J. Uribe-Martes (CUC) Generación de números aleatorios 2/36

 Propiedades

Introducción

Para desarrollar un modelo de simulación el ingrediente fundamental

es la generación de una secuencia de números aleatorios
R1 , R2 , . . . , Rn [1].

C.J. Uribe-Martes (CUC) Generación de números aleatorios 3/36

 Propiedades

Propiedades de los números aleatorios

Cada número aleatorio Ri debe ser una muestra independiente

obtenida de una distribución uniforme continua entre cero y uno [1].

C.J. Uribe-Martes (CUC) Generación de números aleatorios 4/36

 Propiedades

Propiedades de la distribución uniforme [0, 1]


1, 0 ≤ x ≤ 1
f (x) = ; E(R) = 12 ; V (R) = 1
12
0, de lo contrario

Figura: Función de densidad de Figura: Función de probabilidad

probabilidad acumulada

C.J. Uribe-Martes (CUC) Generación de números aleatorios 5/36

 Técnicas de generación

Generación de números pseudo-aleatorios

Generar números aleatorios a través de un algoritmo remueve la

verdadera aleatoriedad, toda vez que el patrón puede ser repetido [1].
Se busca generar una secuencia de números que imite las propiedades
de los números aleatorios [1].

C.J. Uribe-Martes (CUC) Generación de números aleatorios 6/36

 Técnicas de generación

Técnicas para generación de números aleatorios

Una técnica adecuada debe tener las siguientes caracterı́sticas:

Eficiencia [3].
Periodo máximo [3].
Secuencia reproducible [3].
Portabilidad [2].

C.J. Uribe-Martes (CUC) Generación de números aleatorios 7/36

 Técnicas de generación

Cuadrados medios de Von Neumann y Metropolis

1 Seleccione una semilla X0 con D dı́gitos (D > 3).

2 Sea Y0 el resultado de elevar X0 al cuadrado, defina X1 igual a los D
dı́gitos del centro de Y0 y sea R1 = 0.X1 .
3 Sea Yi el resultado de elevar Xi al cuadrado, defina Xi+1 igual a los
D dı́gitos del centro de Yi y sea Ri+1 = 0.Xi+1 .

C.J. Uribe-Martes (CUC) Generación de números aleatorios 8/36

 Técnicas de generación

Generador congruencial lineal

Utiliza la siguiente relación recursiva

Xi+1 = (aXi + c) mód m, i = 0, 1, 2, . . .

El valor inicial X0 es llamado semilla, a es el multiplicador, c es el

incremento y m el módulo, todos enteros no negativos.
Para obtener Ri emplee:
Xi
Ri = , i = 1, 2, . . .
m

C.J. Uribe-Martes (CUC) Generación de números aleatorios 9/36

 Técnicas de generación

Generador congruencial lineal

Los valores de a, c, m y X0 afectan directamente las propiedades

estadı́sticas y el periodo de la secuencia generada [1].
Deben satisfacerse las siguientes relaciones:
a<m
c<m
m>0
X0 < m
La secuencia se repetirá con periodo p ≤ m, por lo que el generador
alcanza el periodo máximo cuando p = m

C.J. Uribe-Martes (CUC) Generación de números aleatorios 10/36

 Técnicas de generación

Generador congruencial multiplicativo

Si el incremento c = 0, se denomina método congruencial

multiplicativo.
No alcanza el periodo máximo ya que la secuencia no contendrá
Xi = 0, sin embargo pueden llegar a alcanzar el periodo m − 1 si se
seleccionan m y a en forma adecuada [3]:
m ha de ser un número primo.
a ha de ser raı́z primitiva de m, es decir,

an mód m 6= 1 n = 1, . . . , m − 2

C.J. Uribe-Martes (CUC) Generación de números aleatorios 11/36

 Técnicas de generación

Generador congruencial multiplicativo

La siguiente tabla indica los parámetros evaluados por Fishman y

Moore (1986) que tienen buen comportamiento [3].
Parámetros Fishman y Moore
a 48.271
m 231 − 1

C.J. Uribe-Martes (CUC) Generación de números aleatorios 12/36

 Técnicas de generación

Generador congrencial mixto

Si el incremento c 6= 0, se denomina método congruencial mixto.

Las siguientes condiciones aseguran que el generador congruencial
mixto tendrá periodo máximo [2, 3]:
1 El único entero positivo que divide a m y a c es 1, es decir, son primos
entre sı́.
2 Si q es un número primo que divide a m, entonces q también divide a
a − 1.
3 Si 4 divide a m, entonces 4 también divide a a − 1.

C.J. Uribe-Martes (CUC) Generación de números aleatorios 13/36

 Técnicas de generación

Generadores congrenciales mixtos

La siguiente tabla indica los generadores congruenciales lineales

mixtos propuestos por Coveyou y MacPherson (1967) y por
Kobayashi (1978) [3].
Parámetros Kobayashi Coveyou y MacPherson
a 314.159.269 515
c 453.806.245 1
m 231 2 35

C.J. Uribe-Martes (CUC) Generación de números aleatorios 14/36

 Técnicas de generación

Métodos congruenciales NO lineales

Algoritmo congruencial cuadrático: Emplea la relación recursiva:

Xi+1 = aXi2 + bXi + c

mód m, i = 0, 1, 2, . . .

Algoritmo de Blum, Blum y Shub: Es similar al algoritmo

congruencial cuadrático, con a = 1, b = 0, c = 0, entonces la relación
recursiva es:

Xi+1 = Xi2 mód m, i = 0, 1, 2, . . .

C.J. Uribe-Martes (CUC) Generación de números aleatorios 15/36

 Técnicas de generación

Combinación de generadores congruenciales lineales

Una manera de conseguir secuencias aleatorias con periodos más

largos es combinar dos o más generadores congruenciales
multiplicativos.

C.J. Uribe-Martes (CUC) Generación de números aleatorios 16/36

 Técnicas de generación

Generador de Wichmann-Hill

Consiste en tres generadores congruenciales lineales con módulos

primos. Cada uno es utilizado para producir un aleatorio entre 0 y 1.
Estos tres resultados se suman, módulo 1, para obtener el resultado
final.
1 xi = 171xi−1 mód 30269
2 yi = 172yi−1 mód 30307
3 zi = 
170zi−1 mód 30323
xi yi zi 
4 ri = + + mód 1
30269 30307 30323

C.J. Uribe-Martes (CUC) Generación de números aleatorios 17/36

 Técnicas de generación

MRG32k3a de L’Ecuyer

Consiste en dos generadores congruenciales recursivos de tercer orden.

Estos se combinan para obtener un nuevo aleatorio en cada iteración.


1 xi = (1403580xi−2 − 810728xi−3 ) mód 232 − 209

2 yi = (527612yi−1 − 1370589yi−3 ) mód 232 − 22853


3 zi = (xi − yi ) mód 232 − 209
zi
4 ri = 32
2 − 209

C.J. Uribe-Martes (CUC) Generación de números aleatorios 18/36

 Pruebas estadı́sticas

Pruebas para números aleatorios

Para verificar si las propiedades deseadas de un conjunto de números

aleatorios diferentes tipos de pruebas pueden desarrollarse.
Para cada prueba debe definirse un nivel de significancia α, el cual
representa la probabilidad de rechazar la hipótesis nula cuando ésta es
cierta:
α = P (rechazar H0 |H0 es cierta)

C.J. Uribe-Martes (CUC) Generación de números aleatorios 19/36

 Pruebas estadı́sticas Pruebas de uniformidad

Prueba de medias

Busca comprobar que el valor esperado de los números en la

secuencia Ri sea igual a 0.5 mediante las siguientes hipótesis:

H0 : µRi = 0,5
H1 : µRi 6= 0,5

C.J. Uribe-Martes (CUC) Generación de números aleatorios 20/36

 Pruebas estadı́sticas Pruebas de uniformidad

Prueba de medias

1 Determine el promedio de los n números aletorios de la secuencia:

n
1X
R̄ = Ri
n
i=1

2 Calcule los lı́mites de aceptación inferior y superior:

 
1 1
LIR̄ = − zα/2 √
2 12n
 
1 1
LSR̄ = + zα/2 √
2 12n

3 Si el valor de R̄ está dentro de los lı́mites de aceptación no hay

evidencia suficiente para rechazar H0 con un nivel de confianza 1-α.

C.J. Uribe-Martes (CUC) Generación de números aleatorios 21/36

 Pruebas estadı́sticas Pruebas de uniformidad

Prueba de varianza

Busca determinar si la varianza de la secuencia aleatoria generada es

igual a 1/12 mediante las siguientes hipótesis:

2 1
H0 : σR i
=
12
2 1
H1 : σR i
6 =
12

C.J. Uribe-Martes (CUC) Generación de números aleatorios 22/36

 Pruebas estadı́sticas Pruebas de uniformidad

Prueba de varianza
1 Determine la varianza muestral de la secuencia R1 , R2 , . . . , Rn :
n
X
(Ri − R̄)2
i=1
V (R) =
n−1
2 Calcule los lı́mites de aceptación inferior y superior mediante:

χ2α ,n−1
2
LIV (R) =
12(n − 1)
χ2(1−α)
2
,n−1
LSV (R) =
12(n − 1)

3 Si el valor de V (R) está dentro de los lı́mites de aceptación no hay

evidencia suficiente para rechazar H0 con un nivel de confianza 1-α.
C.J. Uribe-Martes (CUC) Generación de números aleatorios 23/36
 Pruebas estadı́sticas Pruebas de uniformidad

Prueba de frecuencias

Trata de determinar si el conjunto de números generados se distribuye

de acuerdo con la distribución uniforme [0, 1] para lo cual formula las
siguientes hipótesis:

H0 : Ri ∼ U [0, 1]
H1 : Ri 6∼ U [0, 1]

C.J. Uribe-Martes (CUC) Generación de números aleatorios 24/36

 Pruebas estadı́sticas Pruebas de uniformidad

Prueba de frecuencias
Prueba chi-cuadrado

Para la distribución uniforme, la frecuencia esperada en cada clase, Ei

está dada por:
N
Ei =
n
para n clases igualmente espaciadas, donde N es el número total de
observaciones.
Utiliza el estadı́stico de prueba:
n
X (Oi − Ei )2
χ20 =
Ei
i=1

donde Oi es la frecuencia observada en la i-ésima clase.

C.J. Uribe-Martes (CUC) Generación de números aleatorios 25/36

 Pruebas estadı́sticas Pruebas de uniformidad

Prueba de frecuencias
Prueba chi-cuadrado

La distribución muestral de χ20 es aproximadamente chi-cuadrado con

n − 1 grados de libertad.
Si el estadı́stico de prueba χ20 es menor que el valor χ2α,n−1 no hay
evidencia suficiente para rechazar H0 con un nivel de confianza 1-α.

C.J. Uribe-Martes (CUC) Generación de números aleatorios 26/36

 Pruebas estadı́sticas Pruebas de uniformidad

Prueba de frecuencias
Prueba Kolmogorov-Smirnov

Contrasta la función de densidad acumulada F (x) de la distribución

teórica con la función de densidad empı́rica SN (x) de la muestra de
N obsevaciones.
Se basa en la mayor desviación absoluta entre F (x) y SN (x) en el
rango de la variable aleatoria, utilizando el estadı́stico de prueba:

D = max|F (x) − SN (x)|

C.J. Uribe-Martes (CUC) Generación de números aleatorios 27/36

 Pruebas estadı́sticas Pruebas de uniformidad

Prueba de frecuencias
Prueba Kolmogorov-Smirnov

1 Ordene los datos de menor a mayor. Sea R(i) la i-ésima menor

observación.
2 Determine los valores:
 
+ i
D = max1≤i≤N − R(i)
N
 
− i−1
D = max1≤i≤N R(i) −
N

3 Calcule D = max(D+ , D− ).
4 Identifique el valor crı́tico Dα correspondiente a α y N .
5 Si D ≤ Dα se concluye que no hay evidencia suficiente para rechazar
H0 con un nivel de confianza 1-α.

C.J. Uribe-Martes (CUC) Generación de números aleatorios 28/36

 Pruebas estadı́sticas Pruebas de independencia

Pruebas de independencia

En su mayorı́a buscan probar la independencia de los números de un

conjunto Ri mediante las hipótesis:

H0 : los números del conjunto Ri son independientes

H1 : los números del conjunto Ri no son independientes

C.J. Uribe-Martes (CUC) Generación de números aleatorios 29/36

 Pruebas estadı́sticas Pruebas de independencia

Prueba de corridas arriba y abajo

1 Determine una secuencia de unos y ceros ası́: si Ri+1 ≤ Ri asigne un

cero a la secuencia, de lo contrario asigne un uno.
2 Defina C0 como el número de corridas en la secuencia (una corrida es
cualquier cantidad de unos o ceros consecutivos).
3 Determine el estadı́stico de prueba mediante las ecuaciones:
2n − 1
µC0 =
3
2 16n − 29
σC 0
=
 90 
 C0 − µC0 
Z0 =  
σC 
0

4 Si el estadı́stico Z0 es mayor que el valor crı́tico de Zα/2 , se concluye

que los números del conjunto Ri no son independientes.

C.J. Uribe-Martes (CUC) Generación de números aleatorios 30/36

 Pruebas estadı́sticas Pruebas de independencia

Prueba de corridas arriba y abajo de la media

1 Determine una secuencia de unos y ceros ası́: si Ri ≤ 0,5 asigne un

cero a la secuencia, de lo contrario asigne un uno.
2 Defina C0 como el número de corridas en la secuencia, n0 el número
de ceros de ceros y n1 el número de unos.
3 Determine el estadı́stico de prueba mediante las ecuaciones:
2n0 n1
µC0 = + 0,5
n
2 2n0 n1 (2n0 n1 − n)
σC =
0
n2 (n − 1)
C0 − µC0
Z0 =
σC0
 
4 Si el estadı́stico Z0 está fuera del intervalo −Zα/2 , Zα/2 se concluye
que los números del conjunto Ri no son independientes.
C.J. Uribe-Martes (CUC) Generación de números aleatorios 31/36
 Pruebas estadı́sticas Pruebas de independencia

Prueba de autocorrelación

Prueba la correlación entre los números generados y compara la

correlación muestral con la correlación esperada de cero.
Requiere el cálculo de la autocorrelación entre cada m números
(siendo conocida m como lag o retraso), empezando con el i-ésimo
número de la secuencia.
La autocorrelación ρim entre los siguientes números será de interés
Ri , Ri+m , Ri+2m , . . . , Ri+(M +1)m . Donde el valor de M es el entero
más grande tal que i + (M + 1)m ≤ N ,

C.J. Uribe-Martes (CUC) Generación de números aleatorios 32/36

 Pruebas estadı́sticas Pruebas de independencia

Prueba de autocorrelación

Una autocorrelación diferente de cero implica una falta de

independencia en los datos. La siguiente prueba con dos colas es
adecuada:

H0 : ρim = 0
H1 : ρim 6= 0

Para valores grandes de M , la distribución del estimador de ρim ,

denotado ρ̂im , es aproximadamente normal si los valores Ri ,
Ri+m , Ri+2m , . . . , Ri+(M +1)m no están correlacionados.

C.J. Uribe-Martes (CUC) Generación de números aleatorios 33/36

 Pruebas estadı́sticas Pruebas de independencia

Prueba de autocorrelación

El estadı́stico:
ρ̂im
Z0 =
σρ̂im
está normalmente distribuido con media 0 y varianza 1, bajo el
supuesto de independencia y para valores grandes de M .
Donde
"M #
1 X
ρ̂im = Ri+km Ri+(k+1)m − 0,25
M +1
k=0
√
13M + 7
σρ̂im =
12(M + 1)

No rechace H0 si −zα/2 ≤ Z0 ≤ zα/2 donde zα/2 se puede obtener de

la tabla de probabilidades para la distribución chi-cuadrado.

C.J. Uribe-Martes (CUC) Generación de números aleatorios 34/36

 Referencias

Referencias

Banks, J., Carson II, J. S., Nelson, B. L. y Nicol, D. M.

Discrete-Event System Simulation. Fifth (Pearson, 2014).
Law, A. M. Simulation modeling and analysis. Fifth (McGraw-Hill,
2015).
Pazos Arias, J. J., Suárez González, A. y Dı́az Redondo, R. Teorı́a de
colas y simulación de eventos discretos. (Prentice Hall, 2003).

C.J. Uribe-Martes (CUC) Generación de números aleatorios 35/36

C.J. Uribe-Martes (CUC) Generación de números aleatorios 36/36