A.3 Contrastes específicos para generadores aleatorios

Los contrastes generales anteriores pueden ser muy poco adecuados para testear generadores de números pseudoaleatorios (ver e.g. L’Ecuyer y Simard, 2007). Por ese motivo se han desarrollado contrastes específicos, principalmente con el objetivo de encontrar un generador con buenas propiedades criptográficas.

Muchos de estos contrastes están basados en la prueba chi-cuadrado y trabajan con enteros en lugar de los valores uniformes. El procedimiento habitual consiste en fijar un entero positivo \(K\), y discretizar los valores uniformes \(U_{1},U_{2},\ldots,U_{n}\), de la forma: \[X_i = \left\lfloor K\cdot U_{i}\right\rfloor + 1 ,\] donde \(\left\lfloor u\right\rfloor\) denota la parte entera de \(u\). De esta forma se consigue una sucesión de enteros aleatorios supuestamente independientes con distribución uniforme en \(\{1, \ldots, K\}\).

En esta sección se describirán algunos de los métodos tradicionales en este campo con fines ilustrativos. Si realmente el objetivo es diagnosticar la calidad de un generador, la recomendación sería emplear las baterías de contrastes más recientes descritas en la Sección 2.3.2.

A.3.1 Contraste de frecuencias

Empleando la discretización anterior se simplifica notablemente el contraste chi-cuadrado de bondad de ajuste a una uniforme, descrito en la Sección A.1.4 e implementado en la función chisq.cont.test(). En este caso bastaría con contrastar la equiprobabilidad de la secuencia de enteros (empleando directamente la función chisq.test()) y este método de denomina contraste de frecuencias (frequency test). Por ejemplo:

# Generar
set.seed(1)
u <- runif(1000)
# Discretizar
k <- 10
x <- floor(k*u) + 1
# Test chi-cuadrado
f <- table(factor(x, levels = seq_len(k)))
chisq.test(f)
## 
##  Chi-squared test for given probabilities
## 
## data:  f
## X-squared = 10.26, df = 9, p-value = 0.3298

Este código está implementado en la función simres::freq.test() (fichero test.R) y podríamos emplear:

library(simres)
freq.test(u, nclass = k)
# Alternativamente
# chisq.cont.test(u, distribution = "unif", nclass = k, output = FALSE, min = 0, max = 1)

A.3.2 Contraste de series

El contraste anterior se puede generalizar a contrastar la uniformidad de las \(d\)-uplas \((X_{t+1},X_{t+2},\ldots,X_{t+d})\) con \(t=(i-1)d\), \(i=1,\ldots,m\) siendo \(m=\lfloor n/d \rfloor\). La idea es que troceamos el hipercubo \([0, 1]^d\) en \(K^d\) celdas equiprobables. Considerando como categorías todos los posibles valores de las \(d\)-uplas, podemos emplear el estadístico chi-cuadrado para medir la discrepancia entre las frecuencias observadas y las esperadas, iguales todas a \(\frac{m}{K^d}\). Las elecciones más frecuentes son \(d=2\) (contraste de pares seriados) y \(K=8\), \(10\) ó \(20\). Por ejemplo, la función serial.test() del paquete randtoolbox implementa este contraste para \(d=2\).

Para que la prueba chi-cuadrado sea fiable el valor de \(n\) debería ser grande en comparación con el número de categorías \(K^d\) (e.g. \(n \geq 5dK^d\)). Si se considera un valor \(d \geq 3\) puede ser necesario reducir considerablemente el valor de \(K\) para evitar considerar demasiadas categorías. Alternativamente se podrían considerar distintas técnicas para agrupar estas categorías, por ejemplo como se hace en el contraste del poker o del coleccionista descritos a continuación.

A.3.3 El contraste del poker

En el contrate del poker “clásico” se consideran conjuntos sucesivos de cinco enteros (\(d=5\)) y, para cada uno, se determina cuál de las siguientes posibilidades se da:

  1. Un mismo entero se repite cinco veces (abreviadamente, \(AAAAA\)).

  2. Un mismo entero se repite cuatro veces y otro distinto aparece una vez (\(AAAAB\)).

  3. Un entero se repite tres veces y otro distinto se repite dos (\(AAABB\)).

  4. Un entero se repite tres veces y otros dos distintos aparecen una vez cada uno (\(AAABC\)).

  5. Un entero se repite dos veces, otro distinto se repite también dos veces y un tercer entero diferente aparece una sóla vez (\(AABBC\)).

  6. Un entero se repite dos veces y otros tres distintos aparecen una vez cada uno (\(AABCD\)).

  7. Los cinco enteros que aparecen son todos distintos (\(ABCDE\)).

Bajo las hipótesis de aleatoriedad y uniformidad, se pueden calcular las probabilidades de estas modalidades. Por ejemplo para \(K=10\) obtendríamos:

\[\begin{aligned} P(AAAAA) & =0.0001, P(AAAAB)=0.0045, P(AAABB)=0.0090,\\ P(AAABC) & =0.0720, P(AABBC)=0.1080, P(AABCD)=0.5040,\\ P(ABCDE) & =0.3024. \end{aligned}\]

Es frecuente que las clases \(AAAAA\) y \(AAAAB\) se agrupen a la hora de aplicar el test chi-cuadrado, ya que, en caso contrario, la restricción habitual \(e_{i}\geq5\) llevaría a que \(0.0001\cdot\frac{n}{5}\geq5\), es decir, \(n\geq250\,000\).

Es habitual simplificar el contraste anterior para facilitar su implementación definiendo las categorías según el número de enteros distintos de entre los cinco observados. Así obtendríamos: \[\begin{aligned} P(\text{1 entero diferente}) & = 0.0001, P(\text{2 enteros diferentes}) = 0.0135,\\ P(\text{3 enteros diferentes}) & = 0.1800, P(\text{4 enteros diferentes}) = 0.5040,\\ P(\text{5 enteros diferentes}) & = 0.3024, \end{aligned}\] procediendo también a agrupar las dos primeras modalidades.

En el caso general de considerar \(d\)-uplas (manos de \(d\) cartas con \(K\) posibilidades cada una), la probabilidad de obtener \(c\) valores (cartas) diferentes es (e.g. Knuth, 2002, Sección 3.3.2, p. 64): \[P(C=c) = \frac{K!}{(K-c)!K^d}S(d,c),\] donde \(S(d,c)\) es el número de Stirling de segunda clase, definido como el número de formas que existen de hacer una partición de un conjunto de \(d\) elementos en \(c\) subconjuntos: \[S(d,c) = \frac{1}{c!}\sum_{i=0}^{c} (-1)^{i} \binom{c}{i} (c-i)^d.\] Por ejemplo, la función poker.test() del paquete randtoolbox implementa este contraste para el caso de \(d=K\).

A.3.4 El contraste del coleccionista

Por simplicidad describiremos el caso de \(d=1\) (con \(K\) categorías). Considerando la sucesión de enteros aleatorios se procede (como un coleccionista) a contabilizar cuál es el número, \(Q\), (aleatorio) de valores consecutivos hasta que se completa la colección de todos los enteros entre \(1\) y \(K\). Obviamente, bajo las hipótesis de aleatoriedad y uniformidad, cada posible entero entre \(1\) y \(K\) tiene la misma probabilidad de aparecer en cada generación y, por tanto, resulta posible calcular la distribución de probabilidad de \(Q\). De esta forma podemos utilizar los valores calculados de las probabilidades \[P( Q = K ), P( Q = K+1 ),\ldots, P( Q = M -1 ), P( Q \geq M ),\] para obtener las frecuencias esperadas de cada clase y confrontarlas con las observadas vía el estadístico chi-cuadrado (e.g. Knuth, 2002, Sección 3.3.2, p. 65).

Existen varias elecciones comunes de \(K\) y \(M\). Tomando \(K=5\) con clases \(Q=5\), \(Q=6\), \(\ldots\), \(Q=19\), \(Q\geq20\), las probabilidades vendrían dadas por: \[\begin{array}{rr} P( Q = 5 ) = 0.03840000, \ & P( Q = 6 ) = 0.07680000,\\ P( Q = 7 ) = 0.09984000, \ & P( Q = 8 ) = 0.10752000,\\ P( Q = 9 ) = 0.10450944, \ & P( Q = 10 ) = 0.09547776,\\ P( Q = 11 ) = 0.08381645, \ & P( Q = 12 ) = 0.07163904,\\ P( Q = 13 ) = 0.06011299, \ & P( Q = 14 ) = 0.04979157,\\ P( Q = 15 ) = 0.04086200, \ & P( Q = 16 ) = 0.03331007,\\ P( Q = 17 ) = 0.02702163, \ & P( Q = 18 ) = 0.02184196,\\ P( Q = 19 ) = 0.01760857, \ & P( Q\geq20 ) = 0.07144851. \end{array}\]

Para \(K=10\) se podrían considerar las siguientes categorías (con sus correspondientes probabilidades): \[\begin{array}{rr} P( 10 \leq Q \leq 19 ) = 0.17321155, \ & P( 20 \leq Q \leq 23 ) = 0.17492380,\\ P( 24 \leq Q \leq 27 ) = 0.17150818, \ & P( 28 \leq Q \leq 32 ) = 0.17134210,\\ P( 33 \leq Q \leq 39 ) = 0.15216056, \ & P( Q \geq 40 ) =0.15685380. \end{array}\]