4.3. ПРОВЕРКА И УЛУЧШЕНИЕ КАЧЕСТВА ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

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

последовательность псевдослучайных чисел удовлетворяет предъявляемым к ней требованиям, так как в противном случае даже при наличии абсолютно правильного алгоритма моделирования процесса функционирования системы S по результатам моделирования нельзя достоверно судить о характеристиках системы [29, 37].

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

Проверка равномерности последовательностей псевдослучайных квазиравномерно распределенных чисел может быть выполнена по гистограмме с использованием косвенных признаков [4, 26]. Суть проверки по гистограмме сводится к следующему. Выдвигается гипотеза о равномерности распределения чисел в интервале Затем интервал разбивается на равных частей, тогда при генерации последовательности каждое из чисел х с вероятностью попадает в один из подынтервалов. Всего в каждый подынтервал попадает чисел последовательности причем Относительная частота попадания случайных чисел последовательности в каждый из подынтервалов будет равна Вид соответствующей гистограммы для примера показан на рис. 4.11, а, где пунктирная линия соответствует теоретическому значению а сплошная — экспериментальному Очевидно, что если числа принадлежат псевдослучайной квазиравномерно распределенной последовательности, то при достаточно больших N экспериментальная гистограмма (ломаная линия на рис. 4.11, а) приблизится к теоретической прямой

Оценка степени приближения, т. е. равномерности последовательности может быть проведена с использованием критериев согласия. На практике обычно принимается .

Суть проверки равномерности по косвенным признакам сводится к следующему. Генерируемая последовательность чисел разбивается на две последовательности:

Рис. 4.11. Проверка равномерности последовательности

Затем проводится следующий эксперимент. Вели выполняется условие

то фиксируется наступление некоторого события и в счетчик событий добавляется единица. После опытов, когда генерировано N число, в счетчике будет некоторое число

Геометрически условие (4.13) означает, что точка находится внутри четверти круга радиусом что иллюстрируется рис. 4.11, б. В общем случае точка всегда попадает внутрь единичного квадрата. Тогда теоретически вероятность попадания этой точки в четверть круга

Если числа последовательности равномерны, то в силу закона больших чисел теории вероятностей при больших N относительная частота

Проверка стохастичности последовательностей псевдослучайных чисел наиболее часто проводится методами комбинаций и серий [7,11, 25]. Сущность метода комбинаций сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) числа единиц (нулей) в -разрядном двоичном числе На практике длину последовательности N берут достаточно большой и проверяют все разрядов или только I старших разрядов числа

Теоретически закон появления единиц в I разрядах двоичного числа описывается исходя из независимости отдельных разрядов биномиальным законом распределения:

где — вероятность появления единиц в I разрядах числа — вероятность появления единицы (нуля) в любом разряде числа

Тогда при фиксированной длине выборки N теоретически ожидаемое число появления случайных чисел с единицами в проверяемых I разрядах будет равно

После нахождения теоретических и экспериментальных вероятностей или чисел различных значениях гипотеза о стохастичности проверяется с использованием критериев согласия [7, И, 18, 21].

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

где

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

После разбиения последовательности на серии первого и второго рода будем иметь, например, последовательность вида

Так как случайные числа в данной последовательности независимы и принадлежат последовательности равномерно распределенной на интервале ,

то теоретическая вероятность появления серии длиной в последовательности длиной в N опытах (под опытом здесь понимается генерация числа х, и проверка условия определится формулой Бернулли:

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

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

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

В общем случае корреляционный момент дискретных случайных величин и с возможными значениями определяется по формуле

где — вероятность того, что примет значение

Корреляционный момент характеризует рассеивание случайных величин и их зависимость. Если случайные числа независимы, то . Коэффициент корреляции

где — средние квадратические отклонения величин

При проведении оценок коэффициента корреляции на ЭВМ удобно для вычисления использовать следующее выражение:

где

При вычислениях сначала рационально определить суммы:

При любом для достаточно больших N с доверительной вероятностью 0 справедливо соотношение

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

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

есть наибольшее целое число, такое, что при 0 событие не имеет места. Это означает, что все числа в пределах отрезка апериодичности не повторяются.

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

Способ экспериментального определения длины периода Р и длины отрезка апериодичности сводится к следующему [29]. Запускается программа генерации последовательности с начальным значением и генерируется V чисел . В большинстве практических случаев можно полагать . Генерируются числа последовательности и фиксируется число

Затем программа запускается повторно с начальным числом и при генерации очередного числа проверяется истинность события Если это событие истинно: то вычисляется длина периода последовательности Проводится запуск программы генерации с начальными числами При этом

Рис. 4 12. Экспериментальное определение длины периода и длины отрезка апериодичности: а — вариант 1,6 — варяаят 2

фиксируется минимальный номер при котором истинно событие и вычисляется длина отрезка апериодичности . Если Р оказывается истинным лишь для то .

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

Пример 4.5. Необходимо показать, что в последовательности чисел описываемой уравнением

при простом модуле М можно так выбрать коэффициент Я, что при любом взаимно простом с М, длина отрезка апериодичности, совпадающая а этом случае с длиной периода Р, будет Иначе говоря, надо найти, при каких условиях равенство

справедливо при минимальном значении

Можно записать [см. (4.11)], что поэтому (4.14) имеет место при

(здесь существенно, что взаимно просто с ).

По условию требуется, что наименьший показатель степени удовлетворяющий (4.15) и называемый показателем А по модулю М, был равен. Для любого простого модуля М существует значений Я (первообразных корней), удовлетворяющих уравнению (4.15) при где — функция Эйлера, определяемая как число натуральных чисел взаимно простых с М. Для простого модуля имеем

Таким образом, доказано существование многих Я, при которых повторение элементов последовательности наступит на числе что и требовалось доказать.

Для алгоритмов получения последовательностей чисел общего вида (4.10) экспериментальная проверка является сложной (из-за наличия больших Р и а расчетные соотношения в явном виде не получены. Поэтому в таких случаях целесообразно провести теоретическую оценку длины отрезка апериодичности последовательности Для этого воспользуемся элементарной вероятностной моделью, рассмотренной в следующем примере [4, 36, 37].

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

Так как математическое ожидание случайной величины с такой функцией распределения равно то при получим Такая оценка длины отрезка апериодичности «груба», но полезна на практике для предварительного определения с целью дальнейшего уточнения экспериментальным путем.

Рассмотрим некоторые особенности статистической проверки стохастичности псевдослучайных последовательностей. Для такой проверки могут быть использованы различные статистические критерии оценки, например критерии Колмогорова, Пирсона и т. д. Но в практике моделирования чаще всего пользуются более простыми приближенными способами проверки [29, 37].

Для проверки равномерности базовой последовательности случайных чисел можно воспользоваться такими оценками:

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

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

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

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

гораздо больше, чем при Однако при этом возрастает сложность метода, что приводит к увеличению затрат машинного времени на получение чисел и ограничивает возможности его применения на практике.

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

где функции различны.

В этом случае в основном используется формула и только когда кратно М, последовательность «возмущается», т. е. реализуется переход к формуле Целое число М называется периодом возмущения.

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