Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 38
Текст из файла (страница 38)
Значительное число "случайных трюков" было придумано для эффективного преобразования равномерно распределенных случайных чисел. Изучив эти методы, почучим возможность правильно использовать случайные числа при любом применении метода Монте. Карло. Вероятно, что кто-нибудь когда-нибудь придумает генератор случайных чисел, который будет вырабатывать одну нз этих случайных величин непосредсглеенно, а не косвенно через равномерное распределение.
Но прямые методы, как доказано, не практичны, за исключением генератора "случайный двоичный разряд", описанного в разделе 3.2.2, (См. также упр. 3.4.1-31, в ием равномерное распределение используется, главным образом, для инициализации, после которой метод является почти полностью прямым,) В следующем разделе предполагается наличие случайной последовательности равномерно распределенных между О и 1 независимых действительных чисел.
Равномерно распределенная случайная величина П генерируется всякий раз, когда в ней возникает необходимость. Эти числа обычно представлены в компьютере словом с десятичной точкой слева. 3.4.1. Численные распределения В этом разделе объединены наиболее известные методы получения случайных чисел для различных важных распределений. Многие из методов первоначально были предложены Джоном фон Неймаиом (до1ш 1 оп Хепшапп) в начале 50-х. Постепенно они усовершенствовались другими математиками, особенно Джорджем Марсалья (Оеогйе Магэакйа), И.
Г. Аренсом (3. Н. АЬгепэ) н У, Дитером (Ц. 01егег). А. Случайный выбор из ограниченного множества. Самые простые н наиболее общие типы распределений, используемых в приложениях, — это распределения случайных целых чисел. Целые числа между О и 7 могут быть извлечены из трех двоичных разрядов Ц иа бинарном компьютере; поэтому эти три двоичных разряда можно извлечь из сглартоео значащей (слева) части компьютерного слова, поскольку самые младшие двоичные разряды, производимые многими генераторами случайных чисел, недостаточно случайны (см. раздел 3.2.1.1). В общем случае случайные целые числа Л, которые лежат между 0 и я — 1, можно получить, умиожие (7 на А и положив Х = 1яЦ.
На И13 можно записать После выполнения этих двух операций требуемое целое число появится в регистре А. Чтобы получить случайное целое число, лежащее между 1 и А, следует добавить единицу к этому результату. (Операция "1ИСА 1" последует за (1).) С помощью данного метода каждое целое число можно получить с приблизительно равной вероятностью. Существует незначительная ошибка, так как длина слова компьютера коиечиа (см. упр, 2), но эта ошибка совершеиио незначительна, если й малб, например /с/ш < 1г'10000. В более общем случае можно получить„если необходимо, различные веса для различных целых чисел.
Предположим, что значение Х = х~ должно быть получено с вероятностью рм Л = яэ — с вероятностью рт, ... и Л = х» — с вероятностью р». Генерируем равиомериое число (7 и положим хм еслиО<Г<р», хэ, еслир~ <о' <р~+рэ,' Л = (2) х», если р» + рэ + + р» ~ < (7 < 1. (Заметим, что р~ + рэ+ '''+р» = 1) Существует "наилучший возможный" способ сравнения (7 с различными значениями р» + рэ + . + р„как подразумевается в (2) (см. раздел 2.3.4.6), В частных случаях можно обойтись более эффективными методами; например, для того, чтобы получить одно из одиннадцати чисел 2, 3, ..., 12 с соответствующими "игре в кости" вероятностями 11», ~~, ..., ф, ..., ф, — ', можно вычислить два независимых случайных целых числа между 1 и 6 и сложить их.
Тем не менее существует действительно более быстрый способ выбора хм..., х» с произвольна заданной вероятностью, осиованиый на остроумном подходе, который был введен в употребление А. Дж. Уолкером (см. А. д. Юа(кег, В)ес»гошев Ее»сегв 10,8 (1974), 127-128; АСМ 2гапз, Масй. 5о»1иаге 3 (1977), 263-256). Предположим, что мы образуем х(7 и рассматриваем целую часть К = 1Щ и дробную часть У = (И7) шоб 1 раздельно, например после выполнения операций (1) получим К в регистре А и У вЂ” в регистр.
Затем всегда можно получить желаемое распределение, выполнив операции если У < Рк, то Х+- хк+м яначе Х»- Ук для некоторых подходящих таблиц (Ре,, Р»») и (Уе,..., У»»). В упр. 7 показано„ как вообще можно вычислить такие таблицы. Метод Уолкера иногда называют методом псевдонимов . На бинарном компъютере обычно полезно предполагать, что к является степенью 2, потому что умножение может быть заменено сдвигом. Это можно делать без потери общности, введя дополнительные х, которые появляются с вероятностью О.
Например, снова рассмотрим игру в кости. Предположим, что равенство Х = у должно произойти со следующими 16 вероятностями. 7' = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Рз — О 0 88 58 38 зв зв з8 зв зв зв зв зв 0 0 0 Это можно осуществить, используя (3), если к = 16 и хз+1 = у при 0 < 7' < 16 и если таблицы для Р и У имеют следующий вид. у' = О 1 2 3 4 5 6 7 8 9 10 11 12 13 14 !5 Р, О 0 1 а 1 т 1 1 1 т т в 11 = о 9 7 4 в 6 э в в 8 4 Т 10 6 7 8 (Когда Р, = 1, Уз ие используются.) Например, значение 7 встречается с вероятностью + ° ((1 — Рз) + Рт+ (1 — Ры) + (1 — Ры)) = ф, как и требуется.
Это необычный способ бросания игральных костей, но результаты получаются такие же, как и в реальной ситуации. Вероятности р~, безусловно, могут быть представлены неотрицательными весами юм юз, ..., юь, если обозначить сумму весов через И', то р = и /И'. В разных применениях отдельные веса весьма изменчивы. Матяас, Виттер и Ни (см. работу МаМы, т'1зсег, апб %, ЗОРА 4 (1993), 361-370) показали, как изменять веса и генерировать Л с постоянным средним временем.
В, Общие методы длн непрерывньзх распределений. В общем случае распределение действительных чисел может быть выражено в терминах "функции распределения" Р(х), которал точно определяет вероятность того, что случайная величина Х не превысит значение х: (4) Г(х) = Рг(Х < х). Эта функция всегда монотонно возрастает от О до 1, т.
е. Р(хз) < Г(хз), если х1 < хз, Р( — оо) = О, Г(+ос) = 1. (5) Примеры функций распределения приведены в разделе 3.3.1 (см. рис. 3), Если Г(х) непрерывна и строго возрастающая (так что Р(хз) < Р(хз), когда хз < хз), то она принимает все значения между 0 и 1 и существует обрашнал Функция Г~ О(у), такая, что для 0 < у < 1 тогда и только тогда, когда х = Р~ 0(р).
(6) у = Г(х) В большинстве случаев, когда Г(х) непрерывна н строго возрастающая, можно вычислить случайную велячину Х с распределением Р(х), полагая Х=Р( О(Ц, (Т) где У вЂ” равномерно распределенная случайная величина. Действительно, вероятность того, что Л < х, равна вероятности, что Ф О(У) < х, а именно — вероятности того, что У < Р(х), т. е. Р(х).
Теперь проблема сводится к решению задачи численного анализа — к нахождению хороших методов вычисления Р( 0(У) с требуемой точностью. Численный анализ в этой книге о получисченных алгоритмах не рассматривается, однако существует ряд важных методов, способных улучшить общий подход (7), и здесь они будут рассмотрены. Заметим, что если Х~ — случайная величина, имеющая функцию распределения Р~(х), и если Хз — независимая от Хг случайная величина с функцией распределения Гз(х), то щах(Х~ „Хз) имеет распределение Р~ (х) Гз (х), (8) ппп(ЛыХз) имеет распределение г1(х) +ге(х) — Р~(х)Ре(х). (См, упр. 4.) Например, равномерно распределенная случайная величина У имеет распределение Р(х) = х для О < х < 1; если Ум (гз, ..., Ц вЂ” независимые равномерно распределенные случайные величины, то щах(Умах,..., Ц) имеет функцию распределении г'(х) = х' при О < х < 1.
Эта формула является основой критерия "максимум-1", описанного в разделе 3.3.2. Обратная функция равна г'! '!(9) = ч'й. В частном случае при ! = 2 получаем, следовательно, что формулы далут одинаковое распределение случайной величины Х, хотя, на первый взгляд, это не очетщно. Нет необходимости извлекать квадратный корень из равномерно распределенной случайной величины. Количество подобных хитростей бесконечно: любой алгоритм, использующий случайные числа на входе, дает на выходе случайные величины с некоторым распределением. Задача состоит в нахождении общих методов составления алгоритма, обеспечивающего заданную функцию распределения на выходе.
Вместо того чтобы рассматривать подобные методы в исключительно абстрактных терминах, изучим, как они могут применяться в важных случаях. С, Нормальное распределение. Возможно, наиболее значительным неравномерным, непрерывным распределением является нормальное распределение с нулевым средним значением и среднеквадратичным отклонением, равным единице: (10) Значительность данного распределения показана в разделе 1.2.10. В нашем случае обратную функцию Ф '! не так легко вычислить; но, как мы увидим, существует несколько технических приемов моделирования этого распределения.
1) Метод полярных координат, предложенный Дж. Э. П. Боксом, М. Э. Мюллером и дж. Марсалья [см. С. Е,.Р. Вох, И. Е. Ып1!ег, апд О. Магза811а, Аппа)з Маей. Бгай 29 (1958), 610-611, и Вое1п8 Бс)епс!бс Вее. 1.аЬ. герогс Ш-82-0203 (1962)[. Алгоритм Р (Метод полярных координат длл нормальных случайных величин). Этот алгоритм вычисляет две независимые нормально распределенные случайные величины: Х~ и Хз. Р1. [Получение равномерно распределенных случайных величин.] Генерируем две независимые случайные величины (1~ и Уз, равномерно распределенные между О и 1. Присвоить У» г- 217» — 1, У» <- 2Г~ — 1. !Здесь Ъ~ и У» равномерно распределены между — е1 н +1. На бояьшинстве компьютеров предпочтительнее представление У» и )» в виде чисел с плавающей точкой,) Р2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
