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

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

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

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

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

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

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

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

Таблица.

Способ	Достоинства	Недостатки
Аппаратный	Запас чисел не ограничен. Расходуется мало операций ЭВМ. Не занимает место в оперативной памяти ЭВМ.	Требуется периодическая проверка. Нельзя воспроизводить последовательности. Используется специальное устройство. Необходимы меры по обеспечению стабильности.
Табличный	Требуется однократная проверка. Можно воспроизводить последовательности.	Запас чисел ограничен. Занимает много места в оперативной памяти или необходимо время на обращение к внешней памяти.
Алгоритмический	Требуется однократная проверка. Можно многократно воспроизводить последовательности. Занимает мало место в оперативной памяти ЭВМ. Не используются внешние устройства ЭВМ.	Запас чисел последовательности ограничен ее периодом. Существенные затраты машинного времени.

 

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

{х_i}=х₀, x_l,..., x_N, представляющих собой реализации независимых, равномерно распределенных на интервале (0, 1) случайных величин {ξ_i} = ξ₀, ξ₁, …, ξ_N или – в статистических терминах – повторную выборку из равномерно распределенной на (0, 1) генеральной совокупности значений величины.

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

.

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

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

Такое распределение имеет математическое ожидание M[ξ] = 1/2 и дисперсию D[ξ] = 1/12.

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

Случайная величина ξ, имеющая квазиравномерное распределение в интервале (0, 1), принимает значения x_i=i/(2ⁿ - 1) с вероятностями p_i= 1/2ⁿ, i = .

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

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

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

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

Наибольшее применение в практике моделирования на ЭВМ для генерации последовательностей псевдослучайных чисел находят алгоритмы вида x_i+1 = Ф(х_i), представляющие собой рекуррентные соотношения первого порядка, для которых начальное число х₀ и. постоянные параметры заданы.

Хорошую последовательность случайных чисел может породить только такая функция х_i+1 =Ф (х_i), график которой достаточно плотно заполняет единичный квадрат.

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

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

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

Конгруэнтные процедуры являются чисто детерминированными, так как описываются в виде рекуррентного соотношения

Х_i+1 = λХ_i + μ(modМ),

где X_i, λ, μ, М – неотрицательные целые числа.

Если заданы начальное значение Х₀, множитель λ и аддитивная константа μ, то (4.11) однозначно определяет последовательность целых чисел {X_i}, составленную из остатков от деления на М членов последовательности {λⁱХ₀ + μ(λⁱ - 1)/(λ - 1)}. Таким образом, для любого i≥l справедливо неравенство X_i<M. По целым числам последовательности {X_i} можно построить последовательность {х_i} = {Х_i /М} рациональных чисел из единичного интервала (0, 1).

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

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

Мультипликативный метод. Задает последовательность неотрицательных целых чисел {X_i}, не превосходящих М, по формуле X_i+1 = λX_i(modM).

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

Для машинной реализации наиболее удобна версия М = р^g, где р – число цифр в системе счисления, принятой в ЭВМ (р = 2 для двоичной и р = 10 для десятичной машины); g – число битов в машинном слове. Тогда вычисление остатка от деления на М сводится к выделению g младших разрядов делимого, а преобразование целого числа X_i в рациональную дробь из интервала х_i (0, 1) осуществляется подстановкой слева от X_i двоичной или десятичной запятой.

Алгоритм построения последовательности для двоичной машины М = 2^g сводится к выполнению таких операций:

1. Выбрать в качестве Х₀ произвольное нечетное число.

2. Вычислить коэффициент λ = 8t±3, где t – любое целое положительное число.

3. Найти произведение λХ₀, содержащее не более 2g значащих разрядов.

4. Взять g младших разрядов в качестве первого члена последовательности X₁, а остальные отбросить.

5. Определить дробь x_l = X₁/2^g из интервала (0, 1).

6. Присвоить X₀ = X₁.

7. Вернуться к п.3.

Смешанный метод. Позволяет вычислить последовательность неотрицательных целых чисел {X_i}, не превосходящих М, по формуле X_i+1=λX_i+μ(modM), т.е. в отличие от мультипликативного метода μ ≠ 0. С вычислительной точки зрения смешанный метод генерации сложнее мультипликативного на одну операцию сложения, но при этом возможность выбора дополнительного параметра позволяет уменьшить возможную корреляцию получаемых чисел.

Качество конкретной версии такого генератора можно оценить только с помощью соответствующего машинного эксперимента.

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