Herramientas
Librería de generación de números aleatorios - random (python)
Como librería para generar números escogí random de python. Es de simple uso y le podemos dar rangos específicos en los cuales queremos números aleatorios.
Librería de pruebas estadísticas - scipy
Para realizar algunas pruebas estadísticas que no tenemos incluidas en la librería math de python, utilizaré scipy que contiene funciones interesantes que podremos usar, como chi2, con la cual podremos calcular el chi square necesario para realizar algunas pruebas a las secuencias aleatorias.
a) Los números se acoplan a una distribución?
Para determinar esto, necesitaremos una muestra suficientemente grande. Esto debido a que la forma de saber si nuestro generador de números aleatorios se acopla a una distribución, necesitamos graficar la proporción de la aparición de cada número aleatorio.
Para esto podemos dividir un rango de números, digamos del 0 al 100, en canastas de igual magnitud, y contar cuantas veces cae un número aleatorio en cada canasta, entonces graficariamos esto para ver el comportamiento, y conocer a que distribución se acopla.
Lo que hice yo, fue utilzar un método acumulativo como el que se usó en el examen, para poder generar números aleatorios con la distribución poisson, a partir de uniformes usando random.randint() de python. Entonces genere 100,000 de estos números usando lambda = 10, y conte el número de apariciones de cada número aleatorio usando canastas de 2 en 2. Al final solo lo grafiqué, el resultado se puede ver a continuación:
Él código es el siguiente:
Para esto podemos dividir un rango de números, digamos del 0 al 100, en canastas de igual magnitud, y contar cuantas veces cae un número aleatorio en cada canasta, entonces graficariamos esto para ver el comportamiento, y conocer a que distribución se acopla.
Lo que hice yo, fue utilzar un método acumulativo como el que se usó en el examen, para poder generar números aleatorios con la distribución poisson, a partir de uniformes usando random.randint() de python. Entonces genere 100,000 de estos números usando lambda = 10, y conte el número de apariciones de cada número aleatorio usando canastas de 2 en 2. Al final solo lo grafiqué, el resultado se puede ver a continuación:
(No pude hacerla mucho más visualmente atractiva debido primordialmente a que agregando más números aleatorios causaba que el programa tardara una eternidad en correr. Aún así, se puede ver que la secuencia sigue en efecto la distribución poisson)
Él código es el siguiente:
b) Test para saber si presentan características de números aleatorios
Es imposible probar a ciencia cierta si una secuencia de números dada(y el generador que la produjo) es perfectamente aleatoria. RANDOM.ORG explica esto usando una comic de DILBERT bastante gracioso, pero cierto, que se puede ver a continuación:
El hecho de que la creatura genere el número aleatorio 6 veces seguidas, nos podría hacer creer que en verdad no es una secuencia aleatoria. Pero el hecho es que puede ser que ya haya estado generando otros números previamente, y justamente en el momento en que pasaron a checarla, genero 6 nueves seguidos, es muy poco probable, pero no podemos saber si en verdad se equivoco o no.
Entonces si no podemos provar la aleatoreidad, lo que hacemos es tomar diversas secuencias de un generador aleatorio, y someterlas a pruebas estadísticas. Cada que la secuencia pase más pruebas, podemos tener más confianza en la aleatoreidad de los números, y con esto la confianza en el generador.
Pero ya que debemos esperar que algunas secuencias aparezcan no aleatorias, es decir que aparezca el mismo número varias veces seguidas, podemos esperar que las secuencias fallen algunas pruebas. Pero si muchas secuencias fallan las pruebas, debemos de sospechar del generador.
Lo mismo sería al contrario, si nuestro generador pasa todas las pruebas, deberíamos sospechar, ya que al pasar las pruebas significa que el generador no esta haciendo números aleatorios como los antes mencionados(que sean cadenas repetidas, pero aún así aleatorios), y aunque estos a primera vista no se vean aleatorios, lo son.
Test de Frecuencia (Monobit)
Defecto que detecta: Demasiados zeros o unos
Propiedad que busca: Probabilidad global igual
Parámetros:
- n - largo de la secuencia
Ésta prueba se concentra en la proporción de zeros y unos de una secuencia entera. El propósito es encontrar si el número de unos y zeros en una secuencia es aproximadamente el mismo, como se esperaría de una verdadera secuencia aleatoria.
Procedimiento:1. Convertimos los ceros del programa a -1, y los sumamos todos en una sola variable, a la que llamaremos Sn.
2. Calculamos la siguiente prueba estadística:
Donde erfc es la función error complementaria.
Código:
#Test de Frecuencia(Monobit)
#Funcion que hace la prueba de frecuencia(monobit) a una lista
#que continene una secuencia aleatoria de ceros y unos
def frequency_test(lista):
i = 0
suma = 0
n = len(lista)
for i in range(len(lista)):
if lista[i] == 0:
lista[i] = -1
suma = suma + lista[i]
suma_abs = abs(suma)/math.sqrt(n)
p_value = math.erfc(suma_abs/math.sqrt(2))
if p_value < 0.01:
print "Frequency Test: Not passed\n"
else:
print "Frequency Test: Passed\n"
Test de Frecuencia (Bloques)
Defecto que detecta: Demasiados zeros o unos
Propiedad que busca: Probabilidad local igual
Parámetros:
- n - largo de la secuencia
- m - el largo de cada bloque
- ε - secuencia de bits generada
Descripción:
El enfoque de esta prueba es la proporción de unos dentro de bloques de m bits. El proósito es determinar si una frecuencia de unos dentro de un bloque es aproximadamente m/2, como se esperaría de la aleatoreidad. Haciendo bloques de tamaño 1, estaríamos haciendo la prueba de frecuencia (monobit).
Procedimiento:
1. Partición de la secuencia en bloques de tamaño N, descartando bits no usados.
2. Determinar la proporción de unos con la fórmula:
3. Calcular la prueba estadística:
4. Calcular P - value usando la fórmula:
Donde chidist es la distribución chi al cuadrado y df es el grado de libertad (número de bloques - 1)
5. Si el valor de P - value < 0.01, se concluye que la secuencia no es aleatoria. De otra forma la secuencia es aleatoria.
Código:
#Test de Frecuencia (Bloques)
#Esta funcion toma de parametro una lista con
#la secuencia aleatoria de unos y ceros que se
#desea poner a prueba
def frequency_test_block(list):
m = 10
n = len(list)
N = int(n/m)
blocks = []
i = 0
while(len(blocks) != N):
blocks.append(list[i:(i+m)])
i = i + m
sumas = []
for i in range(len(blocks)):
sumas.append(0)
for j in range(len(blocks[i])):
sumas[i] = sumas[i] + blocks[i][j]/float(m)
#print sumas
x_2 = 0
for i in range(N):
x_2 = x_2 + math.pow((sumas[i] - .5), 2)
x_2 = x_2 * 4*m
df = m - 1
p_value = chi2.cdf(x_2, df)
if p_value < 0.01:
print "Frequency Test with Blocks: Not Passed"
else:
print "Frequency Test with Blocks: Passed"
Runs Test
Defecto que detecta: Si el cambio entre unos y ceros en la secuencia es muy rápido o muy lento.
Propiedad que busca: Depedenca secuencial (local)
Parámetros:
- n - largo de la secuencia
- ε - secuencia de bits generada
Descripción:
El centro de atención de esta prueba es el número total de "corridas" en una secuencia, donde cada corrida es una secuencia ininterrumpida de bits idénticos. Una corrida de largo k consiste en en k bits idénticos y empieza y termina antes y después con un bit del valor opuesto. El propósito de esta prueba es determinar si el número de corridas de unos y ceros de varios largos, es el esperado para una secuencia aleatoria. En particular la prueba determina si la oscilación entre ceros y unos es muy rápida o muy lenta.
Procedimiento:
1. Calcular la proporción de unos de la secuencia de bits generada con la fórmula:
2. Determinar si el pre-test de frecuencia es pasado. Si π −1 2 ≥ τ , el test no será necesario
3. Calcular la prueba estadística:
Donde r(k) = 0 si εk = εk+1, y r(k) = 1 de otra forma.
4. Calcular P - value con la fórmula:
5. Si el valor de P - value < 0.01, la secuencia no es aleatoria. De otra forma la secuencia es aleatoria.
Código:
def runs_test(lista):
suma = 0
n = len(lista)
for i in range(len(lista)):
suma = suma + lista[i]/float(n)
if abs(suma - .5) >= (2/math.sqrt(n)):
print "Runs test does not need to be performed"
return
else:
v_obs = 1
r_k = 0
for i in range(n-1):
if lista[i] == lista[i + 1]:
r_k = 0
else:
r_k = 1
v_obs = v_obs + r_k
p_value = math.erfc((abs(v_obs - (2*n*suma*(1-suma))))/(2*math.sqrt(2*n)*suma*(1-suma)))
if p_value >= 0.01:
print "Runs Test: Passed"
else:
print "Runs Test: Not passed"
Test for the largest run of ones in a block
Defecto que detecta: Si el cambio entre ceros y unos en la secuencia es muy rápida o muy lenta.
Propiead que busca: Dependencia secuencial (local)
Parámetros:
- n - largo de la secuencia.
- ε - secuencia de bits generada
- m - Largo de cada bloque. La prueba necesita que se acomode a partir de la siguiente tabla:
- N - número de bloques, definido de acuerdo a M.
Descripción:
El test se enfoca en la corrida más larga de unos dentro de bloques de m-bits. El propósito de éste test es determinar si el largo de la corrida más larga de unos dentro de la secuencia es consistente con el que se esperaría en una secuencia aleatoria. Una irregularidad esperada en el largo de la corrida más larga de unos implica que también hay una irregularidad en el largo esperado de la corrida más larga de ceros. Entonces solo es necesaria una prueba para los unos.
Ejecución de las Pruebas
Referencias:
