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