. Лекция 11 . Процедуры генерации последовательностей псевдослучайных чисел

Одной из исторически первых процедур получения последовательностей псевдослучайных чисел была процедура, получившая название метода серединных квадратов. Пусть имеется 2n-разрядное число, меньшее единицы: x_i=0,a₁a₂…a_2n. Возведем его в квадрат: x_i²=0,b₁b₂…b_4n, а затем отберем средние 2n разрядов x_i+1=0,b_n+1b_n+2…b_3n, которые и будут являться очередным числом псевдослучайной последовательности. Недостаток данного метода – наличие корреляции между числами последовательности, а в ряде случаев случайность может вообще отсутствовать.

Широкое применение при моделировании систем на ЭВМ получили конгруэнтные процедуры генерации псевдослучайных последовательностей, представляющие собой арифметические операции, в основе которых лежит понятие конгруэнтности. Два целых числа a и b конгруэнтны (сравнимы) по модулю m, где m – целое число, тогда и только тогда, когда существует такое целое число k, что a – b = km, т.е. если разность чисел a и b делится на m и если числа a и bдают одинаковые остатки от деления на абсолютную величину числа m. Конгруэнтные процедуры являются чисто детерминированными, т.к. описываются в виде рекуррентного соотношения:

X_i = ⁱ X₀ + (ⁱ  1)  / (  1) (mod M),

где X_i, , , M – неотрицательные целые числа. Если заданы начальное значение X₀, множитель  и аддитивная константа , то данное соотношение однозначно определяет последовательность целых чисел {X_i}, составленную из остатков деления на M членов последовательности {ⁱ X₀ + (ⁱ  1)  / (  1)}. Таким образом, по целым числам последовательности {X_i} можно построить последовательность {x_i} = {X_i / M} рациональных чисел из интервала (0, 1).

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

Эффективность статистического моделирования на ЭВМ и достоверность получаемых результатов существенным образом зависит от качества исходных (базовых) последовательностей псевдослучайных чисел, которые являются основой для получения стохастических воздействий на элементы моделируемой системы. Прежде чем приступать к реализации моделирующих алгоритмов на ЭВМ, необходимо убедиться в том, что исходная последовательность псевдослучайных чисел удовлетворяет предъявляемым к ней требованиям, т.к. в противном случае даже при наличии абсолютно правильного алгоритма моделирования процесса функционирования системы по результатам моделирования нельзя достоверно судить о ее характеристиках. Поэтому, все применяемые генераторы случайных чисел должны пройти тщательное тестирование перед моделирование системы. Тестирование представляет собой комплекс проверок по различным статистическим критериям, включая в качестве основных тесты на равномерность, стохастичность и независимость.

Проверка равномерности последовательности псевдослучайных квазиравномерно распределенных чисел может быть выполнена по ее гистограмме с использованием косвенных признаков. Суть проверки по гистограмме сводится к следующему: выдвигается гипотеза о равномерности распределения числе в интервале (0, 1), который затем разбивается на m равных частей. Тогда при генерации последовательности {x_i} каждое из чисел x с вероятностью p_j=1/m попадает в один из подынтервалов. Очевидно, что если числа x_i принадлежат псевдослучайной квазиравномерно распределенной последовательности, то при достаточно больших значениях числа испытаний N экспериментальна гистограмма приблизится к теоретической прямой 1/m. Оценка степени приближения, т.е. равномерности последовательности {x_i}, может быть проведена с использованием критериев согласия. На практике обычно принимается m=2050, N=(10²10³).

Проверка стохастичности последовательности псевдослучайных чисел {x_i} наиболее часто проводится методами комбинаций и серий. Сущность метода комбинаций сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) числа единиц (нулей) в n-разрядном двоичном числе X_i. На практике длину последовательности N берут достаточно большой и проверяют все n разрядов или только l старших разрядов. Теоретически вероятность появления j единиц в l разрядах P(j, l) двоичного числа X_i описывается биномиальным законом распределения, исходя из независимости отдельных разрядов. После нахождения теоретических и экспериментальных вероятностей P(j, l) гипотеза о стохастичности проверяется с использованием критериев согласия.

Проверка независимости элементов последовательности псевдослучайных квазиравномерно распределенных чисел проводится на основе вычисления корреляционного момента.