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

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

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

Способ генерации	Суть способа	Достоинства	Недостатки
аппаратный (физический)	При этом способе случайные числа вырабатываются специальной электронной приставкой — генератором (датчиком) случайных чисел,— служащей в качестве одного из внешних устройств ЭВМ. Таким образом, реализация этого способа генерации не требует дополнительных вычислительных операций ЭВМ по выработке случайных чисел, а необходима только операция обращения к внешнему устройству (датчику). В качестве физического эффекта, лежащего в основе таких генераторов чисел, чаще всего используются шумы в электронных и полупроводниковых приборах, явления распада радиоактивных элементов и т. д.	- Запас чисел не ограничен - Расходуется мало операций вычислительной машины - Не занимается место в памяти машины	- Требуется периодическая проверка - Нельзя воспроизводить последовательности -Используется специальное устройство - Необходимы меры по обеспечению стабильности
табличный (файловый)	Случайные числа, оформленные в виде таблицы, помещаются во внешнюю или оперативную память ЭВМ, предварительно из них сформирован соответствующий файл (массив чисел). Рационально использовать при сравнительно небольшом объеме таблицы и соответственно файла чисел, когда для хранения можно применять оперативную память. Хранение файла во внешней памяти не рационально, так как вызывает увеличение затрат машинного времени при моделировании системы S из-за необходимости обращения к внешнему накопителю. Возможны промежуточные способы организации файла, когда он переписывается в оперативную память периодически по частям. Это уменьшает время на обращение к внешней памяти, но сокращает объем оперативной памяти, который можно использовать для моделирования процесса функционирования системы S.	- Требуется однократная проверка - Можно воспроизводить последовательности	- Запас чисел ограничен - Занимает много места в оперативной памяти или необходимо время на обращение к внешней памяти
алгоритмический (программный)	Способ основан на формировании случайных чисел в ЭВМ с помощью специальных алгоритмов и реализующих их программ. Каждое случайное число вычисляется с помощью соответствующей программы по мере возникновения потребностей при моделировании системы на ЭВМ.	- Требуется однократная проверка - Можно многократно воспроизводить последовательности чисел - Занимает мало места в памяти машины - Не используются внешние устройства	- Запас чисел последовательности ограничен ее периодом - Существенные затраты машинного времени

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

. Непрерывная случайная величина  имеет равномерное распределение в интервале (а, Ь), если ее функции плотности и распределения соответственно примут вид:

   

Определим числовые характеристики случайной величины , принимающей значения x, – математическое ожидание, дисперсию и среднее квадратическое отклонение соответственно:

.

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

 

Такое распределение имеет математическое ожидание  и дисперсию .

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

Случайная величина , имеющая квазиравномерное распределение в интервале (0, 1), принимает значения  с вероятностями , .

Математическое ожидание и дисперсия квазиравномерной случайной величины соответственно имеют вид

.

Таким образом, математическое ожидание квазиравномерной случайной величины совпадает с математическим ожиданием равномерной случайной последовательности интервала (0, 1), а дисперсия отличается только множителем , который при достаточно больших n близок к единице.

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

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