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

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

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

Характеристики качества генераторов. При статистическом моделировании системы S с использованием программных генераторов псевдослучайных квазиравномерных последовательностей важными характеристиками качества генератора является длина периода Р и длина отрезка апериодичности L. Длина отрезка апериодичности L псевдослучайной последовательности {x_i}, заданной уравнением

X_i+1 = λX_i +μ (mod M), x_i = X_i/M,

есть наибольшее целое число, такое, что при 0≤j<i≤L событие P{x_i=x_j} не имеет места. Это означает, что все числа x_i в пределах отрезка апериодичности не повторяются.

Очевидно, что использование при моделировании систем последовательности чисел {х_i}, длина которой больше отрезка апериодичности L, может привести к повторению испытаний в тех же условиях, что и раньше, т.е. увеличение числа реализаций не дает новых статистических результатов.

Способ экспериментального определения длины периода Р и длины отрезка апериодичности L сводится к следующему. Запускается программа генерации последовательности {х_i} с начальным значением х₀ и генерируется V чисел х_i. В большинстве практических случаев можно полагать V= (1-5)10⁶. Генерируются числа последовательности {х_i} и фиксируется число х_V. Затем программа запускается повторно с начальным числом х₀ и при генерации очередного числа проверяется истинность события P'{x_i=x_V}. Если это событие истинно: i = i₁ и i = i₂ (i₁ < i₂ < V), то вычисляется длина периода последовательности Р = i₂ – i₁. Проводится запуск программы генерации с начальными числами х₀ и х_р. При этом фиксируется минимальный номер i=i₃, при котором истинно событие Р" {x_i=x_p+i}, и вычисляется длина отрезка апериодичности L = i₃ + P. Если Р' оказывается истинным лишь для i = V, то L > V.

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

Для алгоритмов получения последовательностей чисел {х_i} общего вида экспериментальная проверка является сложной (из-за наличия больших Р и L), а расчетные соотношения в явном виде не получены. Поэтому в таких случаях целесообразно проводить теоретическую оценку длины отрезка апериодичности последовательности L.

Для проверки таблиц случайных цифр обычно применяют различные тесты, в каждом из которых цифры классифицируются по некоторому признаку и эмпирические частоты сравниваются с их математическими ожиданиями с помощью критерия Пирсона.

Для проверки аппаратных генераторов случайных чисел можно использовать те же приемы, что и для проверки последовательностей псевдослучайных чисел, полученных программным способом. Особенностью такой проверки будет то, что проверяются не те числа, которые потом будут необходимы для моделирования системы S. Поэтому кроме проверки качества выдаваемых генератором случайных чисел должна еще гарантироваться устойчивая работа генератора на время проведения машинного эксперимента с моделью M_M.

Улучшение качества последовательностей. В силу рассмотренных преимуществ основное применение в практике имитационного моделирования систем находят различные программные способы получения чисел. Поэтому рассмотрим возможные методы улучшения качества последовательностей псевдослучайных чисел. Одним из наиболее употребительных методов такого улучшения является употребление вместо формул, представляющих собой рекуррентные формулы первого порядка, рекуррентных формул порядка r, т.е.

x_i+l =Ф(x₁, x_i-1, …, x_i-r+1),

где начальные значения х₀, x_l,..., х_r-1 заданы. В этом случае длина отрезка апериодичности L у такой последовательности при r>1 гораздо больше, чем при r=1. Однако при этом возрастает сложность метода, что приводит к увеличению затрат машинного времени на получение чисел и ограничивает возможности его применения на практике.

Для получения последовательности псевдослучайных чисел с большой длиной отрезка апериодичности L можно воспользоваться методом возмущений. В основу этого метода получения последовательности чисел положена формула вида

где функции Ф(u) и Ψ(u) различны.

В этом случае в основном используется формула х_i+1 = Ф(x_i), и только когда i кратно М, последовательность «возмущается», т.е. реализуется переход к формуле х_i+1 = Ψ(х_i). Целое число М называется периодом возмущения.

Все рассмотренные критерии проверки последовательностей псевдослучайных чисел являются необходимыми при постановке имитационных экспериментов на ЭВМ с моделью М_M, но об их достаточности можно говорить лишь при рассмотрении задачи моделирования конкретной системы S.