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: \(\boldsymbol{x}_{i} = A_0 + A_1\boldsymbol{x}_{i-1} + A_2\boldsymbol{x}_{i-2} + \cdots + A_{k}\boldsymbol{x}_{i-k} \bmod m\).

Un ejemplo de generador congruencia lineal múltiple es el denominado generador de Fibonacci retardado (Fibonacci-lagged generator; 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 (lo cual no sería en principio recomendable; ver Knuth Recent News 2002) estableciendo kind a "Knuth-TAOCP-2002" o "Knuth-TAOCP" en la llamada a set.seed() o RNGkind().

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 los 624 enteros de 32 bits correspondientes, el segundo componente es el índice/posición correspondiente al último valor devuelto; el conjunto de enteros solo cambia cada 624 generaciones).

set.seed(1)
u <- runif(1)
seed <- .Random.seed
u <- runif(623)
sum(seed != .Random.seed) 
## [1] 1
# Solo cambia el índice: 
seed[2]; .Random.seed[2]
## [1] 1
## [1] 624
u <- runif(1)
# Cada 624 generaciones cambia el conjunto de enteros y el índice se inicializa
sum(seed != .Random.seed)
## [1] 624
seed[2]; .Random.seed[2]
## [1] 1
## [1] 1

Un 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}\)).