Обобщенные инверсивные конгруэнтные псевдослучайные числа

Подходом к нелинейным конгруэнтным методам генерации равномерных псевдослучайных чисел в интервале [0,1) является инверсивный конгруэнтный генератор с простым модулем. Обобщение для произвольных составных модулей $m=p_{1},\dots p_{r}$ с произвольными различными простыми числами $p_{1},\dots ,p_{r}\geq 5$ здесь будет присутствовать.

Позволять $\mathbb {Z} _{m}=\{0,1,...,m-1\}$. Для целых чисел $a,b\in \mathbb {Z} _{m}$ с НОД (a,m) = 1 — обобщенная инверсивная конгруэнтная последовательность $(y_{n})_{n\geqslant 0}$ элементов $\mathbb {Z} _{m}$ определяется

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

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

где $\varphi (m)=(p_{1}-1)\dots (p_{r}-1)$ обозначает количество натуральных чисел меньше m , которые являются относительно простыми с m .

Пример

Возьмем m = 15 = $3\times 5\,a=2,b=3$ и $y_{0}=1$. Следовательно $\varphi (m)=2\times 4=8\,$ и последовательность $(y_{n})_{n\geqslant 0}=(1,5,13,2,4,7,1,\dots )$ не является максимальным.

Результат ниже показывает, что эти последовательности тесно связаны со следующей инверсивной конгруэнтной последовательностью с простыми модулями.

Для $1\leq i\leq r$ позволять $\mathbb {Z} _{p_{i}}=\{0,1,\dots ,p_{i}-1\},m_{i}=m/p_{i}$ и $a_{i},b_{i}\in \mathbb {Z} _{p_{i}}$ быть целыми числами с

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

Позволять $(y_{n})_{n\geqslant 0}$ быть последовательностью элементов $\mathbb {Z} _{p_{i}}$, заданный

$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. }}$

Теорема 1

Позволять $(y_{n}^{(i)})_{n\geqslant 0}$ для $1\leq i\leq r$ быть определены, как указано выше. Затем

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

Эта теорема показывает, что возможна реализация обобщенного инверсивного конгруэнтного генератора, в которой точные целочисленные вычисления должны выполняться только в $\mathbb {Z} _{p_{1}},\dots ,\mathbb {Z} _{p_{r}}$ но не в $\mathbb {Z} _{m}.$

Доказательство:

Во-первых, заметьте, что $m_{i}\equiv 0{\pmod {p_{j}}},\;{\text{for}}\;i\neq j,$ и, следовательно, $y_{n}\equiv m_{1}y_{n}^{(1)}+m_{2}y_{n}^{(2)}+\dots +m_{r}y_{n}^{(r)}{\pmod {m}}$ тогда и только тогда, когда $y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}$, для $1\leq i\leq r$ который будет показан при индукции по $n\geqslant 0$.

Напомним, что $y_{0}\equiv m_{i}(y_{0}^{(i)}){\pmod {p_{i}}}$ предполагается для $1\leq i\leq r$. Теперь предположим, что $1\leq i\leq r$ и $y_{n}\equiv m_{i}(y_{n}^{(i)}){\pmod {p_{i}}}$ для некоторого целого числа $n\geqslant 0$. Тогда простые вычисления и теорема Ферма дают

$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}}}$,

что подразумевает желаемый результат.

Обобщенные инверсивные конгруэнтные псевдослучайные числа хорошо равномерно распределены в одном измерении. Надежный теоретический подход к оценке свойств их статистической независимости основан на несовпадении s -кортежей псевдослучайных чисел.

Границы расхождения генератора GIC

Мы используем обозначение $D_{m}^{s}=D_{m}(x_{0},\dots ,x_{m}-1)$ где $x_{n}=(x_{n},x_{n}+1,\dots ,x_{n}+s-1)$ ∈ $[0,1)^{s}$ обобщенных инверсивных конгруэнтных псевдослучайных чисел для $s\geq 2$.

Верхняя граница

Позволять $s\geq 2$

Тогда расхождение $D_{m}^{s}$ удовлетворяет

$D_{m}$ $^{s}$ < $m^{-1/2}$ × $({\frac {2}{\pi }}$ × $\log m+{\frac {7}{5}})^{s}$ × $\textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})+s_{m}^{-1}$ для любого обобщенного инверсивного конгруэнтного оператора.

Нижняя граница:

Существуют обобщенные инверсивные конгруэнтные генераторы с

$D_{m}$ $^{s}$ ≥ ${\frac {1}{2(\pi +2)}}$ × $m^{-1/2}$ : × $\textstyle \prod _{i=1}^{r}({\frac {p_{i}-3}{p_{i}-1}})^{1/2}$ для всех размерностей s :≥ 2.

Для фиксированного числа r простых множителей числа m теорема 2 показывает, что $D_{m}^{(s)}=O(m^{-1/2}(\log m)^{s})$ для любой обобщенной инверсивной конгруэнтной последовательности. В этом случае из теоремы 3 следует, что существуют обобщенные инверсивные конгруэнтные генераторы, имеющие невязку $D_{m}^{(s)}$ что, по крайней мере, порядка величины $m^{-1/2}$ для всех размеров $s\geq 2$. Однако если m состоит только из маленьких простых чисел, то r может иметь порядок величины. $(\log m)/\log \log m$ и, следовательно, $\textstyle \prod _{i=1}^{r}(2s-2+s(p_{i})^{-1/2})=O{(m^{\epsilon })}$ для каждого $\epsilon >0$. Поэтому в общем случае получаем $D_{m}^{s}=O(m^{-1/2+\epsilon })$ для каждого $\epsilon >0$.

С $\textstyle \prod _{i=1}^{r}((p_{i}-3)/(p_{i}-1))^{1/2}\geqslant 2^{-r/2}$из аналогичных рассуждений следует, что в общем случае нижняя оценка в теореме 3 имеет по крайней мере порядок величины $m^{-1/2-\epsilon }$ для каждого $\epsilon >0$. Именно в этом диапазоне величин также находится невязка m независимых и равномерно распределенных случайных точек, которая почти всегда имеет порядок величины $m^{-1/2}(\log \log m)^{1/2}$ по закону повторного логарифма для невязок. В этом смысле обобщенные инверсивные конгруэнтные псевдослучайные числа очень точно моделируют истинные случайные числа.

См. также

• Генератор псевдослучайных чисел
• Список генераторов случайных чисел
• Линейный конгруэнтный генератор
• Инверсивный конгруэнтный генератор
• Псевдослучайная функция Наора-Рейнгольда

Примечания

• Эйхенауэр-Херрманн, Юрген (1994), «Об обобщенных инверсивных конгруэнтных псевдослучайных числах», Mathematics of Computation , 63 (207) (первое изд.), Американское математическое общество: 293–299, doi : 10.1090/S0025-5718-1994- 1242056-8 , АЭСТОР   2153575