2.2 Extensiones
Se han considerado diversas extensiones del generador congruencial lineal simple:
Lineal múltiple: \(x_{i}= a_0 + a_1 x_{i-1} + a_2 x_{i-2} + \cdots + a_{k} x_{i-k} \bmod m\), con periodo \(p\leq m^{k}-1\).
No lineal: \(x_{i} = f\left( x_{i-1}, x_{i-2}, \cdots, x_{i-k} \right) \bmod m\). Por ejemplo \(x_{i} = a_0 + a_1 x_{i-1} + a_2 x_{i-1}^2 \bmod m\).
Matricial: \(\mathbf{x}_{i} = A_0 + A_1 \mathbf{x}_{i-1} + A_2 \mathbf{x}_{i-2} + \cdots + A_{k} \mathbf{x}_{i-k} \bmod m\).
Un ejemplo de generador congruencia lineal múltiple es el denominado generador de Fibonacci retardado (Knuth, 1969):
\[x_n = (x_{n-37} + x_{n-100}) \bmod 2^{30},\]
con un período aproximado de \(2^{129}\) y que puede ser empleado en R estableciendo kind a "Knuth-TAOCP" en la llamada a set.seed() o RNGkind() (aunque sería preferible emplear kind = "Knuth-TAOCP-2002"; ver Knuth Recent News 2002).
El generador Mersenne-Twister (Matsumoto y Nishimura, 1998), empleado por defecto en R, de periodo \(2^{19937}-1\) y equidistribution en 623 dimensiones, se puede expresar como un generador congruencial matricial lineal. En cada iteración (twist) genera 624 valores (los últimos componentes de la semilla son 624 enteros de 32 bits) y utiliza un índice para almacenar la posición correspondiente al último valor devuelto (el segundo componente de la semilla). Cada 624 generaciones cambia el conjunto de enteros y el índice se inicializa.
set.seed(1)
# Generamos una simulación y almacenamos la semilla:
u <- runif(1)
seed <- .Random.seed
# Generamos 623 valores más:
u <- runif(623)
# Durante las 624 generaciones solo cambió el índice:
cat("Número de componentes distintos:", sum(seed != .Random.seed), "\n")## Número de componentes distintos: 1cat("Índice inicial:", seed[2], ", actual:", .Random.seed[2], "\n")## Índice inicial: 1 , actual: 624# Si generamos una más:
u <- runif(1)
# Se actualiza el conjunto de enteros y el índice se vuelve a establecer a 1:
cat("Número de componentes distintos:", sum(seed != .Random.seed), "\n")## Número de componentes distintos: 624Un caso particular del generador lineal múltiple son los denominados generadores de registros desfasados (más relacionados con la criptografía). Se generan bits de forma secuencial considerando \(m=2\) y \(a_{i} \in \left \{ 0,1\right \}\) y se van combinando \(l\) bits para obtener valores en el intervalo \((0, 1)\), por ejemplo \(u_i = 0 . x_{it+1} x_{it+2} \ldots x_{it+l}\), siendo \(t\) un parámetro denominado aniquilación (Tausworthe, 1965). Los cálculos se pueden realizar rápidamente mediante operaciones lógicas (los sumandos de la combinación lineal se traducen en un “o” exclusivo XOR), empleando directamente los registros del procesador (ver por ejemplo Ripley, 1987, Algoritmo 2.1).
Otras alternativas consisten en la combinanción de varios generadores, las más empleadas son:
Combinar las salidas: por ejemplo \(u_{i}=\sum_{l=1}^L u_{i}^{(l)} \bmod 1\), donde \(u_{i}^{(l)}\) es el \(i\)-ésimo valor obtenido con el generador \(l\).
Barajar las salidas: por ejemplo se crea una tabla empleando un generador y se utiliza otro para seleccionar el índice del valor que se va a devolver y posteriormente actualizar.
El generador L’Ecuyer-CMRG (L’Ecuyer, 1999), empleado como base para la generación de múltiples secuencias en el paquete parallel, combina dos generadores concruenciales lineales múltiples de orden \(k=3\) (el periodo aproximado es \(2^{191} \approx 3.1 \times 10^{57}\)):
\[x_{1,n} = (1403580 x_{1,n−2} − 810728 x_{1,n−3}) \bmod 2^{32} − 209\] \[x_{2,n} = (527612 x_{2,n−1} − 1370589 x_{2,n−3}) \bmod 2^{32} − 22853\] \[z_n = (x_{1,n} − x_{2,n}) \bmod 4294967087\] \[ u_n = \left\{ \begin{array}[c]{ll} z_n/4294967088 & \text{ si } z_n > 0\\ 4294967087/4294967088 & \text{ si } z_n = 0 \end{array} \right. \]