Соболь И.М. Численные методы Монте-Карло (1973), страница 8

УПРЛ>КНШГМЯ К ГЛЛВЕ ! Из этой формулы следует, что хотя Р(0<л) -ь х прп и-ь от тем ие менее при и=!О" и х=!О г' вероятность Р(йт, )О ь] = 2 1О ь, что в два раза больше, чем при равномерном распределении. Так как алгоритм ун+! Д (10аут) близок к алгоритму середины квадрата: у произведения у„ отбрасываются й старших цифр слева, то этот я результат в какой-то мере объясняет, почему в методе середины квадрата получается больше, чем иапо,малых чисел.

5. Доказатгь что если М с и и Л! с те взаимно простые, то из формулы (7) следует, что а) т„й"те (шод М); б) для последовательности те, шь",то всегда Л=Р; в) длина периода Р рвана наименьшему целому корню сравнения й — 1тмО(глод М). 6. Обобщить теорему 3 на случай метода возмущений (!2) !!ш Р(1,1Р'ЛМ <я) = ! — г-т*". гг У к а за ни е. Предположить, что прн вссх возможных аргумеи. тах к функции Ф(х) и тр(х) не равны и использовать вероятностную модель п.

2.3. Роль ь играет нот ер опыта, в котором впервые уь — — уг, 1<Д и в то же время Л вЂ” 1==-0(шод М) (И. М. Соболь [79]). 7. Доказать, что если последователю!ость и„аь ..., ст„... удовлетворяет моноцинлическому уравнеишо (13), то при каждом з таком, что ! <з<г, среди групп вида (а„,..., ан4т ! ) прн 0<о< <Р— ! встречаются по 2' ' раз все аозт,ожпые гр)ппы, состоящие из нулей и единиц, кроме группы (О, ..., 0), которая встречается 2г — т — 1 раз. (Н. Цирлер [185]). У к аз а н не. Доказать сначала это для з=г. 8.

В качестве меры отклонения гм(х) от Г(х) (см п. 3.!.4) моткпо использовать величину тт ацР [ гм (х) — Г (х) ~. — м Стмт Критерий Колмогорова, близкий к критерию ы' и в некоторых случаях более удобный, основан на тсореме А. Н. Колтюгорова. Теор ем а. Какова бы ни было елрчайлал ее:юсина $ с непрерывной фрнкг!ггед распределения р(х), лри каждом х)0 1'пп Р ()т Л'0 < х] = К (х). М-т ет где К(х) =1+2 члт ( — 1)ге ь ! (Таблица функции распределения Колмогорова К(х) имеется на стр. 293 ) Доказать, что для расчета 0 моткно использовать формулу Р = шах [~ р (7, „) — — ~; ~ — — р(8(а!) ~~. ГЛАВА г ПРЕОБРАЗОВАНИЯ СЛУЧАИНБ1Х ВЕЛИЧИН В этой главе рассмотрены преобразования, позволяющие с помощью случайных чисел 7 вычислять зиачепия любой случайной величины Ц.

Такие вычисления называют л~оделированием случайной величины $ или форвированиелг реализаций случайной величины Впрочем, вычислители предпочитают их называть разыгрыванием величины й. Владение этими преобразованиями необходимо каждому, кто желает овладеть етехпикой» применения методов Моите-Карло.

Автор ие старался изложить здесь максимальное количество рецептов для моделирования различных величин — это сделано в специальной литературе (см. (!9, 69, 111]). Упор сделан иа изложение методов и их систематизацию. Впервые в основу классификации преобразований положено количество случайных чисел, используемых при расчете одпого значения ~. !1оиачалу этот принцип могкет показаться несколько искусствениым, по в полной мере его роль выяснится в гл. 7.

Некоторые из общих методов, наиболее важные с точки зрения практики, сформулированы в виде теорем. Замечания практического характера см. в п. 5.7. $ 1. Метод обратных функций (осиовиой прием моделирования случайигях величин) 1.1. Моделирование дискретных случайных величин.

Рассмотрим дпскре1пую случайную величину $ с распределением х, х, ... х„ метод оврлтных ьхнкшщ й 11 где Рг= Р(аь=х,), Длн того чтобы вычислить значения этой величины разделим интервал 0(у(! на интервалы бг такие (рпс. 14), что длина б, равна Рь Теорема !. Случаг!ная величина с, определенная формулой (2) $=хь когда Теиб, имеег распределение вероятностей (1), Доказательство занимает одну строку: А х)г Р(й=х,) =-Р(Т~Л,) = длина б,=рь л, Для практической реализации формулы (2) рпс 14. удобно в накопителе ЭВУ! распологкить подряд значе- ния х„х,, х„и рь Р~+Ра, Рг+Ра+Рз,, 1.

Для того чтобы вычислить очередное значение $, находим очередное Т. Затем сравниваем Т с Рь Если Т~рь то й=хг; если Т Рь то сРавниваем Т с Р,+Рх. Если Т(рг+Рз, то Ц=хх; если Т~рг+Рз, то сравниваем Т с Р1+/та+!тз, И т. д. 1.1Л. Легко видеть, что в случае, когда $ = х, (1(1(п — 1), првходктгя осуществить 1 сравпечий, в лишь в случае, когда с = х„, число сравнений равно и — 1. Поэтому среднее число сравнений, затрачиваемых при получскви одного значения к, равно 1= 2Р гр+(п-1)р.. Так как порядок значений хь ..., х„ в (1) прокзволен, го выгодно расположить вх в порядке убывания вероятностей, г. е так, чтобы Р~)Рг Ь ...

) Рв, ТОГДа ВЕЛПЧПпа Г бУДЕт МпиаМаЛЬНОй (10. Г. ПОЛ- ляк 169!). 1.!.2. Расчет по формуле (2) заметно упрощается в случае, когда все значения хг, ..., х„р а в н о в е р о я т. н ы: Рг= ... =Р„=1/и. В этом случае многократные сравнения ие нужны: так как бн — это интервал (1 — !) )п(у((/и, то условие Тепаи равносильно условиго 1 — 1~пТ(!, пли (((пТ) =1 — 1. Вместо формулы (2) можно записать, что $=хь где 1= !+Ц(пТ). 46 пгеоаиязоадния случайных величин пл 3 1.1.3. Теорему ! легко обобщить на случайную величину„которая может принимать бесконечную последовательность значений хь хз, ..., х„, ... и имеет распределение / хз ...

х„ у рг Рз . р„ В этом случае числа х„и р. задаются формулами, и вычисление их при каждом расчете Ц может оказаться весьма трудоемким. Тогда можно выбрать число потак, чтобы сумма вероятностей рг+ ...+р„„была достаточно близкой к 1, и значения хь ..., х,, и рь ..., р,, заготовить заранее. Вычислять х, и р, по формулам придется только при г)гт„ а это будет достаточно редко. 1.2.

Моделирование случайных событий.Моделирование случайных событий сводится к моделированию дискретных случайных величин. Чтобы показать, как это делается, рассмотрим четыре задачи, в каждой пз которых требуется моделировать последовательность одинаковых независимых испытаний. 1.2.1. В каждом из испытаний может наступить или не наступить некоторое событие А, вероятность наступления которого Р(А) =р задана. Рассмотрим случайную величину $, называемую индикатором события А, которая равна ! при наступлении А и 0 при наступлении противоположного события А.

Распределение й задается таблицей Согласно теореме ! для осуществления каждого испытания надо найти случайное число т и проверить неравенство т(р. Если оио выполнено, то событие А в этом испытании произошло, а если Т)р, то нет. 1.2.2. С испытанием связана полная группа попарно несовместных событий *) Аг, ..., А„ и заданы вероятно. сти Р(Аг)=рг Для моделирования таких испытаний рассмотрим случайную величину к — номер наступившего события. '! Эго значит, что суьгьга А,+...+А„есть достоверное сооы. тие и А "А. = 0 при гФ/.

т т 4т матод овплтных пункция 4 и Очевидно, распределение $ выражается таблицей Для осуществления каждого испытания надо выбрать случайное число у и по теореме ! разыграть значением. Если $=й то произошло событие Аь Пример. Столкнувшись с ядром атома урана, нейтрон может ассеяться, быть захваченным или вызвать деление ядра.

Есин через обозначить соответствующие этим событиям сечения взаимодействия, а через ~ = ~ + ~ + ~'„— полное ссчение 5 г / взанмодсйствия нейтрона с идром, то вероятности тпех возможных событий раины соответственно ~~,/~, ~' /~ и ~ //~~. Чтобы разыграть «судьбу» нейтрона при столкновении, выбирают случайное число у; если у( ~,/~~, то считают, что нейтрон рассеялся; если ~~»/Х( у ((~~5/~~)+(~55/2~), то нейтрон поглотился; если(~5/~)+ + (~,/Ъ ) (у, то иейтрон вызвал деление ядра. 1.2.3. С испытанием связаны два везависичых совместных событня А и В, вероятности которых заданы: Р (А) = РА Р (В) = ра.

Ввиду независимости событий А и В можно последовательно моделировать их наступление в казкдом испытании: сперва по числу у, методом п. !.2 ! определить, наступило ли событие А, а затем точно также по числу уз определить, наступило ли событие В. Однако чзсто более экономен другой способ. Рассмотрим полную группу попарно несовместных событий, состоящую из четырех событий: А»=АВ А»=АВ Аз АВ А«=АВ. Вероятности этих событий легко вычислить: Рт РАРВ Р5 РА (! РВ) Рз = Рн(! РА) Р» = (! — РА) (! — Рн) ° Следовательно, метод п. !.2.2 позволяет, используя одно случайное число у, определить, какой из этих четырех исходов наступил в моделируемом испытании 1.2.4.

С испытанием связаны два зависимых совместных события А и В, и заданы вероятности Р(А) = РА,! (В) = Ра, Р (АВ) = Рлп. В этом случае также следует рассмотреть полную группу собьпий (3), только вероятности зтнх событий вычисляются иначе: Р5 РАВ Рз РА РАВ Р» РВ РАВ' Р5 = 1 РА РВ+ !»АВ. Впрочем, и в этом случае можно осуществить последовательное моделирование событий А и В, используя дна случайных числа 4З ПРЕОБРАЗОВАНИЯ СЛУЧАЙНЫХ ВЕЛИЧИН /гл. 3 уь ут. Сперва по числу у~ (методом п.

12.1) определяем, наступило ли событие А. Если А наступило, то, зная условную вероятность Р(В/А) = Рлв/Рл, можно по числУ тз опРеделить, настУпнло ли событие В; условием наступления В сл>жпт выполнение неравенства та(Р(В/А). Если >ке событие А нс наступило, то наступление В придется разыгрывать с помоптью условий вероятности Р(В/А), которая равна Р(В/А) (Рв Рлв)/Π— Рл) !.3. Моделирование непрерывных случайных величин.

Предположим, что случайная величина ~ определена в интервале а(х(Ь и имеет плотность р(х) ~О прн а(х(Ь. Обозначим через г" (х) функцию распределения $, которая при а(х(Ь равна к т (х) == ~ р (и) ди. а Случай а= — оо и (плп) Ь=оо пе исключается. Теорема 2. Случайная величина $, удовлетворяютиая уровне~и>о. г(ь) =Т ижеет плотность распределения р(х), Доказательство. Так как функция г(х) строго возрастает в пнтервале (а, Ь) от г(а) =0 до Г(Ь) =-1, то уравнение (4) имеет единственный корень при каждом т (рис.

!5). Прн этом равны вероятности Р(х.СВ(х+с/х) = =Р(Р(х) <Т(Р(х+дх) ). И так как случайная величина Т равномерно распределена в интервале (О, 1), то * Р(х($(х+дх) = а Р хЯ хч/х х =г" (х+дх) — г (х) =р(х) с/х, Рис, 15. что и требовалось доказать.