AOP_Tom2 (1021737), страница 42
Текст из файла (страница 42)
Кпор, САСМ 13 (1970), 326.) Р. Важные целочисленные распределения. Вероятностные распределения на множестве целых чисел (случайные величины, принимающие только целые значения. — Прим, ред.) могут быть получены. в сущности, с помощью технических приемов, описанных в начале раздела, но некоторые из этих распределений настолько важны, что заслуживают специального упоминания. 1) Геожетприческое распределение. Если некоторое событие происходит с вероятностью р, то число Х независимых испытаний, проведенных до появления события (или до момента, когда событие происходит впервые), имеет геометрическое распределение, т.
е, !У = 1 с вероятностью р, Л7 = 2 с вероятностью (1 — р)р, ..., !У = и с вероятностью (1-р)" 'р. Это, по существу, ситуация, которая уже рассматривалась в разделе 3.3.2. Данное распределение непосредственно связано с числом циклов алгоритмов из настоящего раздела, как и циклы на шагах Р1 — РЗ метода полярных координат. Удобный метод генерирования случайной величины с таким распределением состоит в следующем: !У с — )!п(7/ !п(1 — р)~. (39) Чтобы проверить эту формулу, заметим, что )!и Н/1п(1 — р)~ = и тогда и только тогда, когда и — 1 ( 1пС/1п(1 — р) ( и, т.
е. (1 — р)" ' > П > (1 — р)" и зто происходит с требуемой вероятностью (1 — р)" 'р. Величину 1п(7 можно также заменить величиной — 1; где !' имеет показательное распределение со средним 1. Частный случай, когда р = —,,', совсем просто реализуется на бинарном компьютере., так как формула (39) сводится к присвоению !У <- !' — !8 П), т. е.
Ж становится на единицу болыпе числа старших нулевых разрядов в двоичном представлении числа П. 2) Биномиальное распределение (г,р). Если некоторое событие происходит с вероятностью р и проводится ! независимых испытаний, то общее число Л появлений этого события равно и с вероятностью (') р" (1 — р)' " (см. раздел 1.2.10). Друтими словами, если генерируется Пы ..., Ь и достаточно подсчитать, сколько из них не превосходят р.
Для малых г с помощью этого метода легко можно получить точное значение Х. Для больших 1 можно генерировать случайную величину Х, имеющую бета- распределение с целыми параметрами а и Ь. где а+ Ь вЂ” 1 = й При этом эффективно получаем Ь-й наибольший из ! элементов, не беспокоясь о генерированип остальных элементов. Сейчас, если Х > р, положим М з — (г',, где Ж, имеет биномиальное распределение (а — 1, р/Л), так как оно показывает, сколько из а — 1 случайных величии в области [О .. Л) меньше, чем р. Если Х ( р, положим Х < — а+ Хм где Х~ имеет биномиальное распределение (Ь вЂ” 1, (р — Х)/(1 — Х)), так как !т1 показывает нам, сколько из Ь вЂ” 1 случайных чисел в области [Х., 1) меньше р, Выбирая а = 1+ [!/2), параметр ! можно свести к разумной величине после примерно !01 преобразований такого рода.
(Этот подход предложен И. Г. Аренсом, который также предложил альтернативный метод для значений параметра ! средней величины; см. упр. 27.) 3) Пуассоноеское распределение со средним р. Пуассоновское распределение соотносится с показательным распределением, как биномиальное распределение с геометрическим: если некоторое событие может произойти в любой момент времени, то пуассоновское распределение -- это распределение случайной величины, .которая равна числу событий, происшедших в единицу времени (при некоторых других ограничениях. — Прим. ред.).
Например, число альфа-частиц, которые испускаются радиоактивным веществом за одну секунду, имеет распределение Пуассона. В соответствии с этим принципом можно получить пуассоновскую случайную величину й', генерируя независимые показательные случайные величины Лы Лэ, .., со средним 1/р и останавливаясгч как только будет получено Л1+ м Х,„> 1, где Х е- т — 1.
Вероятность того, что Л', + + Л"„, > 1, равна вероятности, что случайная величина, имеющая гамма-распределение порядка щ, будет > р, а это равно [„С"1 1е 'сй/(т — 1)!. Следовательно, вероятность, что Л! = и, равна — / Ьае й — / !" 1е й=е "—,. п>0. (40) При генерировании показательной гшучайной величины методом логарифма, описанным выше, нужно остановиться, когда — (!пГ1 + + !пГ,„,)/р > 1, Упрогцая это выражение, получим, что требуемую пуассоновскую величину можно получить, вычислив е " до определенной точности и генерируя одну или более равномерно распределенных случайных величин Уы Гэ, ...
до тех пор, пока их произведение не будет удовлетворять неравенству П1... П,„( е гч Окончательна полагаем, что Х +- гп — 1. В среднем нужно генерировать р+ 1 равномерно распределенную неличину, поэтому рассматриваемый подход очень полезен, когда р пе слишком велико. Когда р большое, можно получить метод порядка !опр, используя сведения о том, как соотносятся гамма- и биномиальное распределения высокого порядка. Сначала генерируем случайную величину Л, имеющую гамма-распределение по- рядка гп = (пд), где а — подходящая постоянная.
(Так как Х эквивалентно — )п(11~... С„,), по существу, производим т шагов предыдущего метода.) Если Х < д, полагаем Ж < — т + Л'„где М~ — пуассоновская случайная величина со средним и — Л, а если Л' > и, то полагаем й' < — Хы где Ж~ имеет биномиальное распределение (гп — 1, и/Х). Этот метод предложен И. Г. Аренсом и У. Дитером, которые предположили, что — — хорошее значение для а.
7 Справедливость сформулированного утверждения, когда Х > ц, является след- ствием такого важного принципа: "Пусть Лы ..., Л' — независимые показатель- ные случайные величины с одинаковым средним и пусть 5о = Х~ + . + Х, и 1г, = 5,/5,„для 1 ( 1 ( т. Тогда распределение 1ч, Ъэ, ..., 1ь,, такое же, как распределение т — 1 независимых случайных величин, расположенных в порядке возрастания". Чтобы формально доказать этот принцип, подсчитаем вероятность того, что \) < оы ..., 1' о ( е и если 5„, = а для произвольных значений О < е~ < < е~ ~ < 1.
Пусть /(щ,еэ,...,п„, ~) — (ш — 1)-кратный интеграл l о~к гам и йе '~иМ, / пе "1" щ, о о г~ 1ю-и- -с -о х / й — ~/и~41 . е ~~ и '' — ~Ми ° ь — ~ . 1эе о тогда если произвести замену переменных 1~ — — эип 1~+1э — — эит, ..,, 1~+ +г,ь ~ = эпгн Последнее отношение соответствует вероятности того, что равномерно распределенные случайные величины (7ы ..., 11 ~ удовлетворяют неравенствам сч < ем ..., Кн 1 ( е~п и если задано что они также удовлеч воряют иерааенсз Вам П! ( ° ( (7 и В некоторой степени более эффективным, но более сложным будет метод для биномиальной и пуассоновской случайных величин, предложенный в упр. 22. сэ.
Для дальнейшего чтения. Факсимиле письма фон Неймана (уоп )чепшапп), датированного 21 мая 1947 года, в котором метод отбраковки впервые увидел свет, появилось в 51ап1э1аюу Иат 1909 — 1984, в специальном выпуске 1.оэ А1атов 5с1епсе (1,оэ А!атоэ Хайюпа1 ЕаЬ., 1987)., 138-136. В книге Хоп-Нп(уогт Вапг!от 1'апа1е СепегаВоп Д. Девроя (Е. Ренгоуе) (8рбпрп, 1986) обсуждается намного больше алгоритмов генерирования случайных величин с неравномерным распределением; там же подробно рассматривается эффективность каждого метода для типичных компьютеров. В.
Хермаин и Г. Дерфлингер (%. Ноппапп апб С. Рег61пйег, АСМ Тгапэ. Ма1й. 5о1сиаге 19 (1993), 489-495) указали, что может быть опасно использовать метод отбраковки для линейных конгруэнтных генераторов с малыми множителями а - т/т. С теоретической точки зрения интересно рассмотреть оптимальный метод генерирования случайных величин с заданным распределением. Оптимальность здесь означает, что этот метод генерирует требуемую случайную величину, используя минимальное возможное число случайных разрядов. Начала этой теории можно найти в книге Д.
Э. Кнута и Э. Ч. Яо (П. Е. Кпц1Ь апс( А. С. Ъ'ао, А18ог11)ипз апэ( Сотр1ех!1у, ес((сеэ( Ьу Л. Е. ТгацЬ (Не~ч Уог(с; Асабешгс Ргеез, 1976)., 357-428). Упр. 16 рекомендуется как обзор различных методов, приведенных в .этом разделе.
УПРАЖНЕНИЯ 1. [10) Пусть о и 0 — действительные числа, а < 0. Как можно генерировать случайные действительные числа, равномерно распределенные между о и 0? 2. [М10) Пусть тП вЂ” случайное целое число, принимающее значения между О и гп — 1 с одинаковыми вероятностями. Чему шалва равна вероятность того, что (?сЦ = г, если О < г < кэ Сравните с требуелэой вероитностью 1//с.
3. [Ц) Как можно рассмотреть Г? в качестве целого числа и разделипэь его на?э, чтобы получить случайное целое число между О и?э — 1, вместо того чтобы выполнять умножение, как предложено в разделе. Тогда (1) было бы заменено на Ей?А О; ?.ОХ О; 917 К с результатом в регистре Х. Хороший ли зто метод? 4. [М00] Докажите два соотношения в (8). б. [Х1) Предложите аффективный ыетод генерирования случайной величины с функцией распределения Р(х) = рх+Ох + гх (О < х < 1. - — Прим. ред.), где р > О, 0 > О, г > О ир+Оег=1. 6. [НМй) Величина Х патучена следующим образом. Шаг 1.
Генерировать две независимые равномерно распределенные случайные величины с? и У Шаг 2. Если Пз + У > 1, возврат к шагу 1; иначе — присвоить Х э- 11 Какова функция распределения Х? Сколько времени выполняется шаг 1? (Найдите среднее и среднеквадратичное отклонения). 7. [00) (А. Дж. Уолкер (А. 3. %а!кег).) Предположим, что имеется набор кубиков ?с разтичных цветов, скажем пэ кубиков цвета С, при 1 < 0 <?с, и?э коробок (Вц..., Вь), в каждую из которых можно поместить и кубиков. Кроме того, п~ + + пь = кп, твк что кубики будут полностью заполнять коробки Докажите (конструктивно), что всегда можно разместить кубики в коробках так, чтобы в каждой из них содержались кубики самое большее двух различных цветов.
Действительно, можно устроить так, чтобы всякий рвз в коробке В, содержалось два цвета, один из которых — цвет С,. Покажите, как использовать зто утверждение, чтобы подсчитать Р и К, требуемые в (3), при задыэном вероятностном распределении (рц . Рь). 8. [М15[ Покажите, что операцию (3) можно заменить операцией если ?? < Рк, то Х э- хкэц иначе Х э — 1'к. (Таким образом, вместо У используется истинное значение??.) Будет ли зто более удобным нли подходящим для изменения Ре, Рц..., Р1 9. [НМ10) Почему кривая /(х) парис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
