Характеристики качества генераторов

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

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

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

Способ экспериментального определения длины периода Р и длины отрезка апериодичности Ь сводится к следующему [29]. Запускается программа генерации последовательности {х<} с начальным значением х₀ и генерируется V чисел х,. В большинстве практических случаев можно полагать Г=(1 ч-5) 10⁶. Генерируются числа последовательности {х,} и фиксируется число х_у.

Затем программа запускается повторно с начальным числом х₀ и при генерации очередного числа проверяется истинность события Р'{х, = х_к}. Если это событие истинно: г=/! и I=1₂ (*1 < *2 < Ю" ^то вычисляется длина периода последовательности Р=г₂—г₁. Проводится запуск программы генерации с начальными числами х₀ и х_Р. При этом фиксиру;

Рис. 4.12. Экспериментальное определение длины периода от длины отрезка апериодичности: а — варплят 1; б — принят 2.

ется минимальный номер г=/₃, при котором истинно событие Р" {х,=*|" _+<}, и вычисляется длина отрезка апериодичности /, = /₃ + Р (рис. 4.12, а). Если Р' оказывается истинным лишь для /= У, то Ь>У (рис. 4.12, 5).

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

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

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

справедливо при минимальном значении — 1. Можно записать [см. (4.11)], чтоЯГДтоёЛ/), поэтому (4.14) имеет место при.

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

По условию требуется, что наименьший показатель степени з^Р_ы{А), удовлетворяющий (4.15) и называемый показателем А по модулю Л/, был равен А/—1. Для любого простого модуля М существует ср (М— 1) значений Я (первообразных корней), удовлетворяющих уравнению (4.15) при Р_и {А) * <�р (М), где <�р (А/) — функция Эйлера, определяемая как число натуральных чисел т^М, взаимно простых с М. Для простого модуля М имеем ср (М) «А/— 1.

Таким образом, доказано существование многих Я, при которых повторение элементов последовательности {х,} наступит на (М~ 1)-м числе XV-ь ^т• *• 1_,=Р=М— 1, что и требовалось доказать.

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

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

Так как математическое ожидание случайной величины с такой функцией распределения равно >/я/2, то при АГ-" оо получим М[Цш>у/кЩ2. Такая оценка длины отрезка аппериодичности «груба», но полезна на практике для предварительного определения Ь с целью дальнейшего уточнения экспериментальным путем.

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

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

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

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

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

где начальные значения х₀, х_1У …, х,_, заданы. В этом случае длина отрезка аппериодичности 7, у такой последовательности при г> 1.

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

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

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

В этом случае в основном используется формула х_/+1=Ф (х<), и только когда I кратно А/, последовательность «возмущается», т. е. реализуется переход к формуле х_<+1 = 'Р (х_/). Целое число М называется периодом возмущения.

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