Пусть Xl и Х2 - независимые случайные величины, имеющие гамма-распределение соответственно порядка а и Ь. Присвоить X Xi/{Xi + Х2). Другим полезным для малых а и b методом является использование присвоений

Fi С/У" и Г2 и,

повторяемых до тех пор, пока не получится Yi +Y2 < 1; тогда X i- У1/(У1 + F2). [См. работу М. Д. Йонка (М. D. Johnk, Metrika 8 (1964), 5-15).] Еще одним подходом, если а и b - целые числа, которые не настолько велики, является присвоение X Ь-й самой большой по величине из а -- 6 - 1 независимых равномерно распределенных случайных величин (см. упр. 9 в начале гл. 5). [См. также более прямой метод, описанный Р. Ч. С. Ченгом (R. С. Н. Cheng, САСМ 21 (1978), 317-322).]

3) -распределение с и степенями свободы (3.3.1-(22)) можно получить, если положить, что X <г- 2Y, где Y - случайная величина, имеющая гамма-распределение порядка и/2.

4) F-распределение (распределение отношения дисперсий) со степенями свободы ui и U2 определено следующим образом:

где а; > 0. Пусть Fi и F2 - независимые случайные величины, имеющие Х-рас-пределение со степенями свободы ui и 12 соответственно. Положим X i- Y1V2IY2V1 или X <г- i/2F/i/i(l - Y), где Yk, к - 1,2, - случайные величины, имеющие бета-распределение с параметрами i/i/2 и 1/2/2.

5) t-распределение с и степенями свободы определено следующим образом:

Пусть Fi - нормально распределенная случайная величина (среднее - О, дисперсия - 1) и F2 - случайная независимая от Fi величина, имеющая -распределение с и степенями свободы. Положим X YxJ/Y. С другой стороны, когда v > 2, можно поступить следующим образом. Пусть Fi - нормально распределенная случайная величина (среднее" - О, дисперсия - 1) и F2 - независимая от нее случайная величина, имеющая показательное распределение со средним 2/(1/ - 2). Положим Z *г- Yl{v - 2) и отбросим (Fi,F2), если е~~ > 1 - Z. Иначе положим

XF/\/(l-2/i/)(l-Z).

Последний метод предложен Джорджем Марсалья, Math. Сотр. 34 (1980), 235-236. [См. также работу А. Дж. Киндермана, Дж. Ф. Монахама и Дж. Дж. Рамаджа (А- J- Kinderman, J. F. Monahan, and J. G. Ramage, Math. Сотр. 31 (1977), 1009-1018).]

6) Случайные точки на n-мерной сфере единичного радиуса. Пусть Xi, Х2, Х„ - независимые нормально распределенные случайные величины (среднее - О,

дисперсия - 1); требуемая точка выбирается на единичной сфере следующим образом:

(Xi /г, Х2/г, ..., А„/г), где г = sJ+ Xj + + XI (38)

Если мы вычисляем Xk, используя метод полярных координат (алгоритм Р), необходимо каждый раз вычислять две независимые случайные величины X*:, = 1,2, и в обозначениях алгоритма выполняется равенство Xf-I-A" = -2 In 5. Так можно сэкономить немного времени, требуемого для вычисления г. Справедливость (38) вытекает из того факта, что функция распределения точки {Xi,..., Хп) имеет плотность, зависяпдую только от расстояния от начала координат, поэтому при проецировании на единичную сферу она имеет равномерное распределение. Данный метод впервые был предложен Дж.- В. Брауном (G. W. Brown, Modern Mathematics for the Engineer, First series, edited by E. F. Beckenbach (Бекенбах Э. Ф.), New York: McGraw-Hill, 1956, 302). Чтобы получить случайную точку внутри n-мерной сферы, Р. П. Брент (R. Р. Brent) предложил взять точку на поверхности этой сферы и умножить ее координаты на U".

Для размерности 3 можно использовать значительно более простой метод, так как каждая координата этой точки равномерно распределена между -1 и 1. Если найти V"i, V2 и S, используя шаги Р1-РЗ алгоритма Р, искомая точка на повер.хности шара будет иметь вид (aVi, аТ, 25-1), где а = 2\/1 - 5. [Robert Е. Кпор, САСМ 13 (1970), 326.]

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

1) Геометрическое распределение. Если некоторое событие происходит с вероятностью р, то число N независимых испытаний, проведенных до появления события (или до .момента, когда событие происходит впервые), имеет геометрическое распределение, т. е. TV = 1 с вероятностью р, N = 2 с вероятностью (1 - р)р, ..., N = п с вероятностью {1-)"~р. Это, по существу, ситуация, которая уже рассматривалась в разделе 3.3.2. Данное распределение непосредственно связано с числом циклов алгоритмов из настоящего раздела, как и циклы на шагах Р1-РЗ метода полярных координат.

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

N \lnU/\n{l-p)]. (39)

Чтобы проверить эту формулу, заметим, что \lnU/1п(1 - р) = п тогда и только тогда, когда п - 1 < InU/1п(1 - р) < п, т. е. (1 - р)"~ > U > [1 - р)" и это происходит с требуемой вероятностью (1 - р)"~р. Величину In С/ можно также за.меннть величиной -Y, где Y имеет показательное распределение со средним 1.

Частный случай, когда р= , совсем просто реализуется на бинарном компьютере, так как формула (39) сводится к присвоению N +- \-\gU], т. е. N становится на единицу больше числа старших нулевых разрядов в двоичном представлении числа и.

2) Биномиальное распределение (t,p). Если некоторое событие происходит с вероятностью р и проводится t независимых испытаний, то общее число появлений этого события равно п с вероятностью (Jp"(l - (см. раздел 1.2.10). Другими словами, если генерируется Ui, Ut, достаточно подсчитать, сколько из них не превосходят р. Для малых t с помощью этого метода легко можно получить точное значение Л.

Для больших t можно генерировать случайную величину X, имеющую бета-распределение с целыми параметрами аиЬ, где а + Ь-1 - t. При этом эффективно получаем Ь-й наибольший из t элементов, не беспокоясь о генерировании остальных элементов. Сейчас, если X > р, положим N i- Ni, где Ni имеет биномиальное распределение (а - 1, р/Х), так как оно показывает, сколько из а - 1 случайных величин в области [О.. X) меньше, чем р. Если X < р, положим N <- а + Ni, где Ni имеет биномиальное распределение (Ь - 1, (р - Х)/(1 - X)), так как Ai показывает нам, сколько из Ь - 1 случайных чисел в области [X.. 1) меньше р. Выбирая а = I + [t/2\, параметр t можно свести к разумной величине после примерно Igt преобразований такого рода. (Этот подход предложен И. Г. Аренсом, который также предложил альтернативный метод для значений параметра t средней величины; см. упр. 27.)

3) Пуассоновское распределение со средним р. Пуассоновское распределение соотносится с показательным распределением, как биномиальное распределение с геометрическим: если некоторое событие может произойти в любой момент времени, то пуассоновское распределение - это распределение случайной величины, которая равна числу событий, происшедших в единиц} времени (при некоторых других ограничениях. - Прим. ред.). Например, число альфа-частиц, которые испускаются радиоактивным веществом за одну секунду, имеет распределение Пуассона.

В соответствии с этим принципом можно получитЬ} пуассоновскую случайную величину N, генерируя независимые показательные случайные величины Al, Хг,...

со средним 1/р и останавливаясь, как только будет получено Ai Н-----1-А > 1, где

N <г- т - I. Вероятность того, что Al -f- • • • -Ь Хщ > 1, равна вероятности, что случайная величина, имеющая гамма-распределение порядка т, будет > р, а это равно t"\~et/{m - 1)1. Следовательно, вероятность, что N = п, равна

1 /-оо 1 /-оо п

- ее-Ыг--,-- / t"-ie-di = e-, > 0. (40)

n\J (n-iy.J n!

При генерировании показательной случайной величины методом логарифма, описанным выше, нужно остановиться, когда -(Inf/i + \nUm)/p > 1- Упрощая это выражение, получим, что требуемую пуассоновскую величину можно получить, вычислив е~> до определенной точности и генерируя одну или более равномерно распределенных случайных величин Ui, U2, ... до тех пор, пока их произведение не будет удовлетворять неравенству Ui... Um < е~. Окончательно полагаем, что N <- т - I. В среднем нужно генерировать р + I равномерно распределенную величину, поэтому рассматриваемый подход очень полезен, когда р не слишком велико.

Когда р большое, можно получить метод порядка log , используя сведения о том, как соотносятся гамма- и биномиальное распределения высокого порядка.