Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 69
Текст из файла (страница 69)
Сошр. 67 (1991), 735-746.] РАЗДЕЛ 3.6.1 1. а+(/4 — а)Г 2. Пусть У ы Х/т, тогда [Щ = г ешэ т < 1Х/зп < г + 1 чшэ гпг/Ь < Х < т(г+ 1)/Ь Фиэ [гпг/и[ < Х < [ги(г+ 1)/я1. Точная вероятность задается формулой (1/тП [из(г+ 1)/51 — [пзг/51 ) = 1/(з+ «, где [е[ < 1/ш. 3. Если заданы случайные числа, длина которых равна машинному слову, то результат будет отличаться от правильного распределения самое большее на 1/ш, как показано в упр.
2, ио все эксцессы приводят к наименьшим отличиям. Так, если Ь ш ш/3, результат будет меньше Ь/2 приблизительно в г рэз. Намкого лучше получить совершенно равномерное распределение, отбросив У, если У > Ь[гп/Ц [см. П. Е, Кпагй, ТЬе Язап/оЫ СгарЬВаэе (Чем 'г'огй: АСМ Ргеш, 1994), 221). С другой стороны, если использовалась линейная конгруэитиая последовательность, то Ь и модуль гп должны быль взаимно простыми числами, иначе чисеа имеют очень короткий период, как следует из раздела 3.2.1.1.
Например, если Ь = 2 и гп четное, наилучшими числами будут попеременно повторяемые числа 0 и 1. Метод слабее (1) почти в каждом случае, так что мы его не рекомендуем. К сожалению, однако, операция "Ьшш!с" в (1) отсутствует во многих языках высокого уровня (см. упр, 3.2.1.1-3). Деление тв/Ь, возможно, наилучшее, когда "Ьшш!з" отсутствует. 4. шах(Хм Лг) < я тогда и только тогда, когда Хз < х и Хз < х; шш(Хц Лг) > х тогда и только тогда, когда Лг > х и Хз > л.
Вероятногль того, что два независимых событии происходят одновременно, равна произведешпо вероятностей этих событий. 5, Получим независимые равномерно распределенные случайные величины Уг и Уг, Положим Л <- Пг. Если Уз > р, положим Х +- шах(Х, Уз), где Уз — третья равномерно распределенная величина. Если Уг > р+ 9, положить также Х <- пзах(Х, Уз), где (/з— четвертая равномерно распределенная случайная величина.
Этот метод можно очевидным образом обобщить для любой случайной величины с полиномиальной функцией распре- Окружность Он+ Рг = 1 Рис. А-4, "Область принятия" для алгоритма нз упр. 6. деления и даже с функцией распределения, представимой в внле степенного Ряла (как показано, например, в алгоритме Б, вместо максимизации использующем минимизацию). Можем поступить и следующим образом (предложение М. Д. Мак-Парень (М. П. МасЬагед)): если Уг < Р, присвоить Х е- У1/р; иначе, если (ч < р + д, присвоить Х +- шах((У1 — р)/д, Уз): иначе присвоить Х е- шах((Г1 - р- д)/г, Ум Пз). Этот метод по сравнению с другими требует меньше времени на получение равномерно распределенных случайных чисел, несмотря на то что он требует больше арифметических операций и несколько менее устойчив численно.
6. Г(х) = А~/(А1 + Аз), где Л1 и Аз — площади, показанные на рис. А-4, так что /е* 1/':р' Оу Г(х) =, = — агсяпх+ -х1/1 — хз. /"1 „ел к Вероятность окончания процедуры иа шаге 2 равна р = к/4, Процедура продолжается до завершения иа шаге 2, поэтому число выполнений шага 2 имеет геометрическое распределение.
Характеристиками этого числа являются (пбп 1, ач» 4/1г, п1ах оо, бек (4/к) ь/Т вЂ” и/4) согласно упр. 17. 7. Если й = 1, тогда п1 = н, н задача тривиальна. В противном случае всегда можно найти 1 де/, такое, что и; < и < и.. Заполните В, и, кубиками цвета С) и и - и, цвета С',. Затем замените пу на и — и; и исключите цвет Сь Теперь перед нами стоит та же задача, но 5 меньше на 1.
Следовательно, по индукции з дача имеет решение. Следующий алгоритм можно использовать, чтобы подсчитать Р и У для таблиц из (3). Образуем набор пар (рм1)... (Ры5) и рассортируем их по первой компоненте, получив набор (дно~) .. (дыаэ), где д1 < < ды Присвоим и+-5 и будем повторять следующие операции до тех пор, пока не получим и = О: присвоим Р(о1 — 1) е- йд1 и Цо1 — 1] +- х,„.
Удалим (Ф, а1) н (д, а ), поместим-новый элемент (д — (1/Я вЂ” д1 ), а„) на его собственное место в наборе н уменьшим и на 1. (Если рз < 1/5, то алгоритм никогда не поместит х в таблицу для 1'. Этот факт безоговорочно используется в алгоритме М. Алгоритм пытается максимизировать вероятность того, что 1' < Рк в (3), отбирая у самого "богатого" отброшенного элемента и отдавая самому "бедному".
Однако очень трудно определить абсолютный минимум этой вероятности, поскольку подобная задача, по крайней мере, так же трудна, как "проблема упаковки корзин"; см, раздел 7.9.) 8. нужно поменять местами Рз и (у + Р )/и для О < у < 5. 9. Рассмотрите зпак второй производной /" (х) = 1/2/к (хз — 1)е * ~'. 10. Пусть $1 = (1' — 1)/5 для 1 < 1 < 16 и р.+м = Г(5 +1) — Р($1 ) — рг для ! < / < 15. Пусть также рм = 1 — Р(3) н рш = О.
(Формула (15) определяет ры, рм ) Алгоритм нз упр. 7 можно использовать здесь с Ь ж 32 для вычисления РЛ и У,-, после чего получим 1 < 1; < ГЬ для 1 < У < 32. Присвоим Ре +- Рш (которое равно 0) и уо +- Кзз. Затеи присвоим 21 +-1/(5 — ЬР ) н 1; +- 1~1„— Е, для 0 < 1 < 32 н ф, »-1/(ЬРЛ) для 1 < / < 15. Пусть Ь = -' н /»»»»(х) = ь//2/к(е * »~ — е з ~ш)/рз ы» для 51 < х < дз + Ь. Также пусть а = / »»»(дз) для 1 < Л < 5, Ьз = /1»ы(дз) для 6 < у < 1$„'Ьз = -Ь/»»»»Щ + Ь) для 1 < у < 5 н о;: / +~»(хЛ) + (х„— оз)ЬЛ/Ь для 6 < / < 15, где х — корень уравнения /»»»»(х») = -Ьз/Ь.
Наконец присвоим 111 ы»»- о,/Ь, длв 1 < / < 1$, Ез+ы»- 25/7' для 1 < л < 5 н В +и +- 1/(е»Ш" Пгю — 1) для 6 <» < 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,.00$,.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.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); (Ь»,..., Ьы) = (14,9, 11.7, 10.9, 10.4, 10.1, 10,1, 102, 10 3, 104, 10 5, 106, 10.7, 10.7, 10. 8, 10 9), 11. Пустьд(1) =ею~»е 'г~дляг > 3. Таккакб(х) = )з д(1)»(1 = 1 — е ы еп», случайную величину Х с плотностью д можно вычнслить, если положить Х»- С' 0(1 — Ъ') ы л» ькт. су ' р(е '1 З. т»р ар * у обоснованный метод отбраковки, если принять Х с вероятностью /(Х)/сд(Л) = 3/Х 12.
Справедливо равенство /'(х) = х/(х) — 1 < 0 для х > О, так как /(х) = х '— е*ге / е ' ~~дг/г~ для х > О. Пусть х = аз» ну = х + 21п2, тогда /2/х / е ' ~~в1 = -',/2/хе "7 /(д) < -'ь/2/яе *ге/(х) = 2 '. Следовательно, д > а,. 13. Возьмем Ьз = р;; рассмотрим сейчас задачу с Лз = 0 для каждого /. В матричных обо- значениях, если У = АХ, где А = (а„), необходимо, чтобы выполнялось АА = С = (сч). (В других обозначениях, если 1) = 2 а,»Х», срелнее значение 171» равно 2 а,»а».) Если зто матричное уравнение может быть решено для А, то оно может быть решено н тогда, когда А — треугольная матрнца, тек квк А = ВП для некоторой ортогональной матрицы У я некоторой треугольной матрицы В, а ВВ = С.
Требуемое решение в виде треугольной матрицы может бь»ть получено в результате решения уравнений ам = см, омом = сш, » аз, + азз - -сы, апаз» с»з, ошам + о»»озз = с»з, последовательно для ам, аы, 2 2 аш, азы аз» и т. д. [Замечание. Ковариационная матрица должна быть неотрицательно определена, так как среднее значенне величины (2 д,у;) равно сумме 2,сод;д„которая должна быть неотрнцательна. И решение всегда существует, когда С неотрнцательно опрелелена, так как С = П ' йаб(йм..., 2„)(/, где собственные числа Аз неотрицательны, и У '»баб(»/лм..., »/Х„)(7 н будет решением,[ 14.
Р(х/с), если с > О; ступенчатая функция [х >О), если с = 0 нлн 1 — Р(х/с), если с < О. 1$. Функция распределения — ) Р»(х — 1)»Ж(1). Плотность — ) /~(х — 1)/»(1) ой Это называется сверн»кой заданных распределений. 16. Ясно, что, как н требуетск /(1) < сд(г) для всех й Так как ) ы д(1) ос = 1, то д(1) = С1' ' для 0 < 1 < 1, Се ' для 1 > 1, где С = ае/(а+е), Случайную величину с плотностью д легко получить, как смесь распределений С»(х) = х' для 0 < х < 1 и Сз(х) = 1 — е' ' для х > 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
