AOP_Tom2 (1021737), страница 177
Текст из файла (страница 177)
Метод слабее (1) почти в каждом случае, так что мы его не рекомендуем. К сожалению, однако, операция "Мшп!г" в (1) отсутствует во многих языках высокого уровня (см. упр. 3.2.1.1-3). Деление тп/й. возможно, наилучшее, когда ьМтп1гэ отсутствует. 4. шах(Хм Хг) < х тогда и только тогда, когда Хг < х и Хг < х; гпш(Хц Хг) > х тогда и только тогда, когда Лг > х и Хг > х.
Вероятность того, что два независимых события происходят одновременно, равна произиедению вероятностей этих событий. 5. Получим независимые равномерно распределенные случайные величины (7г и с7г. Положим Х ~- Уг. Если Пг > р, положим Х г — шах(Х, Уэ), где (/э — третья равномерно распределенная величина. Если Уг > р+ д, положить также Х г- шах(Х, (гг), где (/г— четвертая равномерно распределенная случайная величина.
Этот метод можно очевидным образом обобщить для любой случайной величины с полиномиальной функцией распре- Окружность Уз+Уз = 1 Рис. А-4. "Область принятия" для алгоритма из упр. б. деления и даже с функцией распределения, представимой в виде степенного ряда (как показано, например, в алгоритме Б, вместо максимизации использующем минимизацию). Можем поступить и следующим образом (предложение М. Д. Мак-Лареиа (М. П.
Мас- 1,вгео)): если Пз < р, присвоить Х з — 17з/р; иначе, если (/з < р + о, присвоить Х з- тах((Ь з — р)/д, 17з); иначе присвоить Х з — шах(((7з -р — д)/г, (/з, (/з). Этот метод по сравнению с другими требует меиьше времени иа получение равиомерно распределенных случайных чисел, несмотря на то что он требует больше арифлзетических операций и иесколько менее устойчив численно, 6. Р(х) = Аз/(Аз + 4з), где Аз и Лз — площади, показанные на рис. А-4, так что /о т/1 У '(У 2 .
2 Р(г) =, = — агсгбо х -Ь -х~/1 — хз зо З/1 у оу Вероятность окончания процедуры на шаге 2 равна р = я/4. Процедура продолжается до завершения иа шаге 2, поэтому число выполнений шага 2 имеет геометрическое распределение. Характеристиками этого числа являются (тшо 1, ате 4/я, свах ж, Йет (4/я) т/1 — л/4) согласно упр. 17.
7. Если У = 1, тогда оз = и, и задача тривиальна. В противном случае всегда можно найти з ф з, такое, что и; < и < и . Заполните В, и, кубиками цвета С, и и — и, цвета Сз.. Затем замените п„иа и — и, и исключите цвет С,. Теперь перед нами стоит та же задача, но /з меньше на 1, Следовательно, по индукции задача имеет решение. Следующий алгоритм можно использовать, чтобы подсчитать Р и Р для таблиц из (3).
Образуем набор пар (рц 1)... (рз,/с) и рассортируем их по первой компоненте, получив иабор (Ф оз) . (Уыаз), где Уз « йы Присвоим и з — )з и будем повторять следующие операции до тех пор, пока не получим о = О: присвоим Р(оз — 1) з — /зоз и 1'(оз — 1) з — х„„. Удалим (дм а~) и (д, а ), поместим новый элемент (у — (1/)с — оз), а„) иа его собственное место в наборе и уменьшим и на 1. (Если р, < 1//з, то алгоритм никогда ие поместит х, в таблицу для Е, Этот факт безоговорочно используется в алгоритме М.
Алгоритм пытается максимизировать вероятность тога, что Р < Рк в (3), отбирая у самого "богатого" отброшенного элемента и отдавая самому "бедному". Однако очень трудно определить абсолютный минимум этой вероятности, поскольку подобная задача, по крайней мере,так же трудна, как "проблема упаковки корзин"; см раздел 7.9.) 6. Нужна поменять местами Р, и (/ ч- Р,)//з для О < / < У. зз 9. Рассмотрите знак второй производной /" (х) = з/2/я(хз — 1)е 10. Пусть 5, = (/ — Ц/3 для 1 < / < 16 и р,ты = Р(5,+з) — Г(5,) — р, лля 1 < з < 13.
Пусть также рзз = 1 — Р(3) и рзз = О. (Формула (13) определяет рц ..., рм.) Алгоритм из упр. 7 можно использовать здесь с (с = 32 для вычисления Р, и 1В после чего получим 1 < 1; < 15 для 1 < д < 32. Присвоим Ре з- Рзз (которое равна 0) и 1'е е- 1'зз. Затем пРисвоим Яз з- 1/(5 — 5Р, ) и 1з з- -'1з — Яз дли 0 <,1 < 32 и (3з з- 1/(ЬРУ) дла 1 < д < 15. Пусть Ь = -' и /зезз(х) = ь/2/я(е * ~~ — е " дю)/р,~.зз для Вз < х < Вз + Ь. Также пусть ау = /з ьзз(дз) для 1 <,1 < 5, Ь, = /з+зз(дз) для б < д < 15, Ь, = -Ь/,'+зз(л, + Ь) для 1 < 1 < 5 и а, = /,+зз(хз) + (хз. — Вз)Ь,/Ь для б < 1 < 15, где хз — корень уравнения /,'+,з(х,) = -Ь,/Ь. Наконец присвоим Вгезз з- оз/Ьз для 1 < / < 15, Е„.ьзз е- 25/д для 1 < / < 5 и В зз е- 1/(е(з -'»" — ц для б < / < 15. Табл.
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); (ам, аш) = (7.о, 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); (Ьз,, Ьзз) = (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).
— з 2 э/з 11. Пусть 9(Г) = ее~~Се ' 7~ дляг > 3. Так как С(х) = ) д(с) 41 = 1-е ы зд~, случайную величину Х с плотностью д можно вычислить, если положить Х з — С (1 — 1') (-О зз — ззгз 9 — ~яГ. Сь . ' З/3) ' 1 ге б 6 обоснованный метод отбраковки, если принять Х с вероятностью /(Х)/сд(Х) = 3/Л. 12.
Справедливо равенство /'(х) = х/(х) — 1 < О для х > О, так как /(х) = х е*гз/ е '7~М/Гондлах>0. Пустьх=а, з идз=х +21п2,тогда з/2/я/ е ' 7~ос = -'з/2/хе * гз/(д) < з з/2/яе ' 7~/(х) = 2 з. Следовательно, у > а,. 13. Возьмем Ь; = д,; рассмотрим сейчас задачу с р, = 0 для каждого д'. В матричных обозначениях, если 1' = АЛ, где А = (ао), необходимо, чтобы выполнялось ААг = С = (с„). (В других обозначениях, если 1; = 2 аззХз, среднее значение 1,1; равно 2 а,з.азз.) Если это матричное уравнение может быть решено для .4, то оно может быть решено и тогда, когда А — треугольная матрица, так как А = В(7 для некоторой ортогональной матрацы У и некоторой треугольной матрицы В, а ВВ = С.
Требуемое решение в виде треугольной т матрицы может быть получено в результате решения уравнений а,з — — сп, аззаз, — — сзз, з оз, + азз — — сзз, ипазз — — сзз, ишазз + озгазз = сзз, ... последовательно для азм ам, 3 азз, азз, азз и т.
д. [Замечание. Ковариационная матрица должна быть неотрипательна з определена, так как среднее значение величины (2 уз 1'„) равно сумме 2, с, у,ду, которая должна быть неотрицателъна. И решение всегда существует, когда С иеотрицательно определена, так как С = (7 'б(ай(Лм..., 1„) У, где собстиенные числа А, неотрицательны, и (7 ~61а8(з/Лз,..., з/А )(/ и будет решением.) 14.
Р(х/с), если с > 0; ступенчатая функция (х > 0), если с = 0 или 1 — Р(х/с), если с < О. 15. Функция распределения — ) Рз(х — З) ОРз(1). Плотность — ) /з(х — Г)/з(1) об Это называется сеергакоб заданных распределений. 16. Ясно, что, как и требуется /(з) < сд(Г) для всех б Так как /с д(г) 41 = 1, то д(1) = Сз' ' для 0 < 1 < 1, Се ' для С > 1, где С = ае/(а+с).
Случайную величину с плотностью д легко получить, как смесь распределений Сз(х) = х для 0 < х < 1 и Сз(х) = 1 — е' для х > 1. С1. (Инициализация.) Присвоить р е- е/(а + е). (Это вероятность того, что используется распределение Сз.) С2.(Генерирование случайной величины с распределением С.) Генерировать независимые равномерно распределенные случайные величины (7 и 1', где Ь' ф О. Если (Г < р, присвоить Х э — 1ггы и д +- е х; иначе — присвоить Х е- 1 — 1и (г и д с- Х' ' (Сейчас Х имеет плотность д, а д = /(Х)/сд(Х).) СЗ.
[Отбросить'[ Генерировать новую равномерно распределенную случайную величину су. Если Н > д, возвратиться к шагу С2. 3 Среднее число итераций равно с = (а -Ь е)/(еГ(а -Ь 1)) < 1.4. Существует несколько способов улучшения этой процедуры. Можно заменить И случайной величиной г', имею1цей показательное распределение со средним 1, которая генерируется, допустим, с помощью алгоритма Я, а затем присвоить Х е- е г~м или Х е- 1+ У в обоих случаях. Более того, если присвоить д +- ре в первом случае ,-х и д е- р + (1 — р)Х" ' во втором, то можно использовать первоначальную случайную величину сГ вместо того, чтобы снова генерировать ее на шаге СЗ Наконец, если У < р/е, можно принять 1"Ы немедленно, не расходуя на вычисление д около 30% времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
