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