Задача. Задача 4. Четвертая метод монтекарло. Цепи маркова

• Название: Четвертая метод монтекарло. Цепи маркова
• Анкор: Задача
• Дата: 13.01.2022
• Размер: 301 Kb.
• Имя файла: Задача 4.doc
• Тип: Документы; #330450
• страница: 1 из 3

ЧАСТЬ ЧЕТВЕРТАЯ

МЕТОД МОНТЕ-КАРЛО. ЦЕПИ МАРКОВА

Глава двадцать первая

МОДЕЛИРОВАНИЕ (РАЗЫГРЫВАНИЕ) СЛУЧАЙНЫХ ВЕЛИЧИН МЕТОДОМ МОНТЕ-КАРЛО

§ 1. Предмет метода Монте-Карло

Датой рождения метода Монте – Карло принято считать 1949 г.. когда американские ученые Н. Метрополис и С. Улам опубликовали статью «Метод Монте-Карло», в которой систематически его изложили. Название метода связано с названием города Монте – Карло, где в игорных домах (казино) играют в рулетку из простейших устройств для получения случайных чисел на использовании которых основан этот метод.

ЭВМ позволяют легко получать так называемые псев­дослучайные числа (при решении задач их применяют вместо случайных чисел); это привело к широкому внедрению метода во многие области науки и техники (статистическая физика, теория массового обслуживания, теория игр и др.). Метод Монте-Карло используют для вычис­ления интегралов, в особенности многомерных для решения систем алгебраических уравнений высокого порядка для исследования различного рода сложных систем (автоматического управления, экологических, биологических и т.д.).

Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую величину X, математическое ожидание которой равно а:



Практически же поступают так: производят п испытаний, в результате которых получают n возможных значении X, вычисляют их среднее арифметическое



и принимают х в качестве оценки (приближенного значе­ния) а* искомого числа а:



Поскольку метод Монте—Карло требует проведения большого числа испытаний, его часто называют методом статистических испытаний. Теория этого метода указы­вает, как наиболее целесообразно выбрать случайную величину X, как найти ее возможные значения. В част­ности, разрабатываются способы уменьшения дисперсии используемых случайных величин, в результате чего уменьшается ошибка, допускаемая при замене искомого математического ожидания а его оценкой а*.

Отыскание возможных значений случайной величины X (моделирование) называют «разыгрыванием случайной ве­личины». Изложим лишь некоторые способы разыгрывания случайных величин и укажем, как оценить допускаемую при этом ошибку.
§ 2. Оценка погрешности метода Монте—Карло

Пусть для получения оценки а* математического ожидания а случайной величины Х было произведено п независимых испытаний (разыграно п возможных значе­ний X) и по ним была найдена выборочная средняя , ко­торая принята в качестве искомой оценки: а*=х. Ясно, что если повторить опыт, то будут получены дру­гие возможные значения X, следовательно, другая сред­няя, а значит, и другая оценка а*. Уже отсюда следует, что получить точную оценку математического ожидания невозможно. Естественно, возникает вопрос о величине допускаемой ошибки. Ограничимся отысканием лишь верхней границы δ допускаемой ошибки с заданной ве­роятностью (надежностью) γ:



Интересующая нас верхняя граница ошибки δ есть не что иное, как «точность оценки» математического ожидания по выборочной средней при помощи доверительных ин­тервалов, о которой уже шла речь в гл. XVI. Поэтому воспользуемся результатами, полученными ранее, и рас­смотрим следующие три случая.

1. Случайная величина Х распределена нормально и ее среднее квадратическое отклонение σ известно. В этом случае с надеж­ностью γ верхняя граница ошибки (см. гл. XVI, § 15)

(*)

где п—число испытаний (разыгранных значений X);t— значение аргумента функции Лапласа, при котором Ф(t)=γ/2, а—известное среднее квадратическое откло­нение X.

Пример 1. С надежностью γ =0,95 найти верхнюю границу ошибки σ, если для оценки математического ожидания нормальной величины Х с известным средним квадратическим отклонением, равным 0,5, было разыграно 100 возможных значений X.

Решение. По условию, n=100, σ=0,5, Ф(t)= 0,95/2 =0,475. По таблице функции Лапласа (см. приложение 2) находим t=1,96. Искомая верхняя граница ошибки δ= 1,96·0,5/ ==0,098.
2. Случайная величина Х распределена нормально, причем ее среднее квадрати­ческое отклонение σ неизвестно. В этом слу­чае с надежностью γ верхняя граница ошибки (см. гл. XVI, § 16)

(**)

где п—число испытаний; s—«исправленное» среднее квад­ратическое отклонение, t_γ находят по таблице приложе­ния 3.

Пример 2. С надежностью γ =0,95 найти верхнюю границу ошибки δ, если для оценки математического ожидания нормальной величины Х было разыграно 100 ее возможных значений и по ним найдено «исправленное» среднее квадратическое отклонение s ==0,5. Решение. По условию, n=100, s=0,5. Используя таблицу приложения 3, по γ =0,95, n=100 находим t_γ,=1,984. Искомая верхняя граница ошибки δ = 1,984·0,5/ =0,099.

3. Случайная величина Х распределена по закону, отличному от нормального. В этом случае при достаточно большом числе испытаний (n>30) с надежностью, приближенно равной γ, верхняя граница ошибки может быть вычислена по формуле (*), если среднее квадратическое отклонение σ случайной ве­личины Х известно; если же σ неизвестно, то можно подставить в формулу (*) его оценку s—«исправленное» среднее квадратическое отклонение либо воспользоваться формулой (**). Заметим, что чем больше п, тем меньше различие между результатами, которые дают обе формулы. Это объясняется тем, что при п — распределение Стьюдента стремится к нормальному (см. гл. XVI, § 16, замечание). В частности (примеры 1 и 2), при n =100, γ=0,95 верхняя граница ошибки равна 0,098 по формуле (*) и 0,099 по формуле (**). Как видим, результаты раз­личаются незначительно.

Замечание. Для того чтобы найти наименьшее число испы­таний, которые обеспечат наперед заданную верхнюю границу ошибки δ, надо выразить n из формул (*) и (**):



Например, если δ==0,098, t=1,96, =0,5, то минимальное число испытаний, при которых ошибка не превысит 0,098, равно

п=1,9б2·0,5²/0,098²=100.
§ 3. Случайные числа

Ранее было указано, что метод Монте—Карло основан на применении случайных чисел; дадим опреде­ление этих чисел. Обозначим через R непрерывную слу­чайную величину, распределенную равномерно в интер­вале (0, 1).

Случайными числами называют возможные значения r непрерывной случайной величины R, распределенной равномерно в интервале (0, 1).

В действительности пользуются не равномерно рас­пределенной случайной величиной R, возможные значе­ния которой, вообще говоря, имеют бесконечное число десятичных знаков, а квазиравномерной случайной величиной R*, возможные значения которой имеют конечное число знаков. В результате замены R на R* разыгрываемая величина имеет не точно, а прибли­женно заданное распределение. В приложении 9 при­ведена таблица случайных чисел, заимствованная из книги: БольшевЛ. Н., Смирнов Н. В. Таблицы математической статистики. М., «Наука», 1965, с. 428.
§ 4. Разыгрывание дискретной случайной величины

Пусть требуется разыграть дискретную случай­ную величину X, т. е. получить последовательность ее возможных значений x_i (i= 1, 2, . . ., п), зная закон рас­пределения X:

X	x1	x2	…	xn
p	p1	p2	…	pn

Обозначим через R непрерывную случайную величину, распределенную равномерно в интервале (0, 1), а через r_j(j=1,2,…) возможные значения, т. е. случайные числа.

Разобьем интервал 0≤R<1 на оси Or точками с координатами р₁, p₁+p₂, р₁+р₂+p₃+…, р₁+р₂+…+p_n-1 на п частичных интервалов ∆₁,∆₂,…,∆_n:

Дл. ∆₁=р₁-0=р_i,

Дл. ∆₂=(р₁+р₂)-р₁,=р₂

……………………….

Дл. ∆_n=1-(p₁+p₂+…+ p_n-1) = Рп.

Видим, что длина частичного интервала с индексом i равна вероятности с тем же индексом:

Дл. ∆_i=р_i. (*)
Теорема. Если каждому случайному числу r_j(0 ≤r< 1), которое попало в интервал ∆_i, ставить в соответствие возможное значение x_i, то разыгрываемая величина будет иметь заданный закон распределения:

X	x1	x2	…	xn
p	p1	p2	…	pn

Доказательство. Так как при попадании слу­чайного числа r_jв частичный интервал ∆_i, разыгрываемая величина принимает возможное значение x_i, а таких интервалов всего n, то разыгрываемая величина имеет те же возможные значения, что и X, а именно х₁, х₂,...,x_n .

Вероятность попадания случайной величины R в ин­тервал ∆_i, равна его длине (см. гл. XI, § 6, замечание), а в силу (*) Дл. ∆_i=р_i. Таким образом, вероятность попадания R в интервал ∆_i равна р_i. Следова­тельно, вероятность того, что разыгрываемая величина примет возможное значение х_i, также равна р_i (поскольку мы условились в случае попадания случайного числа r_j в интервал ∆_i считать, что разыгрываемая величина приняла возможное значение х_i). Итак, разыгрываемая ве­личина имеет заданный закон распределения.

Правило. Для того чтобы разыграть дискретную слу­чайную величину, заданную законом распределения

X	x1	x2	…	xn
p	p1	p2	…	pn

надо: 1) разбить интервал (0, 1) оси Оr на п частичных интервалов: ∆₁—(0; р₁), ∆₂—( р₁+р₂+…+p_n-1);

2) выбрать (например, из таблицы случайных чисел) случайное число r_j.

Если r_j попало в частичный интервал ∆_i то разыг­рываемая дискретная случайная величина приняла воз­можное значение х₁.
Пример. Разыграть 8 значений дискретной случайной величины X, закон распределения которой задан в виде таблицы

X	3	11	24
p	0,25	0,16	0,59

Решение. 1. Разобьем интервал (0,1) оси Оr точками с коор­динатами 0,25; 0,25+0,16=0,41 на 3 частичных интервала: ∆₁— (0; 0,25), ∆₂—(0,25; 0,41), ∆₃—(0,41; 1).

2. Выпишем из таблицы приложения 9 восемь случайных чисел, например: 0,10; 0,37; 0,08; 0,99; 0,12; 0,66; 0,31; 0,85.

Случайное число r₁ =0,10 принадлежит частичному интервалу ∆₁, поэтому разыгрываемая дискретная случайная величина приняла воз­можное значение x₁=3. Случайное число r₂=0,37 принадлежит частичному интервалу ∆₂, поэтому разыгрываемая величина приняла возможное значение x₂ == 11. Аналогично получим остальные возмож­ные значения.

Итак, разыгранные возможные значения Х таковы: 3; 11; 3; 24; 3; 24; 11; 24.

Замечание. Далее будет показано, что разыгрывание собы­тий можно свести к разыгрыванию дискретной случайной величины. Сначала рассмотрим полную группу, состоящую из двух событий (см. § 5), а затем из п событий (см. § 6). Разумеется, полная группа из двух событий является частным случаем полной группы п событий. Однако исходя из методических соображений этот частный случай намерено выделен в самостоятельный параграф—§5.
§ 5. Разыгрывание противоположных событий

Пусть требуется разыграть испытания, в каждом из которых событие А появляется с известной вероят­ностью р и, следовательно, не появляется с вероятностью q=1—р.

Введем в рассмотрение дискретную случайную вели­чину Х с двумя возможными значениями (для определен­ности примем х₁=1,, х₂=0) и соответствующими им ве­роятностями р₁=р, р₂ = q. Условимся считать, что если в испытании величина Х приняла возможное значение х₁=1, то событие А наступило; если Х=х₂=0, то собы­тие A не наступило, т. е. появилось противоположное событие .

Таким образом, разыгрывание противоположных собы­тий А и сведено к разыгрыванию дискретной случай­ной величины Х с заданным законом распределения:

X	1	0
p	p	q

Для разыгрывания Х надо (по правилу § 4) интервал (0, 1) разбить точкой р на два частичных интервала: ∆₁—(0, р) и ∆₂—(р, 1). Затем выбирают случайное число r_j,. Если r_j, попадает в интервал ∆_1, то Х = х₁ (наступило событие A); если r_j, попадает в интервал ∆₂, то Х =x₂=0 (событие A не наступило).

Правило. Для того чтобы разыграть испытания, в каж­дом из которых вероятность появления события равна р и, следовательно, вероятность наступления противополож­ного события A равна 1- р, надо выбрать (например, из таблицы случайных чисел) случайное число r_j-(j=1, 2, ...); если r_j<р, то событие A наступило; если r_j≥р, то появилось противоположное событие .

Пример. Разыграть 6 испытаний, в каждом из которых событие А появляется с вероятностью р=0,35.

Решение. Выберем из таблицы приложения 9 шесть случайных чисел, например: 0,10; 0,36; 0,08; 0,99; 0,12; 0,06. Считая, что при r_j<0,35 событие А появилось, а при r_j≥0,35 наступило противо­положное событие , получим искомую последовательность событий: A, ,A, ,A,A.