Generadores de números aleatorios Y pruebas

Números pseudoaleatorios
Un número pseudo-aleatorio es un número generado en un proceso que parece producir números al azar, pero no lo hace realmente. Las secuencias de números pseudo-aleatorios no muestran ningún patrón o regularidad aparente desde un punto de vista estadístico, a pesar de haber sido generadas por un algoritmo completamente determinista, en el que las mismas condiciones iniciales producen siempre el mismo resultado.

Los generadores de números pseudoaleatorios son ampliamente utilizados en campos tales como el modelado por computadora, estadística, diseño experimental, etc. Algunas de estas secuencias son lo suficientemente aleatorias para ser útiles en estas aplicaciones.

Una de las utilidades principales de los números pseudoaleatorios tiene lugar en el campo de la criptografía. Por ello se sigue investigando en la generación de dichos números, empleando por ejemplo medidores de ruido blanco o analizadores atmosféricos, ya que experimentalmente se ha comprobado que tienen una aleatoriedad bastante alta.

Asimismo, también destacan su uso en el llamado método de Montecarlo, con múltiples utilidades, por ejemplo para hallar áreas / volúmenes encerradas en una gráfica y cuyas integrales son muy difíciles de hallar o irresolubles; mediante la generación de puntos basados en estos números, podemos hacer una buena aproximación de la superficie /volumen total , encerrándolo en un cuadrado / cubo , aunque no lo suficientemente buena.

Un generador pseudoaleatorio de números (GPAN) es un algoritmo que produce una sucesión de números que es una muy buena aproximación a un conjunto aleatorio de números. La sucesión no es exactamente aleatoria en el sentido de que queda completamente determinada por un conjunto relativamente pequeño de valores iniciales, llamados elestado del GPAN. Si bien es posible generar sucesiones mediante generadores de números aleatorios por dispositivos mecánicos que son mejores aproximaciones a una sucesión aleatoria, los números pseudo-aleatorios son importantes en la práctica para simulaciones (por ejemplo, de sistemas físicos mediante el método de Montecarlo), y desempeñan un papel central en la criptografía.

Para la uniformidad

• Bondad de ajuste o chi-cuadrada: X²
• Bondad de ajuste Kolmogorov-Smirnov

Para la aleatoriedad o independencia

• Corridas por arriba y por abajo del promedio
• Corridas ascendentes y descendentes

PRUEBA DE BONDAD DE AJUSTE CHI CUADRADA.

Procedimiento:

1. Generar la muestra de números aleatorios de tamaño N.

2. Subdividir el intervalo [0,1] en n subintervalos.

3. Para cada subintervalo contar la frecuencia observada F0 y calcular la frecuencia esperada FE de números aleatorios, la cual se obtiene dividiendo N/n.

4. Calcular el estadístico de prueba.

5. Comparar el valor calculado X0² contra el valor tabulado de la distribución X², con (n-1) grados de libertad y una significancia ?. Si X0² es menor que X²(n-1),? entonces no se puede rechazar la uniformidad de los números aleatorios.

EJEMPLO 4. Realizar la prueba de bondad de ajuste chi-cuadrada a la siguiente muestra de tamaño 30 de números aleatorios uniformes

0.15	0.31	0.81	0.48	0.01	0.60
0.26	0.34	0.70	0.31	0.07	0.06
0.33	0.49	0.77	0.04	0.43	0.92
0.25	0.83	0.68	0.97	0.11	0.00
0.18	0.11	0.03	0.59	0.25	0.55

INTERVALO	FE	FO	(FE-FO)2/FE
0.00 - 0.20	6	10	2.67
0.21 - 0.40	6	7	0.17
0.41 - 0.60	6	6	0.00
0.61 - 0.80	6	3	1.50
0.81 - 1.00	6	4	0.67
			X20=5.01

Sea alfa= 5%. Tenemos (5-1) grados de libertad, es decir V=4. El valor en tablas de la distribución Ji cuadrada es:

X²_4.5% = 9.49

Como X0² es menor que X²_4.5% es decir; 5.01 es menor que 9.49. entonces no se puede rechazar la uniformidad de los números aleatorios.

PRUEBA DE BONDAD DE AJUSTE DE KOLMOGOROV-SMIRNOV

Procedimiento

1. Generar una muestra de números aleatorios uniformes de tamaño N.

2. Ordenar dichos números en orden ascendente.

3. Calcular la distribución acumulada de los números generados con la siguiente 
expresión

Donde i es la posición que ocupa el número aleatorio Xi en el vector ordenado obtenido en el paso 2.

4. Calcular el estado de prueba Kolmogorov-Smirnov del modo siguiente

D_n = máx | F_n (X_i) – X_i | para toda X_i

5. Si D_n es menor d_alfa,n, entonces no se puede rechazar la hipótesis de que los números generados provienen de una distribución uniforme. La distribución de D_nha sido tabulada como una función de n y alfa para cuando F_n (x) = F₀ (x).

EJEMPLO 5. Efectuar la prueba de Kolmogorov – Smirnov a la siguiente muestra de números aleatorios uniformes.

0.15	0.31	0.81	0.48	0.01	0.60
0.26	0.34	0.70	0.31	0.07	0.06
0.33	0.49	0.77	0.04	0.43	0.92
0.25	0.83	0.68	0.97	0.11	0.00
0.18	0.11	0.03	0.59	0.25	0.55

Sustituyendo los valores en las fórmulas correspondientes se tiene que:

i	RNDi	F(RNDi)	RNDi- F (RNDi)
1	0.00	0.03	0.03
2	0.01	0.07	0.06
3	0.03	0.10	0.07
4	0.04	0.13	0.09
5	0.06	0.17	0.11
6	0.07	0.20	0.13
7	0.11	0.23	0.12
8	0.11	0.27	0.16
9	0.15	0.30	0.15
10	0.18	0.33	0.15
11	0.25	0.36	0.11
12	0.25	0.40	0.15
13	0.26	0.43	0.17
14	0.31	0.47	0.16
15	0.33	0.50	0.17
16	0.34	0.53	0.19
17	0.34	0.57	0.23
18	0.43	0.60	0.17
19	0.48	0.63	0.15
20	0.49	0.67	0.18
21	0.55	0.70	0.15
22	0.59	0.73	0.14
23	0.60	0.77	0.17
24	0.68	0.80	0.12
25	0.70	0.83	0.13
26	0.77	0.87	0.1
27	0.81	0.90	0.09
28	0.83	0.93	0.1
29	0.92	0.97	0.05
30	0.97	1.00	0.03

siguiendo con el paso 4

Dn = Max |RNDi – F(RNDi)| = 0.23

Comparamos el valor Dn (calculado) contra el valor en tablas de la distribución Kolmogorov-Smirnov con n = 30 y un nivel de significancia alfa = 5%, el cual es d_30.5% = 0.242. como 0.23 es menor que 0.242, entonces, no se puede rechazar la uniformidad de los números aleatorios.

CORRIDAS POR ARRIBA Y POR ABAJO DEL PROMEDIO

Procedimiento

Generar la muestra de tamaño N de números aleatorios.

Con base en esta muestra, obtener una nueva sucesión binaria, según el criterio siguiente:

Si r_j es menor o igual a 0.50 entonces asignarle a r_j el símbolo 0.

Si r_j es mayor a 0.50 entonces asignarle a r_j el símbolo 1.

La frecuencia esperada para cada longitud de corrida i, es:

EJEMPLO 6. Dada la siguiente muestra de tamaño 30 de números aleatorios, aplicar la prueba de corridas, para la independencia

0.15	0.31	0.81	0.48	0.01	0.60
0.26	0.34	0.70	0.31	0.07	0.06
0.33	0.49	0.77	0.04	0.43	0.92
0.25	0.83	0.68	0.97	0.11	0.00
0.18	0.11	0.03	0.59	0.25	0.55

Comparando los números aleatorios según el criterio establecido, se obtiene la siguiente sucesión binaria. Leyendo de izquierda a derecha se agrupan los símbolos del mismo tipo para formar las corridas.

0	0	1	0	0	1
0	0	0	1	0	0
0	0	1	0	0	1
0	1	1	1	0	0
0	0	0	1	0	1

En la siguiente tabla se resume la información necesaria para el cálculo de la Ji-cuadrada

Longitud de corrida i	FE	FO	(FE-FO)2/FE
1	8.000	9	0.125
2	3.875	3	0.197
3	1.875	2	0.008
4	0.906	1	0.010
5	0.438	1	0.721

Como para las longitudes de corrida i = 2, 3, 4, 5; las frecuencias observadas son menores o igual a cinco, agrupamos estas longitudes de corridas en una sola longitud de corrida ? 2.

i	FE	FO	(FE-FO)2/FE
1	8	9	0.125
>=2	7.04	7	0.936
			X02 = 1.061

El valor en tablas de X²_1.5%= 3.84; entonces no se puede rechazar la independencia de los números aleatorios.

CORRIDAS ASCENDENTES Y DESCENDENTES

Procedimiento

1. Generar la muestra de tamaño N de números aleatorios.
2. Construir la sucesión binaria de acuerdo al siguiente criterio:

Si rj es menor o igual a r_j+1 entonces asignarle a r_j el símbolo 0.
Si rj es mayor que r_j+1 entonces asignarle a r_j el símbolo 1.

3. Con base en la distribución X², efectuar la prueba, donde la frecuencia esperada de las longitudes de corrida i se calculará con:

EJEMPLO 7. Aplicar la prueba de las corridas ascendentes y descendentes a la muestra de números aleatorios del ejemplo anterior. Compararemos a los números por fila, pero es indistinto hacerlo por columna.

0.15	0.31	0.81	0.48	0.01	0.60
0.26	0.34	0.70	0.31	0.07	0.06
0.33	0.49	0.77	0.04	0.43	0.92
0.25	0.83	0.68	0.97	0.11	0.00
0.18	0.11	0.03	0.59	0.25	0.55

ahora la sucesión binaria es

0	0	1	1	0	1
0	0	0	1	1	0
0	0	1	0	1	1
0	1	0	1	1	0
1	1	0	1	0

obsérvese que la última celda se deja en blanco, pues no hay con que número comparar. (aquí N = 29)

Longitud de corrida i	FE	FO	(FE-FO)2/FE
1	11.500	11	0.020
2	5.083	5	0.001
3	1.400	2	0.257
4	0.292	-
5	0.005	-

i	FE	FO	(FE-FO)2/FE
1	11.500	11	0.020
>=2	6.483	7	0.004
			X02 = 0.024

como el valor calculado de 0.024 es menor que el valor en tablas de Ji-cuadrada X²_1.5%= 3.84, no se puede rechazar la independencia de los números aleatorios.

  APLICACIÓN DE LAS PRUEBAS PARA VERIFICACIÓN DE NÚMEROS ALEATORIOS