Генерирование и статистический анализ псевдослучайных чисел

Рассмотрим последовательность чисел γ₀,γ₁,…, порождаемую рекуррентным уравнением

γ_i+1={Mγ_i}, (4.1)

где М−целое (М>1), {A} означает дробную часть А. Для некоторого множества начальных значений γ₀ последовательность, порождаемая уравнением (4.1), будет равномерно распределенной в интервале (0;1) и при достаточно больших значениях М по своим свойствам близка к последовательности т.н. базовых случайных чисел.

Уравнение (4.1) преобразуем к форме, приспособленной к арифметике с фиксированной запятой и ограниченной длиной разрядного слова

ε_i+1 ≡ M ε_i (mod p), (4.2)

где ε_i – целые положительные числа, не превышающие p; p − некоторая целая константа. Соотношение (4.2) определяет значение ε_i+1 как остаток от деления произведения M ε_i на p. Очевидно, что значения элементов последовательности (4.1) равны γ_i = ε_i/p.

Последовательность (4.2) имеет период. Как только некоторое значение ε_n будет равно начальному (или некоторому другому, имевшему уже место) значению, числа генерируемые уравнением (4.2), будут повторяться.

В соответствии с требованиями, предъявляемыми к генераторам псевдослучайных последовательностей, желательно, чтобы длина периода была максимальной. Она будет зависеть от модуля p и начального значения ε₀.

Учитывая двоичный способ представления чисел в ЭВМ, ограничимся рассмотрением случая

ε_i+1 = Mε_i (mod 2^S), (4.3)

где S – длина разрядной сетки; γ_i = ε_i∙2^-S.

Качество псевдослучайных последовательностей определяется проверкой их равномерности распределения и взаимной независимости с помощью различных статистических тестов. Мы же в лабораторных работах для этого будем использовать критерий согласия Пирсона – χ² или же критерий Колмогорова – Смирнова.

Ниже на рисунке 4.1 приводится схема алгоритма генератора псевдослучайных чисел RANDU (IX,IY,YFL) для 32-разрядной ЭВМ.

Рис. 4.1 – Схема алгоритма генератора псевдослучайных чисел RANDU

Здесь последовательность псевдослучайных чисел определяется из рекуррентного соотношения

ε_i+1 = (65539ε_i) mod 2³², (4.4)

Использованные обозначения: IX – начальное значение, любое нечетное целое число, меньшее 2³²;

IY – получаемая целочисленная случайная величина,

YFL – получаемая случайная величина из интервала (0;1).

Не нашли, что искали? Воспользуйтесь поиском: