Сначала генерируем случайную величину X, имеюидую гамма-распределение порядка т = [рср\, где а - подходящая постоянная. (Так как X эквивалентно - \n[U\...Um), по существу, производим т шагов предыдущего метода.) Если Л < , полагаем N +- т + Ni, где Ni - пуассоновская случайная величина со средним fi - X, а если А > , то полагаем N <- Ni, где Ni имеет биномиальное распределение (т - 1,р/Х). Этот метод предложен И. Г. Аренсом и У. Дитером, которые предположили, что - хорошее значение для а.

Справедливость сформулированного утверждения, когда X > /х. является следствием такого важного принципа: "Пусть A"i, ..., Хщ - независимые показательные случайные величины с одинаковым средним и пусть Sj = Xi + + Xj и Vj = Sj/Sm ДЛЯ 1 < j < m. Тогда распределение VI, V2, Kn-i такое же, как распределение т - 1 независимых случайных величин, расположенных в порядке возрастания". Чтобы формально доказать этот принцип, подсчитаем вероятность того, что Vi < vi, Vjn-i < Vm-i, всли Зщ = s для произвольных значений О < vi < < Vm-i < 1. Пусть f{vi,V2,-.. ,Vm~i) - (гп - 1)-кратный интеграл

Jo Jo

fvm-ls - tl-----tm-1

тогда

f{VuV2,...,V,n-l) /0 Q dU2...

/(1,1,.-.,1) JoduiJldu2...Jl du„.-i

если произвести замену переменных ii = swi, ti+t2 =sw2, ...,tiH-----him-i = sUm-\-

Последнее отношение соответствует вероятности того, что равномерно распределенные случайные величины Ui, Um-i удовлетворяют неравенствам Ui < v\, Um-i < Vm~\, если задано, что они также удовлетворяют неравенствам U\ < <

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

G. Для дальнейшего чтения. Факсимиле письма фон Неймана (von Neumann), датированного 21 мая 1947 года, в котором метод отбраковки впервые увидел свет, появилось в Stanislaw Ulam 1909-1984, в специальном выпуске Los Alamos Science (Los Alamos National Lab., 1987), 135-136. В книге Non-Uniform Random Variate Generation JI. Девроя (L. Devroye) (Springer, 1986) обсуждается намного больше алгоритмов генерирования случайных величин с неравномерным распределением; там же подробно рассматривается эффективность каждого метода для типичных компьютеров.

В. Херманн и Г. Дерфлингер [W. Hermann and G. Derflinger, ACM Trans. Math. Software 19 (1993), 489-495] указали, что может быть опасно использовать метод отбраковки для линейных конгруэнтных генераторов с малыми множителями а и •УШ.

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

найти в книге Д. Э. Кнута и Э. Ч. Яо (D. Е. Knuth and А. С. Yao, Algorithms and Complexity, edited by J. F. Traub (New York: Academic Press, 1976), 357-428).

Упр. 16 рекомендуется как обзор различных методов, приведенных в этом разделе.

УПРАЖНЕНИЯ

1. [10] Пусть аир - действительные числа, а < /3. Как можно генерировать случайные действительные числа, равномерно распределенные между q и /3?

2. [М16] Пусть mil - случайное целое число, принимающее значения между О и m - 1 с одинаковыми вероятностями. Чему точно равна вероятность того, что [kU] = г, если О < г < fc? Сравните с требуемой вероятностью 1/fc.

► 3. [Ц] Как можно рассмотреть U в качестве целого числа и разделить его на fc, чтобы получить случайное целое число между О и fc - 1, вместо того чтобы выполнять умножение, как предложено в разделе. Тогда (1) было бы заменено на

ENTA 0; LDX U; DIV К

с результатом в регистре X. Хороший ли это метод?

4. [М20] Докажите два соотношения в (8).

5. [21 ] Предложите эффективный метод генерирования случайной величины с функцией распределения F{x) = рх + qx + гх (О < х < 1. - Прим. ред.), где р>0, д>0, г>0 Hp + q + r = l.

6. [НМ21] Величина Аполучена следующим образом.

Шаг 1. Генерировать две независимые равно.мерно распределенные случайные величины и W.V.

Шаг 2. Если U" + V >\, возврат к шагу 1; иначе - присвоить X <- С/.

Какова функция распределения А? Сколько времени выполняется шаг 1? (Найдите среднее и среднеквадратичное отклонения).

7. [20] (А. Дж. Уолкер (А. J. Walker).) Предположим, что имеется набор кубиков fc различных цветов, скажем Uj кубиков цвета Cj при 1 < j < fc, и fc коробок {Bi,. ..,Вк}, в каждую ИЗ которых можно поместить п кубиков. Кроме того, ni + + Uk = кп, так что кубики будут полностью заполнять коробки. Докажите (конструктивно), что всегда можно разместить кубики в коробках так, чтобы в каждой из них содержались кубики самое большее двух различных цветов. Действительно, можно устроить так, чтобы всякий раз в коробке Bj содержалось Два цвета, один из которых - цвет Cj. Покажите, как использовать это утверждение, чтобы подсчитать Р и У, требуемые в (3), при заданном вероятностном распределении {р\,... ,рк).

8. Покажите, что операцию (3) можно заменить операцией

если и<Рк, то A--XK+i; иначе А <-1 д--

(Таким образом, вместо V используется истинное значение U.) Будет ли это более удобным или подходящим для изменения Ро, Pi, ..., Pk-i-

9. [HMIO] Почему кривая f{x) на рис. 9 выпукла для Выпуклая кривая Вогнутая кривая X < 1 и вогнута для х > 1?

► 10. [НМ24] Объясните, как вычислить вспомогательные постоянные Pj, Qj, Yj, Zj, Sj, Dj, Ej, чтобы алгоритм М давал ответ с правильным распределением.

► 11. [НМ27] Докажите, что шаги М7 и М8 алгоритма М порождают случайную величину с хвостом, близким к нормальному распределению, т. е. вероятность того, что X < х должна быть точно равна

j\-"Ut I j\-"Ut, x>3.

[Указание. Покажите, что это частный случай метода отбраковки с g{t) = Cte~* для некоторого С]

12. [НМ23] (Р. П. Брент (R. Р. Brent).) Докажите, что числа Oj, определенные в (23), удовлетворяют соотношению

а - а 1 < 2 In 2 для всех j > 1-

[Указание. Если /(х) = е е~* dt, покажите, что /(х) < f{y) для О <х <у.]

13. [НМ25] Дано множество п независимых нормальных случайных величин Al, Аг, ..., Хп со средним О и дисперсией 1. Покажите, как найти константы bj и а;>, 1 < j < г < гг, такие, что если

yi=bi+aiiAi, 72=62+021X1+022X2, Yn=hn+an).X).+---+annXn,

то У1, У2, •.., Vn - зависимые нормально распределенные случайные величины, Yj имеют среднее pj и заданную ковариационную матрицу (cij). (Ковариации dj между У и Yj определяются как среднее значение случайной величины (У - Hi){Yj - щ). В частности, Cjj - это дисперсия Yj, квадрат их среднеквадратичных отклонений. Не все матрицы (c,j) могут быть ковариационными, и ваше построение, конечно, будет работать всякий раз, когда данное условие будет выполняться.)

14. [М21] Найдите распределение сА, если А - случайная величина с непрерывной функцией распределения F{x) и если с - постоянная (возможно, отрицательная).

15. [НМ21] Если Al и Х2 - независимые случайные величины с соответствующими функциями распределения Fi{x) и 2(х) и плотностями /i(x) = F[{x),fiix) = Fiix), какова функция распределения и плотность случайной величины Al +Х2?

► 16. [НМ22] (И. Г. Арене.) Предложите алгоритм для генерирования случайной величины, имеющей гамма-распределение порядка о, когда О < а < 1, с помощью метода отбраковки с cgit) = е~1Т{а) для О < t < 1 и с cg{t) = е~7Г(а) для < > 1.

► 17. [М24] Чему равна функция распределения F{x) случайной величины, имеющей геометрическое распределение с параметром р? Чему равна производящая функция G{z)? Чему равны среднее и дисперсия этого распределения?

18. [М24] Предложите метод вычисления случайной целочисленной величины N, такой, что N принимает значение п с вероятностью пр(1 -р)"", n > 0. (Когда р сравнительно малб, этот случай представляет особый интерес.)

19. [22] Случайная величина N с отрицательным биномиальным распределением с параметрами (<,р) принимает значения N = п с вероятностью ("")р(1 -р)"- (В отличие от обычного биномиального распределения t не обязано быть целым, так как эта величина неотрицательна для всех п, каково бы ни было t > 0.) Обобщая упр. 18, объясните как генерировать целые случайные числа N с этим распределением, когда t - малое положительное целое число. Какой вы предложите метод для < = р = ?

20. [М20] Пусть А - площадь заштрихованной области на рис. 13, R - площадь содержащего ее прямоугольника, / - площадь внутренней области, определенной на шаге R2, и Е - площадь между внутренней областью, отбрасываемой на шаге КЗ, и другой частью