Подход к нелинейным конгруэнтным методам генерация равномерных псевдослучайных чисел в интервале [0,1) - Инверсивный конгруэнтный генератор с простым модулем. Обобщение для произвольных составных модулей
с произвольно четкими простые числа
здесь будет присутствовать.
Позволять
. За целые числа
с НОД (a, m) = 1 обобщенная обратная конгруэнтная последовательность
элементов
определяется


куда
обозначает количество натуральных чисел меньше, чем м которые относительно простой к м.
Пример
Возьмем m = 15 =
и
. Следовательно
и последовательность
не максимум.
Приведенный ниже результат показывает, что эти последовательности тесно связаны со следующей обратимой конгруэнтной последовательностью с простыми модулями.
За
позволять
и
быть целыми числами с

Позволять
быть последовательностью элементов
, данный

Теорема 1.
Позволять
за
быть определенным, как указано выше.

Эта теорема показывает, что возможна реализация обобщенного инверсивного конгруэнтного генератора, в котором точные целочисленные вычисления должны выполняться только в
но не в 
Доказательство:
Во-первых, заметьте, что
и поэтому
если и только если
, за
которое будет показано при индукции по
.
Напомним, что
предполагается для
. Теперь предположим, что
и
для некоторого целого числа
. Тогда несложные вычисления и Теорема Ферма урожай
,
что подразумевает желаемый результат.
Обобщенные инверсивные конгруэнтные псевдослучайные числа хорошо равномерно распределены в одном измерении. Надежный теоретический подход к оценке их свойств статистической независимости основан на несовпадении s-наборы псевдослучайных чисел.
Границы несоответствия генератора GIC
Мы используем обозначения
куда
∈
обобщенных инверсивных конгруэнтных псевдослучайных чисел для
.
Верхняя граница
- Позволять

- Тогда несоответствие
удовлетворяет
<
×
×
×
для любого обобщенного инверсивного конгруэнтного оператора.
Нижняя граница:
- Существуют обобщенные инверсивные конгруэнтные генераторы с
≥
×
: ×
для всех измерений s :≥ 2.
На фиксированный номер р основных факторов м, Теорема 2 показывает, что
для любой обобщенной инверсивной конгруэнтной последовательности. В этом случае из теоремы 3 следует, что существуют обобщенные инверсивные конгруэнтные генераторы, имеющие невязку
что по крайней мере на порядок
для всех измерений
. Однако если м состоит только из маленьких простых чисел, то р может быть на порядок
и поэтому
для каждого
.[1] Следовательно, в общем случае получаем
для каждого
.
С
, из аналогичных рассуждений следует, что в общем случае оценка снизу в теореме 3 не менее чем по порядку величины
для каждого
. Именно в этом диапазоне величин обнаруживается несовпадение m независимых и равномерно распределенных случайных точек, которое почти всегда имеет порядок величины
по закону повторного логарифма невязок.[2] В этом смысле обобщенные инверсивные конгруэнтные псевдослучайные числа очень точно моделируют истинные случайные числа.
Смотрите также
Рекомендации
- ^ Г. Х. Харди и Э. М. Райт, Введение в теорию чисел, 5-е изд., Clarendon Press, Oxford, 1979.
- ^ Кифер Дж. О больших отклонениях эмпирической д.ф. FO векторных случайных переменных и закон повторного логарифма, PacificJ. Математика. 11 (1961), стр. 649-660.
Примечания
- Эйхенауэр-Херрманн, Юрген (1994), Об обобщенных инверсивных конгруэнтных псевдослучайных числах (первое издание), Американское математическое общество, JSTOR 2153575