Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 70
Текст из файла (страница 70)
С»1. [Иннцналнзация.[ Присвоить р»- е/(а + е). (Это вероятность того, что используется распределение Сь) С»2. [Генерирование случайной велячнны с распределением С.[ Генерировать независимые равномерно распределенные случайные величины (/ н К где 1' з» О. Если Ь' < р, присвоить Х е- 1'Ы' и 4 +- е "; иначе — присвоить Х е- 1 — 1п1' и й е- Х' '. (Сейчас Х имеет плотность д, а 4 =/(Х)/сй(Х) ) СЗ. (Отброситьу) Генерировать новую равномерно распределенную случайную величину РЗ Кази Н > ро возвратиться к шагу 02. $ Среднее число итераций равно с = (а+ е)/(еГ(о+ 1)) < 1.4.
Существует несколько способов улучшения этой процедуры. Можно заменить )г случайной величиной У, имеющей показательное распределение со средним 1, которая генерируется, допустим, с помощью алгоритма Б, а затем присвоить Х е- е 1' илн Х е- 1+ У в обоих случаях. Более того, если присвоить 4 +- ре в первом случае и д е- р+ (1 — р)Х" ' во втором, то можно использовать первоначальную случайную величину Н вместо того, чтобы снова генерировать ее на шаге СЗ. Наконец, если 6' < р/е, можно принять Ъ'Ы' немедленно, не расходуя на вычисление о около 30% времени.
1У (а) Е(з') = 1 — (1 -р)'™ для х > О. (Ь) С(з) = рз/(1 — (1 — р)з). (с) Среднее равно 1/р, среднеквадратичное отклонение равно — р/р. Для дальнейших вычислений заметим, что если Н(з) = и+ (1 — д)з, то Н'(1) = 1- д и Н" (1) + Н'(1) — (Н'(1)) = д(1 — о), поэтому среднее и дисперсия 1/Н(з) равны гà — 1 и д(4-1) соответственно (см. раздел 1.2.10). В этом случае д = 1/р, дополнительный множителы в знаменателе С(з) добавляет к среднему 1. 13.
Присвоить Н +- )у~ + Нз — 1, где /1г~ и Нз — независимые случайные величины, имеющие геометрическое распределение с параметром р. (Рассмотрите производящую функцию.) 19. Присвоить Н е- Ю~ + + Н~ — Ь где Ю (независимые. — Нрилс ред.) — случайные величины, имеющие геометрическое распределение с параметром р. (Это число неудач перед 1-м успехом, когда осуществляется последовательность независимых испытаний, каждое из которых приводит к успеху с вероятностью р.) ДЛя 1 ш р м -' И ВООбщв, КОГда СрЕдНЕЕ ЗваЧЕНИЕ (т. Е, Г(1 - р)/р) раСПрЕдЕЛЕНИя Мапб, можно упростить вычисление вероятностей р = (' „'+")р'(1 — р)" последовательно для и = О, 1, 2,..., как показано в следующем алгоритме. В1.
(Инициализация.) Присвоить Н е- О, 4 э- р', г +- д и генерировать равномерно распределенную случайную величину Ь; (Будет выполняться 4 = рл и г = ро + + рл на протяжении всего алгоритма, выполнение которого остановится, как только получим Н < г ) ВЗ. (Итерация ) Если У > г, присвоить Ж е- лГ+ 1, ч +- о(1 — р)(с — 1+ Ж)/Н, г +- г+ о и цовторнть этот шаг. Иначе — возврат З/ н конец. $ (Интересный метод для отрицательного биномиального распределения с произвшчьно большим действительным значением 1 предложил Р. Денге (К.
Ьейег), Сначала нужно генерировать случайную величину Х, имеющую гамма-распределение порядка Ь а затем положить Н равной случайной величине с пуассоновским распределением со средним, равным Х(1 — р)/р.) 20 К1 = 1+(1-Л/В) К1. Еогда выполнен шаг К2, алгоритм завершается с вероятностью Х/В; когда выполнен шаг КЗ, переход к шагу Б.1 происходит с вероятностью Е/В. Справедливо следующее. К1 В/А В/А В/А В/А К2 0 В/А О В/А ЕЗ 0 0 В/А В/Л вЂ” 1/А К4 В/А В/А — //А В/А — Е/А В/А — Х/А — Е/А 21.
В= /8/е ш 1.71553; А = з/я/2 ш 1.25331. Так как в з/а - Ьо Ив = (а — Ьи)згз Я(а — Ьи) - 3~)/Ьь, получим / ш )'~~~и~/а — Вида = ~ а~'"з/Ьз, где а = 4(1+)пс) и Ь ж 4с. Когда с = еы4, 1 принимает максимальное значение э/5/е ш 1.13020. Наконец, чтобы вычислить Ю, понадобятся следующие формулы для интегрирования: /~/Ьи-евтдиы-'Ьта зГзагсе(п(2иа/5-1)+-,'Ьа ' /й-авау(2ие/Ь-1), /з/М+ав г(и= — об~а ш~)пЬ/Ьи+ои~+и~/е+Ь/2~/о)+т~Ьо"'Ли+оп~(2иа/Ь+1), где е, Ь > О. Пусть иа шаге ВЗ выполняется проверка "Хз > 4е* '/(/ — 4х", тогда внешняя область попадет в верхнюю часть прямоугольника, когда и = г(х) = (е* — э/от* — 2ех)/2ех.
(г(х) случайио принимает максимальное значение в точке х = 1/2, в которой г(х) не диффеРенциРУема)) СпРаведливо Е = /е'~*~ ( з/2/е — Ли — аиЦ) Ип, где Ь = 4е' г и а = 4х. Е принимает максимальное значение возле точки х = —.35, где оио приближенно равно Е ш .29410. 22. (Решени» Дж.
Марсалья (С. Машей)(а).) Рассмотрим "непрерывное пуассоновское распределение", определенное следующим образом: гу(х) = /„е '1* ' й/Г(х) лчя х > О. Если Х имеет это распределение, то и [Х) имеет пуассоновское распределение, так как С(х + 1) — С(х) = е "д"/х!. Если д большое, С приближенно нормально. Следовательно, гг~ 0(г'„(х)) приближенно линейно, когда Е'„(х) — функция распределения иормальиой случайной величииы со средним и дисперсией, равными д, т, е. Р„(х) = г'((х —;и)/~/д), где Г(х) — функция нормального распределения (10). Пусть д(х) — реально вычисляемая функция, такая, что [сг' 0(Ре(х))-у(х)[ < е для — со < х < оо. Сейчас можно эффективно геиерировать пуассоновскую случайную величину следующим образом: геиерировать нормальную случайную величину Х и присвоить У е- у(д+ /йХ), Ф е- [К1, М е- [У + Ц. Затем, если [1' — М[ > е, получаем иа выходе Ю, иначе пз выходе будет И вЂ” [а~-0(Р(Х)) < и[, Этот подход применим также к бииомиальиому распределению с Г(1+ 1) /," ( ") "Г()Г(~ — )' поскольку [П( 0(П)1 — величина, имеющая бииомиальиое распределение с параметрами (1, р) и б приближенно нормально.
[См. также альтернативный метод, предложенный Аренсом и Дитером (АЬгепе апб ?Несег, Сошрп1)лб 2$ (1980), 193 — 208).) 23. Да. Второй метод дает распределение [сов 20[, где д — равномерно распределенная случайная величина между О и к/2. (Предполагается, что У = г сов 8, 1' = гзш 0.) 25. Ц = (.10101)з. Обычно двоичное представление формируется с использованием 1 для ч' и Π— для Л слева направо, затем прибавляется 1.
Этот метод [см. (Точер К. Д.) К. П. Тосйег, з. Воу. Ягаа Яос, В16 (1954)., 49[ может привести к эффективному геиерированию независимых двоичных разрядов с заданной вероятностью р, а также ясцользоваться при генерирования случайиых величии с геометрическим и бииомиальным распределением. 26. (а) Верно; ~„Рг(Хв = Ь)Рг(Хз = и — Ь) = с "' '"'(д~ + дз)"/п1 (Ь) Неверно„ поскольку, если пз Р О, Хг — АГт может быть отрицательным. 27. Пусть двоичное представление р имеет вид (.Ь»ЬтЬз... )и Поступим далее в соответствии со следующими правилами. В1. (Инициализация,) Присвоить гл»- й 7»«»- О, 1' »- 1. (В этом алгоритме и» обозначает количество моделируемых равномерно распределенных величин, для которых соотношение с р еще неизвестно, так как их старшие 2 — 1-двоичные разряды совпадают с этими же разрядами числа р, ««' — число моделируемых случайных величин, о которых известно, что они меньше р.) В2.
(Взгляд на следующий столбец двоичных разрядов.) Генерировать случайное целое число М с биномивльным распределением («и, 5»). (Сейчас М означает число неизвестных случайных величин, таких, что их Оай разряд ие совпадает с Ь«,) Присвоить гл»- и» вЂ” М, если Ьз = 1, то присвоить Ж»- )»'+ М, ВЗ. [Сделано?) Если и» = 0 или если остаощиеся двоичные разряды (.Ь,+»Ь,+з, ..)» р все равны нулю, алгоритм завершен, Иначе — присвоить/ е- 2+1 и возвратиться к шагу В2. $ (Когда Ь, = 1 для бесконечного числа 1', среднее число итераций А«удовлетворяет равенствам А.=О; А.=1+ — ~'~ ~/А, д >1. 1 «из 2., Ы Положив А(с) = 2 А а"/п1, получим А(з) = е' — 1+ А(1г)е««~ Поэтому А(з)е ' = 1-е *+ А(1э)е *«» ж 2„(1- е ««з ) = 1 — е « - ~ „~,(-а)"/(и!(2" -1)) и Ам=1+~ ~ / =1+ — "=1йп+ — +-+/е(п)+О(п ) у~~ (-1)» ы -1 ю 15/ 2»-1 и+1 1п2 2 в обозначениях упр.
5.2.2-43.) 28. Генерируем случайную точку (рп..., у„) на единичной сфере и предположим, что л = »~~ а»9~. Генерируем независимую равномерно распределенную случайную величину ЬЬ Если р" +'У < К~/~ а» у»У, то на выходе получится точка (9»/р,..., р„/р); в остальных СЛуЧаяХ НаЧИНаЕМ СмаЧаЛа. ЗДЕСЬ Кг = ППП((Яа»у»Э)" /(Л,а»»р»Г) ) 2 я»Г ж 1) = а„" есзи па„> а~ ((и+ 1)/(а» + о ))~~~(а»а„/и)" — в остальных случаях.
29, Предположим, что Х„+» = 1, затем присвоим Х»»- Х,С»'«" или Х» +- Х»+»е лля Ь и, и — 1, ., 1, где П» — равномерно распределеннав случайная величина или У» — случайная величина с показательным распределением. (АСМ Тгавз. Ма»Ь. Яоггиаге 6 (1980), 359-364. Этот метод введен в употребление в 60-х годах Давидом Сенешолом (РатЫ Бепеэсйо!), см. работу Ашег. Ясаййгзс(ал 26,4 (Сего(»ег, 1972), 56-57.
Альтернатива состоит в генернровании и равномерно распределенных случайных чисел и их сортировке наибатее быстрым методом. Предложенный здесь метод является особенно полезным, если только требуется несколько наиболыпих или наименьших Х«. Заметим, что (Ф '1(Х»),...„г(»1(Х„)) соответствуют упорядоченным случайным величинам с функцией распределения Е.] 90. 1"енерировать случайные числа Е» -- -д ' 1п У» „Яг = Я, — д ' Ьа(гм ...
до тех нор, пока не выполнится 2 е» > 1. На выходе получим (Хз, Ъ)) = /(Еу) лля 1 <,1 < «и, где У((йдЬ»... Ьз«)г) = (( Ь»Ь»... Ь«)м( Ь»»Ь,+»... Ьг«)г)- Если менее старшие двоичные разряды значительно менее случайны, чем более старший двоичный разряд, то надежнее (но медленнее) положить, что /((.Ь»Ьг... Ьм)т) = ((.Ь!Ьз . Ьг -»)м (-ЬзЬ» .. Ьз«)з) 31. (а) Достаточно рассмотреть случай, когда й = 2, так ках агХг + " + агХ» = Х сов В+ 1'гйпВ при Х = Хм созВ = аг и У м (агХг+ . + аьХь)/з1пВ. И справедливо равенство -гг/г гз(2 Рг(ХсоаВ+ УешВ < я) ~ е Иеог(зсгид+ гзщВ < к) 2я у,, — с " ' липе(и<я) =(10) 2я ~ми после подстшювкн и = есоеВ+1е(пВ, с = -езшВ+ссоеВ.
(Ь) Существуют числа а > 1 и В > 1, такие, что (о зг+ а ы)/т/2 = 1 и ВВ гг + 1~8 ы = 1, поскольку числа Л„растут экспоненциально по н согласно свойствам линейных рекуррентиых соотношений. Если отказаться от формы линейного рекурреитного соотношения, скажем, испачьзуя рекуррентиое соотношение Л = Л -ысозВ„+ Х ы юпВ„, где В выбрано равномерно в (О ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
