AOP_Tom2 (1021737), страница 40
Текст из файла (страница 40)
Марсалья, Дж. Марсалья, М. Д. Мак-Ларен и Т. А. Брей (см. работы С. Магэаййа, Аппа)в МаСЛ. БСаС. 32 (1961), 894-.899: С. Магэа811а, М. Р, МасБагеп, апд Т. А. Вгау, САСМ 7 (1964), 4-10). В дальнейшем алгоритм М усовершенствовали Дж. Марсалья, К. Ананханараянан и Н. Дж. Поль (см.
работу С. Магва811а, К. АпапСЬапагауапап, апб г1. Л. Рап1, 1пб Ргос. БеНеги 5 (1976), 27 — 30). 3) Метод "чет-нечет принадлежит Дж. Э. Форсайту (С. Е. ЕогэуСЬе). Поразительно простая техника генерирования случайных величин с обычной экспоненциальной плотностью вида 1(х) = Се ~1*1 (а < х < Ь), (20) где 0<5(х)<1 дляа«я<Ь, (21) была открыта Джоном фон Нейманом и Дж.
Е. Форсайтом приблизительно в 1950 году. Идея основана на методе отбраковки, описанном ранее. Предполагается, что д(х) — зто равномерное распределение на интервале (а ..Ь). Присноим Х е- а + (Ь вЂ” а)1?, где (? — — равномерно распределенная случайная величина, и примем Х с вероятностью е "1"1. Последняя операция может быть осуществлена путем сравнения е "сх1 с У либо Ь(Х) с †)п 'г', когда К вЂ” другая равномерно Таблица 1 ПРИМЕРЫ ТАБЛИЦ, ИСПОЛЬЗУЕМЪ!Х С АЛГОРИТМОМ 54ь Рз ! РЬ!б !'+зб 2 Я азб 5' +1 Пэ ыб Е +1б еПрактнчески эти данные могут быть приведены с намного большей точностью; в таблице при- ведено только достаточное количество цифр, чтобы интересующиеся читатели могли более точна проверить собственные алгоритмы вычисления значений.
распределенная случайная величина, но работу можно проделать без применения каких-либо трансцендентных функций следующим интересным способолг. Присвоим Ъго 4- И(Х) и будем генерировать обычные равномерно распределенные случайные величины 171, 152, ..., пока не найдутся к > 1 с 1гк 1 < 1'к. Для фиксированных Х и И вероятность того, что И,(Х) > 1'1 » 1'ы равна 1/И), умноженному на вероятность того, что шах(171,...,1га) < И(Х), т. е, И(Х)е/й!. Следовательно, вероятность того, что К = И, раина И(Х)" 1/(И вЂ” 1)! — И(Х)ь/И1, а вероятность того, что К вЂ” нечетное число, равна а нечетное, а Е 1 (22) Следовательно, мы отбраковываем Х и начинаем снова, если К . — четное число. Принимаем Х как случайную величину с плотностью распределения (20), если К— нечетное число. Обычно мы не генерируем много значений 1, чтобы определить К, поскольку среднее значение К (при заданном Х) равно 2',„ЕОРг(К > И) ~ „~„И(Х)а/И) = ел(х1 < е.
Несколькими годами позже Форсайт показал, что этот подход приводит к получению эффективного метода вычисления нормальных случайных величин без использования вспомогательных программ для вычисления квадратных корней или логгрифмов, как в алгоритмах Р и М. Его процедуру с улучшенным выбором интервалов !0..5), осуществленную И. Г. Аренсом (1. Н. АЬгеп5) и У.
Дитером (и. Рлгегег), можно представить в виде алга)зитыа. Алгоритм Р (Метод "чет-нече!на для нормальных случайных величин). Этот алгоритм генерирует нормальные случайные величины на бинарном компьютере; предполагается, что имеется приблизительно 1+ 1 двоичных разрядов точности. Он нуждается в таблице значений д, = а. — а 1 Дпя 1 </ <1+ 1, где ад опРеделяется 0 .000 .067 1 .849 .161 2 .970 .236 3 .855 .285 4 .994 .308 5 .995 .304 б .933 .280 7 .923 .241 8 .727 .197 9 1,000 .152 10 .691 .112 11 .454 .079 12 .287 .052 13 .174 .033 14 .101 .020 15 .057 .086 0.00 .236 — 0 92 .206 — 5.85 .234 — 0.58 .201 -33.13 201 -39.55 .214 — 2.57 .217 — 1.61 .275 0.67 .200 О ОО .289 0.35 .440 — 0 17 698 0.92 1.150 0.36 1 974 — 0.02 3.526 0.19 0.59 0.20 0.96 1.32 — 0.06 6.66 0.12 1.38 1.31 34.93 0.31 41.35 1.12 2.97 0.54 2.51 0 75 0.73 0.56 0.00 0.17 0.65 0.38 0.37 — 0.01 0.28 0.39 0.24 0.20 0.22 0.78 0.21 0.21 0.0 0.24 0.2 .505 25.00 0.26 0 4 .773 12.50 0 28 0.6 .876 8.33 0.29 0.8 .939 6.25 0.29 1.0 .986 5.00 0.28 1,2 .995 4.06 О 26 14 .987 3 37 0.25 1.6 .979 2.86 0.24 1.8 .972 2 47 0.23 2.0 .966 2.16 0 22 2.2 .960 1.92 0.21 2.4 .954 1.71 0.21 2.6 .948 1.54 0.20 2.8 .942 1.40 0.22 3.0 .936 1.27 (О, 2/е) з/2/е) я=1/3 Рис.
13. Область "принятия" в методе отношения равномерных случайных величин для нормально распределенных случайных величин. Данны линий с отношением координат х распределены нормально. х= -1/3 (О, — з/2/е) — ч/2/е) Алгоритм К (Метод втношен1ьй для нормальных случайных величин). Этот алгоритм генерирует нормальные случайные величины Х. К1. (Получить (/,)/) Генерировать две независимые равномерно распределенные случайные величины У и 11, где (/ ,-Е О, и присвоить Х з — ь/8/е (1т — ~) /1/ (Сейчас Л' равно отношению координат (1/, з/8/е (Ъ' — -')) случайной точки в прямоугольнике, содержащем заштрихованную область на рис. 13.
Принимаем Х, если соответствующая точка в самом деле находится в заштрихованной области, иначе — начинаем сначала.) К2. (Необязательная проверка верхней грани.! Если Хт < 5 — 4е1/4(/, на выходе — Л н завершение алгоритма. (Этот шаг можно опустить, если пожелаете; он так или иначе проверяет, находятся лн избранные точки во внешней области рис. 13, делая излишним вычисление логарифма.) КЗ.
(Необязательная проверка нижней грани.) Если Х2 > 4е 'зз/У+ 1.4, возвратиться к шагу К1. (Этот шаг также может быть опущен; он так или ияаче проверяет, находятся лн выбранные точки за внешней областью рнс. 13, делая ненужным вычисление логарифма).
К.4. (Окончательная проверка.] Если Хз < — 4 1п (/, выход Х и завершение алгортима; иначе — возврат к шагу В.1. $ В упр. 20 и 21 представлен временной анализ; анализируются четыре различных алгоритма, так как шаги В.2 и К3 при желании могут быть включены или пропущены. В следующей таблице показано, сколько в среднем времени уходит на выполнение каждого шага в зависимости от применения необязательной проверки. Оба 1.369 1 369 (25) 0.467 0.232 Ни Одного 1.369 0 0 1.369 Шаг В1 В2 ВЗ В4 Только ВЗ 1.369 0 1.369 1.134 Только В2 1.369 1.369 0 0.467 и > О, и < д(О/и) (26) для некоторой неотрицательной интегрируемой функции д, Если присвоить Х э'дд/(дд то веРОЯтность того, что Х < х, можно вычислить пУтем интегРиРаваниЯ по 21ид1О по всей области, определенной двумя соотношениями в (26) и добавочным условием в/и < х с последующим делением иа этот же интеграл, но без дополнительного условия.
Допустим, и = 1и, так что 22О = иддй Тогда интеграл имеет вид Следовательно, вероятность, что Х < хд равна д(д)дд// кд)дд. (27) 22 Я Нормальное распределение возникает, когда д(1) = е ' 2зд а условие из < д(О/и) упрощается в этом случае до (и/и)я < -4 1пи. Легко видеть, что множество всех (О, О), удовлетворяющих этому соотнонэению, полностью содержится в прямоугольнике на рис. 13.
Грани шагов В2 и ВЗ определяют внутреннюю и внешнюю области простыми граничными уравнениями. Хорошо известное неравенство е* > 1+к, справедливое для всех действительных чисел х, можно использовать, чтобы показать, что неравенства 1+ 1пс — си < — 1пи < 1/(си) — 1+ 1пс (28) Таким образом, стоит отбросить необязательную проверку, если есть быстрые операции логарифмирования, но если подпрограмма вычисления логарифмов выполняется довольно медленно, то проверку стоит включить. Но зачем делать эту работу7 По одной единственной причине — чтобы вычислить вероятность того, что Х < х, которая оказывается точным значением (10). Но такое вычисление вряд ли будет очень простым, если не удастся найти хороший прием.
Во всяком шэучае, в первую очередь, нужно понять, как может быть открыт такой алгоритм. Киндерман (К1пс1егшап) и Монахам (МопаЬап) открыли его, разрабатывая следующую теорию, которая может использоваться с любой хорошо себя ведущей плотностью /(х) [слэ. АСМ Тгапэ, Мас12. Яойяаге 3 (1977), 257 — 260). Предположим, что точка (7/, )д ) равномерно генерируется в области (и, эд)-плоскости, определенной неравенствами выполняются для любой константы с > О. В упр. 21 доказывается, что с = еья является наилучшей возможной константой для использования на шаге К2. Более сложная ситуация складывается на шаге В3, н в этом случае, кажется, не существует простого выражения для оптимального с, но вычислительные эксперименты показывают, что наилучшее значение с для шага К3 приблизительно равно е' зз.
Аппроксимирующей кривой (28) является касательная к истинной границе, когда и = 1/с. Существует возможность получения быстрого метода путем разделения области на подобласти, с болыпинством из которых иметь дело намного быстрее. Конечно, подразумевается, что нужны дополнительные таблицы, как в алгоритмах М и Г.
Интересная альтернатива, требующая меньшего числа вспомогательных таблиц, предложена Аренсом и Дитером в САСМ 31 (1988), 1330-1337. 5) Нормальная случайная величина из нормальной случайной величины. В упр. 31 обсуждается интересный подход, который позволяет экономить время работы, так как сразу использует нормальные случайные величины вместо равномерно распределенных случайных величин.
Этот метод, введенный в употребление в 1996 году К. С. Уэллесом (С. Я. %а1!асе), в настоящее время не нашел достаточного теоретического обоснования, но удовлетворяет многим эмпирическим критериям. 6) Нреобразования нормального распределения. До сих пор рассматривалось нормальное распределение со средним, равным нулю, и среднеквадратичным отклонением, равным единице. Если Х имеет такое распределение, то (29) имеет нормальное распределение со средним, равным Р, и среднеквадратичным отклонением, равным о.
Кроме того, если Х, и Хг — независимые нормальные случайные величины со средним, равным нулю, среднеквадратичным отклонением, равным единице, н у) — — р) +огХы 1г = рг+ог(РХг+ Л вЂ” Р Хг), (30) то 1'г н г'г — зависимые нормально распределенные случайные величины со средними, равными ры рг, среднеквадратичными отклонениями, равными оы ог, н коэффициентом корреляции Р. (Для генерирования и переменных обратитесь к упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
