Números pseudoaleatorios congruenciales inversos generalizados

Un enfoque a los métodos congruenciales no lineales para generar números pseudoaleatorios uniformes en el intervalo [0,1) es el generador congruencial inverso con módulo primo. Aquí se presentará una generalización para módulos compuestos arbitrarios con primos distintos arbitrarios . ${\displaystyle m=p_{1},\dots p_{r}}$ ${\displaystyle p_{1},\dots ,p_{r}\geq 5}$

Sea . Para números enteros con mcd (a,m) = 1, una secuencia congruencial inversa generalizada de elementos de se define por ${\displaystyle \mathbb {Z} _{m}=\{0,1,...,m-1\}}$ ${\displaystyle a,b\in \mathbb {Z} _{m}}$ ${\displaystyle (y_{n})_{n\geqslant 0}}$ ${\displaystyle \mathbb {Z} _{m}}$

${\displaystyle y_{0}={\rm {seed}}}$

${\displaystyle y_{n+1}\equiv ay_{n}^{\varphi (m)-1}+b{\pmod {m}}{\text{, }}n\geqslant 0}$

donde denota el número de números enteros positivos menores que m que son relativamente primos con respecto a m . ${\displaystyle \varphi (m)=(p_{1}-1)\dots (p_{r}-1)}$

Ejemplo

Supongamos que m = 15 = y . Por lo tanto y la secuencia no es máxima. ${\displaystyle 3\times 5\,a=2,b=3}$ ${\displaystyle y_{0}=1}$ ${\displaystyle \varphi (m)=2\times 4=8\,}$ ${\displaystyle (y_{n})_{n\geqslant 0}=(1,5,13,2,4,7,1,\dots )}$

El resultado a continuación muestra que estas secuencias están estrechamente relacionadas con la siguiente secuencia congruencial inversa con módulos primos.

Para que sean y sean enteros con ${\displaystyle 1\leq i\leq r}$ ${\displaystyle \mathbb {Z} _{p_{i}}=\{0,1,\dots ,p_{i}-1\},m_{i}=m/p_{i}}$ ${\displaystyle a_{i},b_{i}\in \mathbb {Z} _{p_{i}}}$

${\displaystyle a\equiv m_{i}^{2}a_{i}{\pmod {p_{i}}}\;{\text{and }}\;b\equiv m_{i}b_{i}{\pmod {p_{i}}}{\text{. }}}$

Sea una secuencia de elementos de , dada por ${\displaystyle (y_{n})_{n\geqslant 0}}$ ${\displaystyle \mathbb {Z} _{p_{i}}}$

${\displaystyle y_{n+1}^{(i)}\equiv a_{i}(y_{n}^{(i)})^{p_{i}-2}+b_{i}{\pmod {p_{i}}}\;{\text{, }}n\geqslant 0\;{\text{where}}\;y_{0}\equiv m_{i}(y_{0}^{(i)}){\pmod {p_{i}}}\;{\text{is assumed. }}}$

Teorema 1

Sea para lo que se defina arriba. Entonces ${\displaystyle (y_{n}^{(i)})_{n\geqslant 0}}$ ${\displaystyle 1\leq i\leq r}$

${\displaystyle y_{n}\equiv m_{1}y_{n}^{(1)}+m_{2}y_{n}^{(2)}+\dots +m_{r}y_{n}^{(r)}{\pmod {m}}.}$

Este teorema muestra que es posible una implementación del generador congruencial inverso generalizado, donde los cálculos enteros exactos deben realizarse solo en pero no en ${\displaystyle \mathbb {Z} _{p_{1}},\dots ,\mathbb {Z} _{p_{r}}}$ ${\displaystyle \mathbb {Z} _{m}.}$

Prueba:

Primero, observe que y, por lo tanto , si y solo si , para lo cual se mostrará en la inducción en . ${\displaystyle m_{i}\equiv 0{\pmod {p_{j}}},\;{\text{for}}\;i\neq j,}$ ${\displaystyle y_{n}\equiv m_{1}y_{n}^{(1)}+m_{2}y_{n}^{(2)}+\dots +m_{r}y_{n}^{(r)}{\pmod {m}}}$ ${\displaystyle y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}}$ ${\displaystyle 1\leq i\leq r}$ ${\displaystyle n\geqslant 0}$

Recordemos que se supone para . Ahora, supongamos que y para algún entero . Entonces, cálculos sencillos y el teorema de Fermat dan ${\displaystyle y_{0}\equiv m_{i}(y_{0}^{(i)}){\pmod {p_{i}}}}$ ${\displaystyle 1\leq i\leq r}$ ${\displaystyle 1\leq i\leq r}$ ${\displaystyle y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}}$ ${\displaystyle n\geqslant 0}$

${\displaystyle y_{n+1}\equiv ay_{n}^{\varphi (m)-1}+b\equiv m_{i}(a_{i}m_{i}^{\varphi (m)}(y_{n}^{(i)})^{\varphi (m)-1}+b_{i})\equiv m_{i}(a_{i}(y_{n}^{(i)})^{p_{i}-2}+b_{i})\equiv m_{i}(y_{n+1}^{(i)}){\pmod {p_{i}}}}$,

lo que implica el resultado deseado.

Los números pseudoaleatorios congruenciales inversos generalizados están bien equidistribuidos en una dimensión. Un enfoque teórico confiable para evaluar sus propiedades de independencia estadística se basa en la discrepancia de s -tuplas de números pseudoaleatorios.

Límites de discrepancia del generador GIC

Utilizamos la notación donde ∈ de números pseudoaleatorios congruenciales inversos generalizados para . ${\displaystyle D_{m}^{s}=D_{m}(x_{0},\dots ,x_{m}-1)}$ ${\displaystyle x_{n}=(x_{n},x_{n}+1,\dots ,x_{n}+s-1)}$ ${\displaystyle [0,1)^{s}}$ ${\displaystyle s\geq 2}$

Límite superior

Dejar ${\displaystyle s\geq 2}$

Entonces la discrepancia satisface ${\displaystyle D_{m}^{s}}$

${\displaystyle D_{m}}$ ${\displaystyle ^{s}}$< × × × para cualquier operador congruencial inverso generalizado. ${\displaystyle m^{-1/2}}$ ${\displaystyle ({\frac {2}{\pi }}}$ ${\displaystyle \log m+{\frac {7}{5}})^{s}}$ ${\displaystyle \textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})+s_{m}^{-1}}$

Límite inferior:

Existen Generadores Congruenciales Inversos Generalizados con

${\displaystyle D_{m}}$ ${\displaystyle ^{s}}$ ≥ ×  : × para todas las dimensiones s  :≥ 2. ${\displaystyle {\frac {1}{2(\pi +2)}}}$ ${\displaystyle m^{-1/2}}$ ${\displaystyle \textstyle \prod _{i=1}^{r}({\frac {p_{i}-3}{p_{i}-1}})^{1/2}}$

Para un número fijo r de factores primos de m , el Teorema 2 muestra que para cualquier Sucesión Congruencial Inversa Generalizada. En este caso el Teorema 3 implica que existen Generadores Congruenciales Inversos Generalizados que tienen una discrepancia que es al menos del orden de magnitud para toda dimensión . Sin embargo, si m está compuesto solo de primos pequeños, entonces r puede ser de un orden de magnitud y por lo tanto para cada . ^[1] Por lo tanto, se obtiene en el caso general para cada . ${\displaystyle D_{m}^{(s)}=O(m^{-1/2}(\log m)^{s})}$ ${\displaystyle D_{m}^{(s)}}$ ${\displaystyle m^{-1/2}}$ ${\displaystyle s\geq 2}$ ${\displaystyle (\log m)/\log \log m}$ ${\displaystyle \textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})=O{(m^{\epsilon })}}$ ${\displaystyle \epsilon >0}$ ${\displaystyle D_{m}^{s}=O(m^{-1/2+\epsilon })}$ ${\displaystyle \epsilon >0}$

Dado que , argumentos similares implican que en el caso general el límite inferior en el Teorema 3 es al menos del orden de magnitud para cada . Es este rango de magnitudes donde también se encuentra la discrepancia de m puntos aleatorios independientes y uniformemente distribuidos que casi siempre tiene el orden de magnitud de acuerdo con la ley del logaritmo iterado para discrepancias. ^[2] En este sentido, los Números Pseudoaleatorios Congruenciales Inversos Generalizados modelan números aleatorios verdaderos muy de cerca. ${\displaystyle \textstyle \prod _{i=1}^{r}((p_{i}-3)/(p_{i}-1))^{1/2}\geqslant 2^{-r/2}}$ ${\displaystyle m^{-1/2-\epsilon }}$ ${\displaystyle \epsilon >0}$ ${\displaystyle m^{-1/2}(\log \log m)^{1/2}}$

Véase también

• Generador de números pseudoaleatorios
• Lista de generadores de números aleatorios
• Generador congruencial lineal
• Generador congruencial inverso
• Función pseudoaleatoria de Naor-Reingold

Referencias

1. GH Hardy y EM Wright, Introducción a la teoría de números, 5.ª ed., Clarendon Press, Oxford, 1979.
2. J. Kiefer, Sobre grandes desviaciones de las variables aleatorias vectoriales df Fo empíricas y una ley del logaritmo iterado, Pacific J. Math. 11 (1961), págs. 649-660.

Notas

• Eichenauer-Herrmann, Jürgen (1994), "Sobre números pseudoaleatorios congruenciales inversos generalizados", Mathematics of Computation , 63 (207) (primera edición), American Mathematical Society: 293–299, doi : 10.1090/S0025-5718-1994-1242056-8 , JSTOR  2153575