из упр. 7 можно использовать здесь с А; = 32 для вычисления Pj и Yj, после чего получим 1 < У- < 15 для 1 < j < 32. Присвоим Ро <- Рз2 (которое равно 0) и Уо <- У32. Затем присвоим Zj ч- 1/(5 - 5Р,) и Yj ч- Yj - Zj для О < j < 32 и <- 1/(5Р,) для 1 < j < 15.

Пусть Л = i и /j+i5(x) = у/21ж{е- - e->/°)/pj+i5 для 5j < х < 5j + Л. Также пусть aj = fj+ib{Sj) для 1 < j < 5, bj = fj+ib{Sj) для 6<j< 15; bj = -/j+i5(5j + h) для 1 < j < 5 и aj = fj+ib{xj) + {xj - Sj)bj/h для & <j < 15, где Zj - корень уравнения fj+ib{xj) = -bj/h. Наконец присвоим Dj+ib 4- aj/bj для \ < j < 15, £,+15 Ч- 2ЪЦ для 1 < j < 5 и <- l/(e(2j-i)/5 - 1) для 6 < J < 15.

Табл. 1 была подсчитана с использованием следующих промежуточных величин: (pi, ... ,рз1) = (.156, .147, .133, .116, .097, .078, .060, .044, .032, .022, .014, .009, .005, .003, .002, .002, .005, .007, .009, .010, .009, .009, .008, .006, .005, .004, .002, .002, .001, .001, .003); (хе, ...,ххъ) = (1.115, 1.304,1.502,1.700,1.899,2.099,2.298,2.497,2.697,2.896); (ai,...,ai5) = (7.5,9.1,9.5,9.8,9.9, 10.0,10.0,10.1,10.1,10.1,10.1,10.2,10.2,10.2, 10.2); (bi,..., bis) = (14.9,11.7,10.9,10.4,10.1, 10.1,10.2,10.3,10.4,10.5,10.6,10.7,10.7,10.8,10.9).

11. Пусть g{t) = eliel для t > 3. Так как G(x) = Ц g{i)dt = 1-6"-/ случайную величину А с плотностью д можно вычислить, если положить X <- С~(1-У) = ч/9 - 2 In V. Сейчас е~ < («/3)е" " для t > 3. Таким образом будет получен обоснованный метод отбраковки, если принять X с вероятностью f{X)/cg{X) = 3/Х.

12. Справедливо равенство /(х) = х/(х) - 1 < О для х > О, так как /(х) = х~ - е" /~е"/ dt/t для х > 0. Пусть х = a-i и = х + 2 In 2, тогда

VVJ-e-dt = \e-"f{y) < ive-=/V(x) = 2" Следовательно, у > aj.

13. Возьмем bj = fij; рассмотрим сейчас задачу с ij = О для каждого j. В матричных обозначениях, если Y = АХ, где А - (aij), необходимо, чтобы выполнялось АА = С = (cij). (В других обозначениях, если Yj = ajkXk, среднее значение YiYj равно aikajk-) Если это матричное уравнение может быть решено для А, то оно может быть решено и тогда, когда А - треугольная матрица, так как А = BU для некоторой ортогональной матрицы U и некоторой треугольной матрицы В, а ВВ = С. Требуемое решение в виде треугольной матрицы может быть получено в результате решения уравнений afi = си, аиаг! = С12, ail +022 = С22, aaasi = С13, 021031 -I-022О32 = С23, •. последовательно для ац, a2i, 022, 031, аз2 и т. д. [Замечание. Ковариационная матрица должна быть неотрицательно определена, так как среднее значение величины {yjYjY равно сумме Cijyiyj, которая должна быть неотрицательна. И решение всегда существует, когда С неотрицательно определена, так как С = {7~Miag(Ai,..., А„)(7, где собственные числа Aj неотрицательны, и f7~diag(\/A7,..., \/X)U и будет решением.]

14. F{x/c), если с > 0; ступенчатая функция [х > 0], если с = О или 1 - F{x/c), если с < 0.

15. Функция распределения - Fi(x - t)dF2{t). Плотность - /i(x - t)f2{t)dt. Это называется сверткой заданных распределений.

16. Ясно, что, как и требуется f{t) < cg{t) для всех t. Так как 9it)dt = 1, то g{t) = Cf для о < t < 1, Се~ для t>l, где С = ае/{а + е). Случайную величину с плотностью д легко получить, как смесь распределений Gi(x) = х" для О < х < 1 и G2(x) = 1 - е~ для X > 1.

G1. [Инициализация.] Присвоить р •«- е/(а -I- е). (Это вероятность того, что используется распределение Gi.)

G2. [Генерирование случайной величины с распределением G.] Генерировать независимые равномерно распределенные случайные величины U и V, где У 0. Если

и < р, присвоить X <г- V" и g <- е ; иначе - присвоить X <- 1 - In V и q <- (Сейчас X имеет плотность д, я q = f{X)/cg{X).)

G3. [Отбросить?] Генерировать новую равномерно распределенную случайную величину и. Если и > q, возвратиться к шагу G2.

Среднее число итераций равно с - {а + е)/(еГ(о -t-1)) < 1.4.

Существует несколько способов улучшения этой процедуры. Можно заменить V случайной величиной У, имеющей показательное распределение со средним 1, которая генерируется, допустим, с помощью алгоритма S, а затем присвоить X •«- е"" или X 1 + Y в обоих случаях. Более того, если присвоить q 4- ре~ в первом случае ид <- р -t- (1 - р)Х°"" во втором, то можно использовать первоначальную случайную величину и вместо того, чтобы снова генерировать ее на шаге G3. Наконец, если U < р/е, можно принять V" немедленно, не расходуя на вычисление g около 30% времени.

17. (а) F(z) = 1 - (1 -р)- для Z > 0. (Ь) С(г) = р2/(1 - (1 -р)2). (с) Среднее равно 1/р, среднеквадратичное отклонение равно л/1 - р/р- Для дальнейших вычислений заметим, что если Я(2) =g-t-(l -д)2, то Я(1) = 1-д и Я"(1)-t-Я(1) - (Я(1)) = g(l-g), поэтому среднее и дисперсия 1/Я(г) равны д -1 и g(g -1) соответственно (см. раздел 1.2.10). В этом случае g = 1/р, дополнительный множитель z в знаменателе G{z) добавляет к среднему 1.

18. Присвоить N <- Ni + N2 - 1, где Ni и - независимые случайные величины, имеющие геометрическое распределение с параметром р. (Рассмотрите производящую функцию.)

19. Присвоить N Ni -\-----\- Nt -t, где Nj (независимые. - Прим. ред.) - случайные

величины, имеющие геометрическое распределение с параметром р. (Это число неудач перед t-M успехом, когда осуществляется последовательность независимых испытаний, каждое из которых приводит к успеху с вероятностью р.)

Для t = р = I и вообще, когда среднее значение (т. е. t{l -р)/р) распределения мало, можно упростить вычисление вероятностей р„ = (~""")p4l ~ Р)" последовательно для п = о, 1, 2, ..., как показано в следующем алгоритме.

81. [Инициализация.] Присвоить iV 0, g 4- р, г 4- g и генерировать равномерно распределенную случайную величину U. (Будет выполняться q = Pn и г = ро + + PN на протяжении всего алгоритма, выполнение которого остановится, как только получим и < г.)

82. [Итерация.] Если U >г, присвоить Л •«- N+1, q •«- g(l -p){t-l+N)/N, г <r + q и повторить этот шаг. Иначе - возврат N и конец.

[Интересный метод для отрицательного биномиального распределения с произвольно большим действительным значением t предложил Р. Леже (R. Leger). Сначала нужно генерировать случайную величину X, имеющую гамма-распределение порядка t, а затем положить N равной случайной величине с пуассоновским распределением со средним, равным .(1 -р)/р.]

20. R1 = 1 + {1 - A/R)-R1. Когда выполнен шаг R2, алгоритм завершается с вероятностью I/R; когда выполнен шаг R3, переход к шагу R1 происходит с вероятностью E/R. Справедливо следующее.

R1 R/A R/A R/A R/A

R2 О R/A О R/A

R3 О О R/A R/A-I/A

R4 R/A R/A-I/A R/A-E/A R/A-I/A-E/A

21. R = у/8/ё « 1.71553; A = as 1.25331. Так как

получим / = £uVa-budu = ab, где a = 4(1 + Inc) и 6 = 4c. Когда с = e/ / принимает максимальное значение f x/S/e « 1.13020. Наконец, чтобы вычислить Е, понадобятся следующие формулы для интегрирования:

JVbu-au du = ba-axcsm{2ua/b-l) + \ba-Wbu-au (2uo/b-l),

JVbu+au du = -ba-\n{Vbu+au + Uy/a+b/2y/a} + ba-Wbu+au{2ua/b+l),

где а,Ь>0. Пусть на шаге R3 выполняется проверка "Х > Ae/U - 4ж", тогда внешняя область попадет в верхнюю часть прямоугольника, когда и = г{х) = (е - Уе - 2еж)/2еж. (г(ж) случайно принимает максимальное значение в точке х = 1/2, в которой г{х) не дифференцируема!) Справедливо Е = /o(i/2/e - \/Ьи - au2)du, где Ь = Ае" и а = 4ж. 15 принимает максимальное значение возле точки х = -.35, где оно приближенно равно Е W .29410.

22. (Решение Дж. Марсалья (G. Marsaglia).) Рассмотрим "непрерывное пуассоновское распределение", определенное следующим образом: G(z) = е~4~ dt/r(z) для z > 0. Если X имеет это распределение, то и [Х\ имеет пуассоновское распределение, так как G(z + 1) - G(z) = e~>fj,/xl. Если fj. большое, G приближенно нормально. Следовательно, С~ЦГ{х)) приближенно линейно, когда F{x) - функция распределения нормальной случайной величины со средним и дисперсией, равными р, т. е. F{x) = F{{x - n)ly/Jl), где F{x) - функция нормального распределения (10). Пусть д{х) - реально вычисляемая функция, такая, что \С~\Р,{х))-д{х)\ < е для -оо < ж < оо. Сейчас можно эффективно генерировать пуассоновскую случайную величину следующим образом: генерировать нормальную случайную величину X и присвоить У <- д{ц + /JIX), N <- \Y\, М ч-[У + jj. Затем, если У - М > е, получаем на выходе N, иначе на выходе будет M-[G-4(F(X))<M].

Этот подход применим также к биномиальному распределению с

G(x)= f и-\1-иГ-

du (-

Г(ж)Г(« + 1-ж)

поскольку L~()J - величина, имеющая биномиальное распределение с параметрами {t,p) и G приближенно нормально.

[См. также альтернативный метод, предложенный Аренсом и Дитером (Ahrens and Dieter, Computing 25 (1980), 193-208).]

23. Да. Второй метод дает распределение cos26, где в - равномерно распределенная случайная величина между О и 7г/2. (Предполагается, что U = г cos б, V = г sin б.)

25. II = (.10101)2. Обычно двоичное представление формируется с использованием 1 для V и О - для Л слева направо, затем прибавляется 1. Этот метод [см. (Точер К. Д.) К. D. Tocher, J. Лоу. Stat. Soc. В16 (1954), 49] может привести к эффективному генерированию независимых двоичных разрядов с заданной вероятностью р, а также использоваться при генерировании случайных величин с геометрическим и биномиальным распределением.

26. (а) Верно: Рг(М = fc)Pr(iV2 = п - к) = е--Цщ + р2)"/п1 (Ь) Неверно, поскольку, если р2 ф О, Ni - N2 может быть отрицательным.