9. 3. Методы имитации случайных факторов

Базовой последовательностью случайных чисел, используемой для формирования в ЭВМ случайных элементов различной природы, с различными законами распределения является совокупность случайных чисел с равномерным законом распределения:

где f(x) - дифференциальный закон распределения равномерно распределенных чисел x в интервале [a,b].

Строго говоря, на цифровой ЭВМ получить последовательность случайных величин с равномерным распределением не представляется возможным[1]. Поэтому, если считать, что число разрядов ЭВМ равно k, а случайное число сформировано согласно формуле:

где a_j = 0, P_j = ½; a_j = 1, 1 - P_j = ½, то x = i/(2^k – 1) принимает значение i/(2^k – 1), (i = 0, 1, 2, …, 2^k – 1) с вероятностью P_i = 1/2^k. Такое распределение чисел x называется квазиравномерным в интервале [0;1], причем математическое ожидание и дисперсия определяются следующими соотношениями:

, (9.2)

Из формул (9.2) видно, что математическое ожидание M[x] точно совпадает с генеральным средним для равномерного распределения в интервале [0;1], а дисперсия при k ® ¥ асимптотически стремится к дисперсии для равномерного распределения при a = 0, b = 1, равной 1/12.

Практически при k > 15 обеспечивается требуемая точность в имитационных исследованиях. Поэтому в дальнейшем будем говорить о равномерном законе, хотя в действительности при программном моделировании имеем дело с квазиравномерным законом. При выводе выражений (9.2) предполагалось, что x формируется на основе случайных чисел a_j, принимающих значения (0;1) с вероятностью P_j = 1/2, для чего в машине должен существовать случайный генератор, дающий строго случайные последовательности чисел a_j с соответствующим распределением. Так как в ЭВМ такого генератора нет, случайные числа вырабатываются программным путем, в силу чего они, строго говоря, не являются случайными, так как формируются на основе вполне детерминированных преобразований, поэтому их называют псевдослучайными. Такие последовательности случайных чисел являются периодическими, поэтому очень длинные последовательности, длина которых превосходит период, уже не будут строго случайными. Однако, если при моделировании количество обращений к программному датчику случайных чисел оказывается меньше периода, измеряемого количеством различных случайных чисел, то такая периодичность программного датчика не оказывает существенного влияния на результаты моделирования.

Основные достоинства программного способа получения псевдослучайных чисел состоят в следующем:

• не требуются специальные внешние устройства;

• получение чисел достаточно быстрое (обычно требуется 3 -10 команд на число);

• возможно повторное воспроизведение чисел;

• требуется только однократная проверка алгоритма получения заданной последовательности чисел.

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

x_r = j (x_r-1, x_r-2, ..., x₀).

Простейшим примером указанного способа получения случайных чисел, равномерно распределенных в интервале[0;1], может служить метод вычетов, в котором используется следующее рекуррентное соотношение:

x_i+1 = bx_i (mod M),

где выражение bx_i (mod M) означает остаток от деления произведения bx_i на число M; x_i+1 - очередное случайное число; x_i - предыдущее случайное число; b - некоторая константа; М - число, определяющее наибольшее значение получаемых случайных чисел.

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

1. выбрать в качестве параметра a₀ – произвольное нечетное число, например a₀ = 5¹³ при разрядности ЭВМ k = 32, M = 2³¹ – 1

2. вычислить коэффициент b по формуле b = 8c ± 3, где c – любое целое положительное число, в частном случае b = 5¹³;

3. вычислить произведение ba₀; взять k младших разрядов в качестве первого члена последовательности a₁, остальные отбросить;

4. провести нормализацию числа по формуле x₁ = a₁ / (2^k – 1);

5. вычислить очередное псевдослучайное число a₂ как k младших разрядов произведения ba₁ и вернуться к пункту 4.

Описанный генератор подвергался, как отмечено в [3] широкой экспериментальной проверке и проявил достаточно хорошие свойства. С другими аналитическими способами получения случайных чисел, равномерно распределенных в интервале [0;1], можно ознакомиться в [1]. В случае применения методов перемешивания очередное число последовательности получается путем хаотического перемешивания разрядов предыдущего случайного числа с помощью операций сдвига, специальных сложений и различных арифметических операций. Например, часто используются следующие комбинации операций для перемешивания разрядов предыдущего случайного числа:

• сдвиг предыдущего числа на некоторое число разрядов влево и специальное сложение результатов этого сдвига с предыдущим числом последовательности;

• сдвиг предыдущего числа на некоторое число разрядов влево и вправо и специальное сложение результатов этих сдвигов.

Данные операции заканчиваются взятием модуля и нормализацией. В качестве начальной константы для формирования последовательности обычно берут иррациональные числа

Имитация случайных событий. Пусть в результате эксперимента должно наступить одно из несовместимых событий A₁, A₂, …, A_k, …, A_n, которые образуют полную группу событий, то есть.

где P_k – вероятность наступления события A_k..

Разбиваем отрезок [0; 1] на n частей длиной P₁, P₂, …, P_n; при этом точки деления отрезка имеют следующие координаты:

Пусть теперь x – очередное число от генератора случайных чисел. Если l_k-1 £ x £ l_k то считаем, что произошло событие A_k.

Действительно,

P (A_k) = P (l_k-1 £ x £ l_k) = l_k – l_k-1 = P_k.

Рассмотренная процедура может быть положена в основу выбора направления передачи требований при моделировании замкнутых сетей массового обслуживания.. Аналогичным образом можно моделировать дискретные случайные величины при конечном числе их значений. Если имеем дискретную случайную величину y, причем y = 1 с вероятностью P, а y =0 с вероятностью 1 – P, то при имитации ее на ЭВМ необходимо каждый раз решать следующую систему неравенств: если 0 £ x_i £ P, то y_i = 1; если P £ x_i £ 1, то y_i = 0, где x_i – очередное случайное число от генератора случайных равномерно распределенных чисел.

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

Метод обратной функции. Он основан на использовании следующей теоремы. Если x – случайная величина, равномерно распределенная на отрезке [0; 1], то случайная величина y, являющаяся решением уравнения:

, (9.3)

имеет плотность распределения f (y).

Данный метод позволяет сформулировать правило генерирования случайных чисел, имеющих произвольное непрерывное распределение f (y):

• вырабатывается случайное число x_i генератором случайной равномерной последовательности;

• случайное число y_i , имеющее распределение f (y), находится из решения уравнения

Таким образом, последовательность чисел x₀, x₁, x₂, …, x_i преобразуется в последовательность y₀, y₁, y₂, …, y_i, имеющую заданную плотность распределения f (y). Рассмотрим примеры.

Пример 1. Необходимо получить последовательность чисел, равномерно распределенных на отрезке [a,b]. Тогда, используя (9.3) имеем:

,

откуда y_i = x_i (b – a) +a.

Пример 2. Необходимо получить последовательность чисел, имеющих распределение по показательной функции: