Макеты страниц 4.3. ПРОВЕРКА И УЛУЧШЕНИЕ КАЧЕСТВА ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛЭффективность статистического моделирования систем на ЭВМ и достоверность получаемых результатов существенным образом зависят от качества исходных (базовых) последовательностей псевдослучайных чисел, которые являются основой для получения стохастических воздействий на элементы моделируемой системы. Поэтому, прежде чем приступать к реализации моделирующих алгоритмов на ЭВМ, необходимо убедиться в том, что исходная последовательность псевдослучайных чисел удовлетворяет предъявляемым к ней требованиям, так как в противном случае даже при наличии абсолютно правильного алгоритма моделирования процесса функционирования системы S по результатам моделирования нельзя достоверно судить о характеристиках системы [29, 37]. Проверка качества последовательностей. Результаты анализа системы S, полученные методом статистического моделирования на ЭВМ, существенно зависят от качества используемых псевдослучайных квазиравномерных последовательностей чисел. Поэтому все применяемые генераторы случайных чисел должны перед моделированием системы пройти тщательное предварительное тестирование, которое представляет собой комплекс проверок по различным статистическим критериям, включая в качестве основных проверки (тесты) на равномерность, стохастичность и независимость. Рассмотрим возможные методы проведения таких проверок, наиболее часто используемые в практике статистического моделирования систем. Проверка равномерности последовательностей псевдослучайных квазиравномерно распределенных чисел Оценка степени приближения, т. е. равномерности последовательности Суть проверки равномерности по косвенным признакам сводится к следующему. Генерируемая последовательность чисел
Рис. 4.11. Проверка равномерности последовательности
Затем проводится следующий эксперимент. Вели выполняется условие
то фиксируется наступление некоторого события и в счетчик событий добавляется единица. После Геометрически условие (4.13) означает, что точка
Если числа последовательности Проверка стохастичности последовательностей псевдослучайных чисел Теоретически закон появления
где Тогда при фиксированной длине выборки N теоретически ожидаемое число появления случайных чисел После нахождения теоретических и экспериментальных вероятностей При анализе стохастичности последовательности чисел
где Серией называется любой отрезок последовательности, состоящий из идущих друг за другом элементов одного и того же рода, причем число элементов в отрезке (а или После разбиения последовательности
Так как случайные числа то теоретическая вероятность появления серии длиной
В случае экспериментальной проверки оцениваются частоты появления серий длиной Проверка независимости элементов последовательности псевдослучайных квазиравномерно распределенных чисел проводится на основе вычисления корреляционного момента [4]. Случайные величины В общем случае корреляционный момент дискретных случайных величин
где Корреляционный момент характеризует рассеивание случайных величин
где При проведении оценок коэффициента корреляции на ЭВМ удобно для вычисления использовать следующее выражение:
где
При вычислениях сначала рационально определить суммы:
При любом
Если найденное эмпирическое значение Характеристики качества генераторов. При статистическом моделировании системы S с использованием программных генераторов псевдослучайных квазиравномерных последовательностей важными характеристиками качества генератора является длина периода Р и длина отрезка апериодичности
есть наибольшее целое число, такое, что при 0 событие Очевидно, что использование при моделировании систем последовательности чисел Способ экспериментального определения длины периода Р и длины отрезка апериодичности Затем программа запускается повторно с начальным числом
Рис. 4 12. Экспериментальное определение длины периода и длины отрезка апериодичности: а — вариант 1,6 — варяаят 2 фиксируется минимальный номер В некоторых случаях достаточно громоздкий эксперимент по определению длин периода и отрезка апериодичности можно заменить аналитическим расчетом, как это показано в следующем примере. Пример 4.5. Необходимо показать, что в последовательности чисел
при простом модуле М можно так выбрать коэффициент Я, что при любом
справедливо при минимальном значении Можно записать [см. (4.11)], что
(здесь существенно, что По условию требуется, что наименьший показатель степени Таким образом, доказано существование многих Я, при которых повторение элементов последовательности Для алгоритмов получения последовательностей чисел Пример 4.6. Пусть имеется конечное множество, содержащее N различных чисел. Проведем последовательность независимых опытов, в каждом из которых из этого множества извлекается и записывается одно число. Вероятность извлечения любого числа в каждом из опытов равна
Так как математическое ожидание случайной величины с такой функцией распределения равно Рассмотрим некоторые особенности статистической проверки стохастичности псевдослучайных последовательностей. Для такой проверки могут быть использованы различные статистические критерии оценки, например критерии Колмогорова, Пирсона и т. д. Но в практике моделирования чаще всего пользуются более простыми приближенными способами проверки [29, 37]. Для проверки равномерности базовой последовательности случайных чисел
Для проверки таблиц случайных цифр обычно применяют различные тесты, в каждом из которых цифры классифицируются по некоторому признаку и эмпирические частоты сравниваются с их математическими ожиданиями с помощью критерия Пирсона [29, 46]. Для проверки аппаратных генераторов случайных чисел можно использовать те же приемы, что и для проверки последовательностей псевдослучайных чисел, полученных программным способом. Особенностью такой проверки будет то, что проверяются не те числа, которые потом будут необходимы для моделирования системы S. Поэтому кроме проверки качества выдаваемых генератором случайных чисел должна еще гарантироваться устойчивая работа генератора на время проведения машинного эксперимента с моделью Улучшение качества последовательностей. В силу рассмотренных преимуществ основное применение в практике имитационного моделирования систем находят различные программные способы получения чисел. Поэтому рассмотрим возможные методы улучшения качества последовательностей псевдослучайных чисел. Одним из наиболее употребительных методов такого улучшения является употребление вместо формул вида (4.9), представляющих собой рекуррентные формулы первого порядка, рекуррентных формул порядка
где начальные значения гораздо больше, чем при Для получения последовательности псевдослучайных чисел с большой длиной отрезка апериодичности
где функции В этом случае в основном используется формула Все рассмотренные критерии проверки последовательностей псевдослучайных чисел являются необходимыми при постановке имитационных экспериментов на ЭВМ с моделью Мы, но об их достаточности можно говорить лишь при рассмотрении задачи моделирования конкретной системы S.
|
Оглавление
|