выполняются для любой константы с > 0. в упр. 21 доказывается, что с = е/* является наилучшей возможной константой для использования на шаге R2. Более сложная ситуация складывается на шаге R3, и в этом случае, кажется, не существует простого выражения для оптимального с, но вычислительные эксперименты показывают, что наилучшее значение с для шага R3 приблизительно равно е. Аппроксимирующей кривой (28) является касательная к истинной границе, когда и = 1/с.

Существует возможность получения быстрого метода путем разделения области на подобласти, с большинством из которых иметь дело намного быстрее. Конечно, подразумевается, что нужны дополнительные таблицы, как в алгоритмах МиГ. Интересная альтернатива, требующая меньшего числа вспомогательных таблиц, предложена Аренсом и Дитером в САСМ 31 (1988), 1330-1337.

5) Нормальная случайная величина из нормальной случайной величины. В упр. 31 обсуждается интересный подход, который позволяет экономить время работы, так как сразу использует нормальные случайные величины вместо равномерно распределенных случайных величин. Этот метод, введенный в употребление в 1996 году К. С. Уэллесом (С. S. Wallace), в настоящее время не нашел достаточного теоретического обоснования, но удовлетворяет многим эмпирическим критериям.

6) Преобразования нормального распределения. До сих пор рассматривалось нормальное распределение со средним, равным нулю, и среднеквадратичным отклонением, равным единице. Если X имеет такое распределение, то

Y = p + aX (29)

имеет нормальное распределение со средним, равным р, и среднеквадратичным отклонением, равным а. Кроме того, если Xi и Х2 - независимые нормальные случайные величины со средним, равным нулю, среднеквадратичным отклонением, равным единице, и

Yi=Pi+ агХг, Уг = Мг + 2 (pXi + /1X2), (30)

то Yi и У2 - зависимые нормально распределенные случайные величины со средними, равными р2, среднеквадратичными отклонениями, равными cti, стз, и коэффициентом корреляции р. (Для генерирования п переменных обратитесь к упр. 13.)

D. Показательное распределение. После равномерного и нормального распределений следующим наиболее важным распределением случайной величины является показат.ельное распределение. Такие распределения появляются в ситуациях "время поступления". Например, если радиоактивное вещество излучает альфа-частицы так, что одна частица в среднем испускается каждые р секунд, то время между двумя последовательными испусканиями имеет показательное распределение со средним, равным р. Это распределение задается формулой

F(a;) = 1-е-/", х>0. (31)

1) Метод логарифма. Очевидно, если у = F{x) = 1 - е~, то х - F~\y) = -р\п{1 - у). Следовательно, -/х1п(1 - U) имеет экспоненциальное распределение

согласно (7). Поскольку I - U равномерно распределено, когда U имеет такое же распределение, можно сделать вывод, что

X = -ti\nU (32)

имеет экспоненциальное распределение со средним, равным /х. (Случай, когда и = О, должен трактоваться особо; его можно заменять любым подходящим значением 6, так как вероятность возникновения этого случая крайне мала.)

2) Метод случайной минимизации. Как было показано в алгоритме F, существует простой и быстрый способ альтернативного вычисления логарифма равномерной случайной величины. Следующий особенно эффективный подход разработали Дж. Марсалья, М. Сибая (М. Sibuya) и И. Г. Арене (J. Н. Ahrens) [см. САСМ 15 (1972), 876-877].

Алгоритм S {Экспоненциальное распределение со средним, равным р). Этот алгоритм вырабатывает экспоненциальные случайные величины на бинарном компьютере, используя равномерно распределенные случайные величины с точностью до {t + 1) двоичных разрядов. Постоянные

QW = !f + Sf£.- + 2fi. *>1. (33)

могут вычисляться заранее до тех пор, пока они не превысят следующее значение: Q[k] > 1 - 2-*.

51. [Получить и и сдвинуть.] Генерировать (t-1-l) двоичных разрядов равномерной случайной двоичной дроби U = (.Ьохг ... 6)2; определить местоположение первого нулевого двоичного разряда bj и избавиться от старших j + 1 двоичных разрядов с помощью присвоения U <г- (.6+1... 6)2. (Как и в алгоритме F, среднее число отбрасываемых двоичных разрядов.равно 2.)

52. [Немедленное принятие?] Если U < 1п2, присвоить X (- p{j\n2 + U) п завершить алгоритм. (Отметим, что Q[l] = In 2.)

53. [Минимизация.] Найти наименьшее А; > 2, такое, что U < Q[k]. Генерировать к новых равномерно распределенных случайных величин Ui, ..., Uk я присвоить V<-mm{Ui,...,Uk).

54. [Получение ответа.] Присвоить X i- p{j + V) In 2.

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

Е. Другие непрерывные распределения. Кратко рассмотрим, как обращаться с другими распределениями, которые достаточно часто возникают на практике.

1) Гамма-распределение порядка а > О определяется как

F{x)=- Te-e-Ut, х>0. (34)

W Jo

При а - 1 оно является показательным распределением со средним, равным 1; при а = I - это распределение случайной величины Z", где Z - нормально

распределенная случайная величина (среднее равно О, дисперсия - 1). Если А" и Y - независимые случайные величины, имеющие гамма-распределение порядка а и Ь соответственно, то X + Y имеет гамма-распределение порядка а + Ь. Так, например, сумма к независимых случайных величин, имеющих показательное распределение со средним, равным 1, имеет гамма-распределение порядка к. Если метод логарифма (32) использовался для генерирования таких случайных величин, имеющих показательное распределение, то здесь необходимо вычислить только один логарифм: X +- -l-n{Ui.. .Uk), где Ui, Uk - равномерно распределенные случайные величины, не равные нулю. Таким методом можно генерировать все случайные величины с гамма-распределением порядка а, где а - целое. Для завершения картины соответствующий метод для О < а < 1 приведен в упр. 16.

Простой метод логарифма также очень медленный, когда а большое, поскольку он требует [а\ равномерно распределенных случайных величин. Более того, существует реальный риск, что произведение Ui... f/[aj приведет к переполнению (потере плавающей точки). Для большого а следующий алгоритм, предложенный И. Г. Аренсом, является достаточно эффективным и легко записьшается в терминах стандартных программ. [См. Ann. Inst. Stat. Math. 13 (1962), 231-237.]

Алгоритм A (Гамма-распределение порядка а > I).

Al. [Генерирование кандидата.] Присвоить Y <г- tan(7rf/), где U - равномерно распределенная случайная величина, и присвоить X i- \/2о - IF -I- а - 1. (Вместо tan(7rC/) можно использовать метод полярных координат, вычисляя отношение V2/V1, как на шаге Р4 алгоритма Р.)

А2. [Принимать?] Если X < О, возврат к шагу А1. Иначе - генерировать равномерно распределенную случайную величину V и возвратиться к шагу А1, если У >(1+у2)ехр((а-1)1п(Х/(а-1)) -уДУ). Иначе - принять А.

Среднее время выполнения шага А1 < 1.902, когда а > 3.

Существует также заманчивый подход для больших а, основанный на таком замечательном факте, что га.мма-распределение случайных величин приблизительно равно аХ, когда X - нормально распределенная величина со средним значением 1 - 1/(9а) и среднеквадратичным отклонением 1/у/9а [см. работы Э. Б. Уилсон (Е. В. Wilson) и М. М. Гилферти (М. М. Hilferty), Ргос. Nat. Acad. Sci. 17 (1931), 684-688, а также Дж. Марсалья (G. Marsaglia, Computers and Math. 3 (1977), 321-325)]*.

В некоторой степени усложненный, но значительно более быстрый алгоритм, который генерирует случайные величины, имеющие гамма-распределение, за приблизительно вдвое большее время, чем случайные величины, имеющие нормальное распределение, приведен в статье И. Г. Аренсаи У. Дитера, САСМ 25 (1982), 47-54, в которой содержится полезное описание принципов, используемых при построении алгоритма.

2) Бета-распределение с положительными параметрами а и b определяется как

() = ГШ г - *)" 0<х<1. (35)

Г(а) Г(Ь) Уо

* Заменить "--{За - 1)" иа "-(За - 1)" на шаге 3 алгоритма на с. 323.