Generador congruencial lineal combinado

Un generador congruencial lineal combinado ( CLCG ) es un algoritmo generador de números pseudoaleatorios basado en la combinación de dos o más generadores congruenciales lineales (LCG). Un LCG tradicional tiene un período inadecuado para la simulación de sistemas complejos . ^{[ 1 ]} Al combinar dos o más LCG, se pueden crear números aleatorios con un período más largo y mejores propiedades estadísticas. ^{[ 1 ]} El algoritmo se define como: ^{[ 2 ]}$${\displaystyle X_{i}\equiv \left(\sum _{j=1}^{k}(-1)^{j-1}Y_{i,j}\right){\pmod {m_{1}-1}}}$$ dónde:

• ${\displaystyle m_{1}}$es el " módulo " del primer LCG
• ${\displaystyle Y_{i,j}}$es la i- ^ésima entrada del j- ^ésimo LCG
• ${\displaystyle X_{i}}$es el i ^-ésimo número entero aleatorio generado

con: $${\displaystyle R_{i}\equiv {\begin{cases}X_{i}/m_{1}&{\text{para }}X_{i}>0\\(m_{1}-1)/m_{1}&{\text{para }}X_{i}=0\end{cases}}}$$ dónde${\displaystyle R_{i}}$es un número aleatorio con distribución uniforme entre 0 y 1.

Si W _{i ,1} , W _{i ,2} , ..., W _{i ,k} son cualesquiera variables aleatorias discretas e independientes y una de ellas se distribuye uniformemente de 0 a m ₁ − 2, entonces Z _i se distribuye uniformemente entre 0 y m ₁ − 2, donde: ^{[ 2 ]}    $${\displaystyle Z_{i}=\left(\sum _{j=1}^{k}W_{i,j}\right){\pmod {m_{1}-1}}}$$

Sean X _{i ,1} , X _{i ,2} , ..., X _{i , k} salidas de k LCG. Si W _{i , j} se define como X _{i , j} − 1, entonces W _{i , j} estará aproximadamente uniformemente distribuido de 0 a m _j − 1. ^{[ 2 ]} El coeficiente "( − 1) ^{j − 1} " realiza implícitamente la resta de uno de X _{i , j} . ^{[ 1 ]}    

El algoritmo CLCG proporciona una forma eficiente de calcular números pseudoaleatorios. El algoritmo LCG es computacionalmente económico. ^{[ 3 ]} Los resultados de múltiples algoritmos LCG se combinan mediante el algoritmo CLCG para crear números pseudoaleatorios con un período más largo que el que se puede lograr con el método LCG por sí solo. ^{[ 3 ]}

El período de una CLCG es el mínimo común múltiplo de los períodos de los generadores individuales, que son uno menos que los módulos. Dado que todos los módulos son primos impares, los períodos son pares y, por lo tanto, comparten al menos un divisor común de 2, pero si los módulos se eligen de manera que 2 sea el máximo común divisor de cada par, esto dará como resultado un período de: ^{[ 1 ]}$${\displaystyle P={\frac {(m_{1}-1)(m_{2}-1)\cdots (m_{k}-1)}{2^{k-1}}}}$$

El siguiente es un ejemplo de algoritmo diseñado para su uso en computadoras de 32 bits: ^{[ 2 ]}$${\displaystyle k=2}$$ Los LCG se utilizan con las siguientes propiedades: $${\displaystyle {\begin{aligned}a_{1}&=40014&a_{2}&=40692\\m_{1}&=2147483563&m_{2}&=2147483399\\c_{1}&=0&c_{2}&=0\end{aligned}}}$$

El algoritmo CLCG se configura de la siguiente manera:

El período máximo de los dos LCG utilizados se calcula mediante la fórmula: ^{[ 1 ]}$${\displaystyle (m-1)}$$ Esto equivale a 2.100 millones para los dos LCG utilizados.

Este CLCG que se muestra en este ejemplo tiene un período máximo de: $${\displaystyle (m_{1}-1)(m_{2}-1)/2\approx 2.3\times 10^{18}}$$ Esto representa una mejora considerable con respecto al período de los LCG individuales. Se puede observar que el método combinado aumenta el período en nueve órdenes de magnitud.

Sorprendentemente, el período de este CLCG puede no ser suficiente para todas las aplicaciones. ^{[ 1 ]} Se han utilizado otros algoritmos que emplean el método CLCG para crear generadores de números pseudoaleatorios con períodos tan largos como3 × 10 ⁵⁷ . ^{[ 4 ] [ 5 ] [ 6 ]}

El primero de los dos generadores, que utiliza b = 40.014 y m = 2.147.483.563, también es utilizado por la calculadora científica Texas Instruments TI-30X IIS .

• Generador congruencial lineal
• Wichmann-Hill , un modelo LCG combinado específico propuesto en 1982.

• Descripción general del uso y las pruebas de los generadores de números pseudoaleatorios.