8.2. Моделирование случайных величин

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

Равномерно распределенные в интервале [0, 1] последовательности случайных чисел можно получить тремя способами:

• использование таблиц случайных чисел (табличный способ);

• применение генераторов случайных чисел (аппаратный способ);

• метод псевдослучайных чисел (программный способ).

8.2.1. Табличный способ

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

	0	1	2	3	…	9
	0.1	0.1	0.1	0.1	…	0.1

При составлении таких таблиц выполняется требование, чтобы каждая из этих цифр 0; 1; ...; 9 встречалась примерно одинаково часто и независимо от других с вероятностью .

Самая большая из опубликованных таблиц случайных чисел содержит 1000 000 цифр. Таблицы случайных чисел требуют тщательной проверки с помощью специальных статистических тестов.

8.2.2. Аппаратный способ

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

Полученные с помощью идеального генератора псевдослучайные последовательности чисел должны:

• состоять из квазиравномерно распределенных чисел;

• содержать статистически независимые числа;

• быть воспроизводимыми;

• иметь неповторяющиеся числа;

• получаться с минимальными затратами машинного времени;

• занимать минимальный объем машинной памяти.

Недостатки данного способа получения случайных чисел следующие:

1. Трудно проверить качество вырабатываемых чисел.

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

8.2.3. Алгоритмический способ

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

. (8.3)

Данные алгоритмы представляют рекуррентные соотношенияпервого порядка, для которых начальное числоx₀и постоянные параметры уже заданы.

Метод серединных квадратов

Пусть имеется 2n-разрядное число, меньшее 1:.

1. Возведем его в квадрат: .

2. Отберем средние 2nразрядов, которые будут являться очередным числом псевдослучайной последовательности.

Недостаток метода: наличие корреляции между числами последовательности, в некоторых случаях может отсутствовать.

Конгруэнтные процедуры генерации

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

Два целых числа α и β конгруэнтны или сравнимы по модулю m,m– целое число, тогда и только тогда, когда существует такое целое числоk, что α – β = km, т.е. разность α – β делится наm, и числа α и β дают одинаковые остатки от деления на абсолютную величину числаm.

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

, (8.4)

где , , , M– неотрицательные целые числа.

Раскроем рекуррентное соотношение (8.4):

(8.5)

Если заданы начальные числа X₀, , , M(8.5) последовательность целых чисел {X_i}, составленную из остатков от деления наМчленов последовательности.

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

Мультипликативный метод

Задается последовательность неотрицательных целых чисел , не превосходящихМ, рассчитанных по формуле

, (8.6)

т.е. это частный случай соотношения (8.4) при  = 0.

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

В машинной реализации наиболее удобна версия M = p^g, гдеp– число цифр в системе счисления в ЭВМ;g– число битов в машинном слове. Тогда вычисление остатка от деления наМсводится к выделениюgмладших разрядов делимого. Преобразование целого числав рациональную дробь из интервалаосуществляется подстановкой слева отдвоичной или десятичной запятой.

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

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

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

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

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

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

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

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

Смешанный метод

Позволяет вычислить последовательность неотрицательных целых чисел {X_i}, не превосходящихМ, по формуле

.

Отличием от мультипликативного метода является  ≠ 0.

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

Достоинства метода псевдослучайных чисел:

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

2. Малый объем памяти ЭВМ для программирования.

3. Любое из чисел легко воспроизвести.

4. Качество генерируемых случайных чисел достаточно проверить один раз.

Подавляющее число расчетов по методу Монте-Карло осуществляется с использованием псевдослучайных чисел. От последовательности случайных чисел, равномерно распределенных в интервале [0, 1], нетрудно перейти к последовательности случайных чисел с произвольным заданным законом распределения.