AOP_Tom2 (1021737), страница 41
Текст из файла (страница 41)
13.) Р. Показательное распределение. После равномерного и нормального распределений следующим наиболее важным распределением случайной величины является показашельное распределение. Такие распределения появляются в ситуациях "время поступления". Например, если радиоактивное вещество излучает альфа- частицы так, что одна частица в среднем испускается каждые р секунд, то время между двумя последовательными испусканиями имеет показательное распределение со средним, равным р. Это распределение задается формулой г'(х)=1 — е *7', х>0, (31) 1) Метод логарифма. Очевидно, если у = Г(х) = 1 — е *7", то х = г'1 '1(у) = — р!п(1 — у). Следовательно, — р!п(1 — (7) имеет экспоненциальное распределение согласно (7).
Поскольку 1 — П равномерно распределено, когда П имеет такое же распределение, можно сделать вывод, что (32) Х = -р!пУ имеет экспоненциальное распределение со средним, равным р. (Случай, когда У = О, должен трактоваться особо; его можно заменять любым подходящим значением е, так как вероятность возникновения этого случая крайне мала.) 2) Мешод случайной минимизации.
Как было показано в алгоритме Г, существует простой и быстрый способ альтернативного вычисления логарифма равномерной случайной величины. Следующий особенно эффективный подход разработали Дж. Марсалья, М. Сибая (М. 8!Ьпуа) и И. Г. Арене (Л. Н, АЬгепэ) [см. САСМ 15 (1972), 876-877!. Алгоритм Б (Экспоненциальное распределение со средним, раенмм р). Этот алгоритм вырабатывает экспоненциальные случайные величины на бинарном компьютере, используя равномерно распределенные случайные величины с точностью до (! + 1) двоичных разрядов. Постоянные 1' 2' й' !п2 (1п2)~ (1п2)" (33) могут вычисляться заранее до тех пор, пока онн не превысят следующее значение: Я[Ь] > 1 — 2 '.
81. [Получить !7 и сдвинуть.] Генерировать (с+ 1) двоичных разрядов равномерной случайной двоичной дроби У = (.ЬоЬ|Ьт...Ь~)т, определить местоположение первого нулевого двоичного разряда Ь и избавиться от старших у + 1 двоичных разрядов с помощью присвоения П < — (.Ьу~л...Ьс)э. (Как и в алгоритме Е, среднее число отбрасываемых двоичных разрядов, равно 2.) 82. [Немедленное принятие?) Егли (7 < !п2, присвоить Х < — р01п2+ У) и завершить алгоритм. (Отметим, что ф1] = !п 2.) ЯЗ.
[Минимизация.] Найти нанменыпее Ь > 2, такое, что !7 < !д[Ь]. Генерировать Ь новых равномерно распределенных случайных величин У~, ..., Пь и присвоить У ~ — ш!п((7ы..., Гть). 84. [Получение ответа.] Присвоить Х <- р(7' + 1') !п 2. $ Можно также использовать альтернативный метод генерирования случайных величин с показательным распределением (например, метод отношений равномерных случайных величин, как в алгоритме К). Е.
Другие непрерывные распределения. Кратко рассмотрим, как обращаться с другими распределениями, которые достаточно часто возникают на практике. 1) Гамма-распределение порядка а > 0 определяется как 1 г'* г'(х) = / !' ~е ~а!, х>О. (34) Г(а) и Прн и = 1 оно является показательным распределением со средним, равным 1; прн а = — — это распределение случайной величины -Л, где Х вЂ” нормально 1 1 2 Алгоритм А (Гамма-распределение порядка а > 1).
А1. (Генерирование кандидата.) Присвоить У»- »ап(яП), где П вЂ” — равномерно распределенная случайная величина, и присвоить Х е- тГ2а — 11' + а — 1, (Вместо сап(яП) можно использовать метод полярных координат, вычисляя отношение 1гтЯ, как на шаге Р4 алгоритма Р.) А2. (Принимать?) Если Х < О. возират к шагу А1, Иначе — генерировать равномерно распределенную случайную величину )г и возвратиться к шагу А1, если !Г > (1+ Ря) ехр((а — 1) !п(Х/(а — 1)) — »Г2а — 1 1'). Иначе — принять Х.
Среднее время выполнения шага А1 < 1.902, когда а > 3. Существует также заманчивый подход для больших а, основанный на таком замечательном факте, что гамма-распределение случайных величин приблизительно равно аХз, когда Х вЂ” нормально распределенная величина со средним значением 1 — 1/(9а) и среднеквадратичным отклонением 1/т/9а [см. работы Э. Б. Уилсон (Е. В. 1ГП!зоп) и М. М. Гилферти (М. М.
Н!!1егсу), Ргос. Гтаа Асад. Ясй 17 (1931), 684 — 688, а также Дж. Марсалья (С. Магва81!а, Согпри»егз апд Ма1Ъ. 3 (1977). 321— 325)]*. В некоторой степени усложненный, но значительно более быстрый алгоритм, который генерирует случайные величины, имеющие гамма-распределение, за приблизительно ндвое большее время, чем случайные величины, имеющие нормальное распределение. приведен в статье И.
Г. Аренса и У. Дитера, САС51 25 (1982), 47-54, в которой содержится полезное описание принципов, используемых при построении алгоритма. 2) Бежа-распределение с положительными параметрами а и Ь определяется как Р( ) = ( + ) ~1-'(! — С)'-'д», 0<*<1. Г(а+ Ь) Г* Г(а) Г(Ь) /о (35) * Заменить ае(зо — 1)" ни "— (За — 1)" иа шаге 3 алгоритма иа с. З23. распределенная случайная величина (среднее равно О, дисперсия — 1).
Если Х и у — независимые случайные величины, имеющие гамма-распределение порядка а и Ь соответственно, то Х + 1" имеет гамма-распределение порядка а+ Ь. Так, например, сумма й независимых случайных величин, имеющих показательное распределение со средним, равным 1, имеет гамма-распределение порядка Ь. Если метод логарифма (32) использовался для генерирования таких случайных величин, имеющих показательное распределение, то здесь необходимо вычислить только один логарифм: Х» — — !п(П»...17»), где 1Г», ..., 17» — равномерно распределенные случайные величины, не равные нулю.
Таким методом »южно генерировать все случайные величины с гамма-распределением порядка а, где а — целое. Для завершения картины соответствуиидий метод для 0 < а < 1 приведен в упр. 16. Простой метод логарифма также очень медленный, когда а большое, поскольку он требует (а] равномерно распределенных случайных величин. Более того, существует реальный риск, что произведение Ц... (Г»,! приведет к переполнению (потере плавающей точки).
Для большого а следующий алгоритм, предложенный И. Г. Аренсом, ивляется достаточно зффективным и легко записывается в терминах стандартных программ. (См. Апп. 1пзС. 5»аа Май. 13 (1962), 231-237.] и 1г < — ег ггь У о!!а 1 повторяемых до тех пор, пока не получится Уг + Уг < 1; тогда Х ( — Уг/(Уг + Уг). ]См. работу М. Д. Йонка (М. П. Лобик, Месгйа 8 (1964).
5 — 15).] Еще одним подходом, если а и 6 — целые числа, которые не настолько велики, является присвоение Х Ь-й самой большой по величине из а+ 6 — 1 независимых равномерно распределенных случайных величин (см. упр. 9 в начале гл. 5). [См. также более прямой метод, описанный Р. г1. С. Ченгом (Н. С. Н. С(геп8, САСЬХ 21 (1978), 317-322).] 3) Х~-распределение с и степенями свободы (3.3.1-(22)) можно получить, если положить, что Х < — 2У, где У вЂ” случайная величина, имеющая гамма-распределение порядка и/2. 4) г"-распределение (раепределение отношения дисперсий) со степенями свободы иг и иг определено следующим образом: Р(х) = г г " г г" ' Еюуг '( + и Е) — и/г-иг/г дс Г(иг /2) Г(иг/2) (36) где х > О. ПУсть Уг и Уг — независимые слУчайные величины, имеющие Хг-Рас- пределение ео степенями свободы иг и иг соответственно.
Положим Х +- 1 гиз/У и, или Л' е- игУ/иг (1 — У), где Уио Ь = 1,2, — случайные величины, имеющие бета- распределение с параметрами иг/2 и иг/2. 5) г-распределение с и степенями свободы определено следующим образом: Р(х) = ' ' (1+ г~/~) 1"~П/~ ае Г((и + 1)/2) Г* г/пи иГ(и/2),/ „ (37) Пусть 1; — нормально распределенная случайная величина (среднее — О, дисперсия --1) и Уг — - случайная независимая от Уг величина, имеющая Х~-распределение с и степенями свободы. Положим Л' < — Уг/ь/Уг/и. С другой стороны, когда и > 2, можно поступить следующим образом. Пусть Уг -- нормально распределенная случайная величина (среднее' — — О, дисперсия — 1) и 1'г — независимая от нее случайная величина, имеющая показательное распределение со средним 2/(и — 2).
Положим Я < — 1'г/(и — 2) и отбросим (Уг, Уг), если е уг х > 1 — л. Иначе положим Последний метод предложен Джорджем Марсвлья, Масй. Сошр. 34 (1980), 235 — 236. ]См. также работу А. Дж. Киндермана, Дж. Ф. Монахама н Дж. Дж. Рамаджа (А. 1. К1пдеппап, 1. Р. Мопабап, апд 1. С. Вапгайе, Магб. Сошр. 31 (1977), 1009- 1018) .] 6) Случайные пгочкн на и-мерной сфере единичного радиуса. Пусть Хг, Хю Хо -- независимые нормально распределенные случайные величины (среднее — О, Пусть Хг и Лг - — независимые случайные величины, имеющие гамма-распределение соответственно порядка а и Ь. Присвоить Х е- Лг/(Хг + Лг).
Другим полезным для малых а и Ь методом является использование присвоений дисперсия — 1); требуемая точка выбирается на единичной сфере следующим образом: (Х~/г, Хз/г,..., Х„/г), где г = (38) Если мы вычисляем Ль, используя метод полярных координат (алгоритм Р), необходимо каждый раз вычислять две независимые случайные величины Хы Ь = 1, 2, и в обозначениях алгоритма выполняется равенство Хз+Хзз = — 2 1п 5. Так можно сэкономить немного времени, требуемого для вычисления т. Справедливость (38) вытекает из того факта, что функция распределения точки (Л ы..., Х„) имеет плотность, зависящую только от расстояния от начала координат, поэтому при проецировании на единичную сферу ова имеет равномерное распределение.
Данный метод впервые был предложен Дж. В. Брауном (С. 1У. Вгогеп, Модегп Ма1Ьешабсз /ог !Ле Еп81пеег, Р!гэт зебез, ей~ес1 Ьу Е. Р. Вес1сепЬасЬ (Бекенбах Э. Ф.), Хе~ч Уог(с МсСгаж-Н!!1, 1956, 302). Чтобы получить случайную точку енушри и-мерной сферы, Р. Н. Брент (Н.
Р. Вгепт) предложил взять точку на поверхности этой сферы и умножить ее координаты на Р~". Для размерности 3 можно использовать значительно более простой метод, так как каждая координата этой точки равномерно распределена между — 1 и 1. Егли найти гы $з и Я, используя шаги Р1-РЗ алгоритма Р, искомая точка на поверхности шара будет иметь вид (а1'~, а1'з, 25 — 1), где а = 2~/1 — 5, (НоЬегг Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
