Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 42
Текст из файла (страница 42)
С другой стороны, когда о > 2, можно поступить следующим образом, Пусть 1» — нормально распределенная случайнал величина (среднее — О, дисперсия — 1) и 1'г — независимая от нее случайная величина, имеющая показательное распределение со средним 2/(»2 — 2), Положим Я е- 1»г/(о — 2) и отбросим (1'»,1'г), если е»' л > 1- Е Иначе положим .2 2»»ДГ-2/»»2 -2». Последний метод предложен Джорджем Марсвлья, Масй. Сошр.
34 (1980), 235 — 236. (См. также работу А. Дж. Киндермана, Дж. Ф. Монахама и Дж. Дж, Рамаджа (А. 1. К1пдеппап, Я. Г. Мопайап, апб 1, 6. Выпаде, Магй. Сотр. 31 (1977), 1009- 1018).) 6) Сл»/чайные точки ка п-меркой с2рере единичного радиуса. Пусть Лм Лг,- Մ— независимые нормально распределенные случайные величины (среднее — О, где х > О. Пусть 1» и 1'г — — независимые случайные величины, имеющие Хг-рас« пределение со степенями свободы о» и ог соответственно. Положим Х е- 1'» ог/Уго» или Х 6- огГ/е»(1 — 1'), где 1'6, Ь = 1,2, — случайные величины, имеющие бета- распределение с параметрами о»/2 и 2 г/2.
дисперсия — 1); требуемая точка выбирается на единичной сфере следующим образом: (Х|/г, Хз/г„..., Х„/г), где г = (36) Если мы вычисляем Лы используя метод полярньи координат (алгоритм Р), необходимо каждый раз вычислять две независимые случайные величины Хы !с = 1, 2, и в обозначениях алгоритма выполняется равенство Хе+ Хтт = -2 !п 5. Так можно сэкономить немного времени, требуемого для вычисления г. Справедливость (38) вытекает из того факта, что функция распределения точки (Л э,, Л „) имеет плотность, зависящую только от расстояния от начала координат, поэтому при проецировании на единичную сферу она имеет равномерное распределение. Данный метод впервые был предложен Джг В. Брауном (С.
19. Вгони, Модегп МасЬетап'сэ Еог йе Епл!пеег, Р!гэ! велев, есйгеб Ьу Е. Р. Вес!сепЬасЬ (Бекенбах Э. Ф.), Неъ. Ъог!с МсСгап-Н!!1„ 1956, 302), Чтобы получить случайную точку вн1лпри и-мерной сферы, Р. Н. Брант (Н. Р. Вгеп!) предложил взять точку на поверхности этой сферы и умножить ее координаты на П'~". Для размерности 3 можно использовать значительно более простой метод, так как каждая координата этой точки равномерно распределена между — 1 и 1. Егди найти Ъ'м 1т и 5, используя шаги Р1 — РЗ алгоритма Р, искомая точка на поверхности шара будет иметь вид (а~ 'ы а$т, 25 — 1), где а = 2~/1 — 5. (НоЬег! Е.
Кнор, САСМ 13 (1970), 326.) Р. Важные целочисленные распределения. Вероятностные распределения на множестве целых чисел (случайные величины, принимающие только целые значения. — Прим. ред,) могут быть получены, в сущности, с помощью технических приемов, описанных в начале раздета, но некоторые из этих распределений настолько важны, что заслуживают специального упоминания. 1) Геометрическое распределение. Если некоторое событие происходит с вероятностью р, то число У независимых испытаний, проведенных до появления события (или до момента, когда событие происходит впервые), имеет геометрическое распределение, т. е. Х = 1 с вероятностью р, Л' = 2 с вероятностью (1 — р)р, ..., Х = п с вероятностью (1-р)" 'р.
Это, по существу, ситуация, которая уже рассматривалась в разделе 3.3.2. Данное распределение непосредственно связано с числом циклов алгоритмов из настоящего раздела, как и циклы на шагах Р1-РЗ метода полярных координат. Удобный метод генерирования случайной величины с таким распределением состоит в следующем: )т' ! — !!и (// !п(1 — р)~, (39) Чтобы проверить эту формулу, заметим, что ! !и П/ !п(1 — р)~ = и тогда и только тогда. когда и — 1 < 1пП/!п(1 — р) < и, т.
е. (1 — р)" ' > П > (1 — р)" и это происходит с требуемой вероятностью (1 — р)" 'р. Величину 1пП можно также заменить величиной — 1; где 1' имеет показательное распределение со средним 1. Частный случай, когда р = -,', совсем просто реализуется иа бинарном компьютере, так как формула (39) сводится к присвоению К +- !' — !к !Г!, т, е. Х становится на единицу больше числа старших нулевых разрядов в двоичном представлении числа П. 2) Бвномиальное распределение (1, р). Если некоторое событие происходит с вероятностью р и проводится ! независимых испытаний, то общее число У появлений этого события равно и с вероятностью (') р" (1 — р)' " (см.
раздел 1.2.10). Другими словами, если генерируется Ь'ы ..., Ц, достаточно подсчитать, сколько из них не превосходят р. Для малых ! с помощью этого метода легко можно получить точное значение )т'. Для болыпих ! можно генерировать случайную величину Х, имеющую бета- распределение с целыми параметрами а и Ь. где а+ Ь вЂ” 1 = б Прн этом эффективно получаем Ь-й наиболыпий из 1 элементов, не беспокоясь о гснерировании остальных элементов. Сейчас, если Х > р, положим )т" +- Л'ы где Ь/~ имеет бпномиальное распределение (а — 1, р/Х), так как оно показывает, сколько из а — 1 случайных величин в области (О ..
Х) меньше, чем р. Если Х с р, положим Ж < — а+ Л'ы где Х~ имеет биномиальное распределение (Ь вЂ” 1, (р — Х)/(1 — Х)), так как Х~ показывает нам, сколько из Ь вЂ” 1 случайных чисел в области (Х..1) меньше р. Выбирая а = 1+ (1/2), параметр Г можно свести к разумной величине после примерно !я! преобразований такого рода, (Этот подход предложен И. Г. Аренсом, который также предложил альтернативный метод для значений параметра!средней величины; см.
упр. 27.) 3) Пуассоновское распределение со средним р. Пуассоновское распределение соотносится с показательным распределением, кэк биномиальное распределение с геометрическим: если некоторое событие может произойти в любой момент времени, то пуассоновское распределение — это распределение случайной величины, которая равна числу событий, происшедших в единицу времени (при некоторых других ограничениях. — - Прим, ред.). Например, число альфа-частиц, которые нспускаются радиоактивным веществом за одну секунду, имеет распределение Пуассона.
В соответствии с этим принципом можно получить пуассоновскую случайную величину Л', генерируя независимые показательные случайные величины Хы Хз,... со средним 1/р и останавливаясь, как только будет получено Л~ + + Х,„> 1, где )У ~ — т — 1. Вероятность того, что Х~ + + Х„, > 1, равна вероятности, что случайная величина. имеющая гамма-распределение порядка гл, будет > д, а это равно ( !"' 'е 'Ф/(пт — 1)!.
Следовательно, вероятность, что Ж = и, равна 1 г~ — / Ф"е 'й — / !" 'е 'сМ=е "—, л>0. (40) и При генерировании показательной случайной величины методом логарифма, описанным выше, нужно остановиться, когда — (1пЦ + + !и(/ )/д > 1. Упрощая это выражение, получим, что требуемую пуассоновскую величину можно получить, вычислив е " до определенной точности и генерируя одну или более равномерно распределенных случайньгх величин П|, бз, ... до тех пор, пока их произведение не будет удовлетворять неравенству (/~...(У < е л.
Окончательно полагаем, что Х < — т — 1. В среднем нужно генерировать р+ 1 равномерно распределенную величину, поэтому рассматриваемый подход очень полезен, когда д пе слишком велико. Когда р большое, можно получить метод порядка!оба,, используя сведения о том, как соотносятся гамма- и биномиальное распределения высокого порядка.
Сначала генерируем случайную величину Л, имеющую гамма-распределение порядка гп — (ар), где а — подходящая постоянная. (Так как Х эквивалентно — !п(Уз...Н ), по существу, производим т шагов предыдущего метода.) Если Х < д, полагаем Х з — из+ Л'з, где Юз — пуассоновская случайная величина со средним д — Х, а если Х > !з, то полагаем А' з- Хм где Хз имеет бнномнальное распределение (гл — 1, р7Х). Этот метод предложен И. Г. Аренсом и У. Дитером, которые предположили, что — — хорошее значение для а. Справедливость сформулированного утверждения, когда Х > Гч является следствием такого важного принципа; "Пусть Хз, ..., Л,„— независимые показательные. случайные величины с одинаковым средним и пусть 51 = Хз + ° + Хз и 1', = Я,/5„, для 1 < 7' < пз.
Тогда распределение 1'м гз, ..., $' з такое же, как распределение пз — 1 независимых случайных величин, расположенных в порядке возрастания". Чтобы формально доказать этот принцип, подсчитаем иероятность того, что гз < из, ..., 1;„~ < е .з, если Я = и для произвольных значений О < пз « - и з < 1. Пусть Димвз,...,е з) — (пз — 1)-кратный интеграл г~~ -ы ц ''' ~ 2 к/ де ' '~"сй ре м" ВЕ о г(е, ез, и,) )о"' з!из Д'" йьз...)' 'г1и„, 7(1,1,...,1) г',7„, г' 4н, г~ если произвестизамену переменныхгз = впь зз+гз = знь..., !1+ "+г,„-з —— ви„, и Последнее отношение соответствует вероятности того, что равномерно распределенные случайные величины Ум ..., У„, з удовлетворяют неравенствам Уз < вз, ..., У„, з < ем з, если задано, что они также удовлетворяют неравенствам Уз « В некоторой степени более эффективным, но более сложным будет метод для биномиальной и пуассоновской сяучайньзх величин, предложенный в упр.
22. С. Для дальнейшего чтения, Факсимиле письма фон Неймана (топ Непшапп), датированного 21 мая 1947 года, в котором метод отбраковки впервые увидел свет, появилось в 9гапЫан 66аш 1909 — 1964, в специальном выпуске Ьоз А!ашоз Яс!енсе (1оэ А!апюв На!!опа) ЬаЬ., 1987), 13о-136. В книге Аоп-Нп!1огш Напг!от 1'аг!асс Сепегаг!оп Д. Девроя (!. Резтоуе) (Брг!пйег, 1986) обсуждается намного больше алгоритмов генерирования случайных величин с неравномерным распределением, там же подробно рассматривается эффективность каждого метода для типичных компьютеров. В. Херманн и Г.
Дерфлингер (%. Нбппапп апб С. Вегб!пйег, АСМ Тгапз. Май. Яойзгаге 19 (1993), 489-49о) указали, что может быть опасно использовать метод отбраковкп для линейньзх конгруэнтных генераторов с малыми множителями а ж з/т. С теоретической точки зрения интересно рассмотреть оппзимальнмй метод генерирования случайных величин с заданным распределением. Оптимальность здесь означает, что этот метод генерирует требуемую случайную величину, используя минимальное возможное число случайных разрядов. Начала этой теории можно найти в книге Д. Э. Кнута и Э. Ч. Яо (П.
Е. КпцтЬ ацб А. С. Уао, А)богййпш аэк( Сагир)ех)су, ейсес) Ьу 3. Г. ТгацЬ (Кеш Уог)с Асас1енйс Ргеез, 1976), 357-428). Упр. 16 рекомендуется как обзор различных методов, приведенных в этом разделе. УПРАЖНЕНИЯ 1. [10) Пусть а и  — действительные числа„а <,9. Как можно генерировать случайные действительные числа, равномерно распределенные между а и В? 2. [М16) Пусть энС вЂ” случайное целое число, принимающее значения между О и эп — 1 с одинаковыми вероятностями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
