Шаг 1. [Основной цикл] For J 1 to М do through шаг 3 od; and STOP.

Шаг 2. [Генерация нового необработанного случайного числа] Set (В*Х(У-l)+i()(mod MOD)i).

(Число X{J) должно лежать в интервале 0Х(/)< <MOD.)

Шаг 3. [Генерация следующего случайного числа] Set Y {J) fr- X {J)IIAOD. (YiJ) будет лежать в интервале 0< К(/)<:1 и будет обладать желаемым распределением.)

Возьмем К=0, M0D=2i», В=101 и Х(0)=432. Первые числа, выработанные алгоритмом LCM, будут

Xi=624 Fi=624/1024=0.610 X 2=560 72=560/1024=0.546 Хз=240 Уз=240/1024=0.234 Х4=688 7,=688/1024=0.673 Х5=880 75=880/1024=0.859 Хб=816 Г,=816/1024=0.796 Х,=496 У.=496/1024= 0.484 Х8=944 Г"=944/1024=0.923

Существует глубокая и интересная теория по вопросу «хорошего» выбора К, В, MOD и Х(0), которая выходит за рамки этой книги. Для наших целей достаточно просто утверждения, что существует такой выбор этих параметров, при котором алгоритм LCM будет генерировать числа в интервале [О, 1), представляющиеся непредсказуемыми и удовлетворяющие определенным статистическим критериям. Для всех практических целей эти числа оказываются последовательностью наблюдений равномерно распределенной случайной переменной.

Равномерно распределенные случайные переменные можно, в частности, использовать при моделировании случайных переменных с другими распределениями. Начнем с двух относительно простых примеров.

Пусть X - дискретная случайная переменная со следующим распределением:

Р(Х=1)=0.1 Р(Х=2)=0.2 Р(Х=3)=0.4 Р(Х=4)=0.2 Р(Х=5)=0.1

Как можно получить от компьютера «выборки» из X, такие, что значение Х=1 встретится приблизительно в 10% случаев, значение Х=2 приблизительно в 20% случаев и т. д.

) По определению, если а (mod т)=х для целых аит.тох есть (целый) остаток от деления а на т. Например, 5 (mod 3)=2,

Так как сумма всех вероятностей в распределении равна единице, проще всего разбить интервал [О, 1) на пять подынтервалов и назначить каждое возможное значение X подынтервалу, длина которого равна вероятности того, что X реально принимает это значение. В нашем примере мы могли бы установить следующее соответствие:

Х=1<[0, 0.1) Х=2<->[0.1, 0.3) Х=3[0.3, 0.7) Х=4<->[0.7, 0.9) Х=5<[0.9, 1.0)

Для машинного моделирования случайной переменной X генерируют стандартное (равномерно распределенное) случайное число Z. Если ZIO, 0.1), берем Х=1; если ZgIO.I, 0.3), берем Х=2. После извлечения большого числа выборок наблюдаемое распределение частот X должно быть довольно близко к искомому распределению.

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

Теперь рассмотрим использование генератора равномерно распределенных случайных чисел. Хороший простои алгоритм основывается непосредственно на центральной предельной теореме и на преобразовании, с помощью которого можно превратить распределение N{[1, о) в N (О, 1) и наоборот.

Следующая теорема является простейшей из центральных предельных теорем, и именно ее часто называют центральной предельной теоремой.

Теорема 6.3.3 (центральная предельная теорема). Пусть Xi, Хг, . . ., Х„ - последовательность независимых, одинаково распределенных случайных переменных со средним р и дисперсией о. Распределение вероятности для случайной -.переменной

а У п

стремится к N(0, 1) при поо. •

Теорема 6.3.4. Если случайная переменная Y имеет распределение N{[1, а), то переменная

имеет распределение Л/(О, 1). Обратное также верно.

Доказательство теоремы 6.3.3 требует некоторой квалификации и поэтому опущено; доказательство теоремы 6.3.4 очевидно и оставлено в качестве упражнения.

Algorithm NRN (нормальные случайные числа) для генерации нормально распределенных случайных чисел с использованием генератора равномерно распределенных случайных чисел RANN. Равномерно распределенные случайные числа применяются для выработки случайных чисел с распределением (О, 1) на основе теоремы 6.3.3. Случайные числа с распределением Л(0, 1) преобразуются в случайные числа N{[1, а) с использованием теоремы 6.3.4. Необходимо задать на входе в алгоритм значения п, р,, а. Предполагается, что нужна последовательность F(l), F(2), . . ., Y{M) из М случайных чисел. Шаг 1. [Основной цикл] For У 1 to М do through шаг 3 od; and STOP.

Шаг 2. [Генерация нового случайного числа с распределением Л(0, 1)] CALL RANN п раз; на выходе процедуры - последовательность Хи • • •» Х, set

Z(J), Xi+Xi+...+X„-(n/2) Уп/12

(Так как каждое Х обладает равномерным распределением со средним 1/2 и дисперсией 1/12, то Z(J) будет обладать распределением Л(0, 1) согласно теореме 6.3.3. Практически для большинства применений достаточно и=10.) Шаг 3. [Генерация нового числа с распределением N {[л, а)] Set YiJ)aZiJ)+ii.

Теперь рассмотрим две более совершенные процедуры. Начнем с общей задачи моделирования произвольного непрерывного распределения с использованием равномерного распределения.

Для любой случайной переменной X интегральная функция распределения определяется как

F{a)=P{Xa), -оо<с<оо.

Легко убедиться, что любая интегральная функция распределения обладает следующими свойствами:

1) F{a) - неубывающая функция а; .

2) lim Р(й)=1;

3) lim F(a)=0;

4) pla<5i<b)=F(b)-F{a) для всех a<b.

Если X - непрерывная случайная переменная с плотностью f{x), то

Р(а) = Р(Ха)= J f(x)dx