Метод Монте-Карло

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

Будак Владимир Павлович,
Национальный исследовательский
университет «МЭИ»
кафедра светотехники
: +7 (095) 763-5239
[email protected]

2. Стохастическая рекурсия лучей

L(r, l ) L0 (r, l)
1
2
L
(
r
,
l
)
(
r
;
l
,
l
)
F
(
r
,
r
)
(
r
,
r
)
d
r1
0 1 1
1
1
1
1
L0 (r2 , l 2 ) (r; l1 , l 2 ) F (r1 , r2 ) (r1 , r2 ) d 2 r2 (r; l, l1 ) F (r, r1 ) (r, r1 ) d 2 r1
Наилучший метод решения задачи стохастической рекурсии –
метод Монте-Карло

3. Определение метода Монте-Карло

Методом Монте-Карло называется метод моделирования
случайной величины с целью определения характеристик ее
распределения:
1. численный метод
2. можно решать любые задачи, а не только вероятностные:
a) при непосредственной реализации стохастической
модели говорят о прямом моделировании,
b) возможно "выдумывание" такого случайного процесса,
статистические характеристики которого соответствуют
некоторым характеристикам детерминированного
процесса.
Хотя добиться успеха можно, используя рулетку, карандаш и
бумагу, до появления ЭВМ метод не получил широкого развития

4. Задачи с равновероятными исходами

Основные понятия теории вероятности – анализ азартных игр – задачи с
равновероятными исходами:
• Вероятность орел – решка: P(о)= P(р)=1/2;
• Грань игральной кости: P(г)=1/6;
• Карта из колоды: P(к) =1/32;
1
В случае равновероятных исходов
P( A)
вероятность события A:
общее число исходов
4!
С
В такой системе возможны и более сложные
2!2! 3 4 0.0125
P
(
A
)
ситуации – вероятность двух тузов в прикупе:
32!
С
31 32
2!30!
2
4
2
32
Общее определение вероятности по Laplace
(Pierre-Simon, 1749–1827) для систем с
равновероятными исходами:
P( A)
число благоприятных исходов
общее число исходов
Системы с бесконечным числом исходов

5. Геометрическая вероятность

Hall A. On an experimental determinition of π. – Messeng. Math., 1873, V2. P.113:
ρ
L
L
l
α
ρ
[0, L], [0, ]
l sin условие пересечения
S(A)
α
π
Определим некоторую меру события, которая пропорцианальна площади:
S ( A) l
2l
P( A)
sin
d
S0
L 0
L
P( A)
n( A)
2l N
N
L n( A)
Частотное определение вероятности Mises Richard (1883, Львов - 1953, Бостон):
частота =
n( A)
P( A)
N N
Что такое предел экспериментальной величины с точки зрения
математической теории?

6. Вероятностное пространство

Ω
I.
ω
A
Задано пространство Ω элементарных событий (исходов) ω: ω Ω;
II. Событие A является множеством ω и подмножеством Ω – существует
набор правил, по которым из элементов ω можно образовывать систему
подмножеств – алгебра ;
III. Введена мера множества события A, удовлетворяющая правилам:
1. 1 P(A) 0: P(Ω)=1, P( )=0
2. Ai , i 1, n Ai
n
n
Aj , i, j 1, n, i j : P( Ai ) P( Ai )
i 1
i 1
Хорошо для математики, но неясна связь с физикой частотой события

7. Случайная величина

Случайная величина: функция ξ= ξ(ω), ω Ω на заданном вероятностном
пространстве (Ω, ,P);
Случайная величина сама является случайным событием на
вероятностном пространстве (X, ,Pξ) – непосредственно заданная
случайная величина;
Алгебра есть система интервалов на некотором сегменте X;
Pξ(B)= P(ξ B);
Случайная величина может быть:
1. непрерывной : P (dx) p ( x)dx
p ( x)dx 1
(X )
n
2. дискретной : P (dx) P ( x) ( x xi )
i 1
n
P (x ) 1
i 1
i
что позволяет не разделять непрерывную и дискретную
случайные величины

8. Моменты случайной величины

M
( ) P(d ) xP (dx) xp ( x)dx
( )
M n
(X )
- математическое ожидание (среднее)
(X )
1. Mc c;
3. M( 1 2 ) M 1 M 2 ;
2. Mc cM ;
4. M( 1 2 ) M 1 M 2
x n p ( x)dx
(X )
Центральные моменты
случайной величины:
Важнейшей из которых является дисперсия:
M( M ) n
( x M ) n p ( x)dx
(X )
D
( x M )
2
p ( x)dx
(X )
D M( M ) 2 M 2 2 M (M ) 2 M 2 (M ) 2 ;
1. Dc 0;
2. Dc c 2D ;
3. D( 1 2 ) D 1 D 2 ;
Моменты позволяют оценить не саму величину, а ее
распределение

9. Неравенство Чебышева

Чебышев Пафнутий Львович (1821–1894): ( 0) : P M
D
(X )
( x M )2 P (dx)
M
( x M )2 P (dx) 2
D
2
P (dx) 2 P M
M
Для дополнительного события: ( 0) : P M 1 D2
Специальная случайная величина:
1 N
i , ( i , i 1, N ) : (M i a) (D i 2 )
N i 1
2
1 N 1 N
1 N 1 N
M M i M i a, D D i 2 D i
N
N i 1 N i 1
N i 1 N i 1
1 N
2
1 N
P
P i a 1
a
i
N
2
N
N i 1
N i 1
Экспериментальное определение (измерение) математического
ожидания

10. Закон больших чисел в форме Bernoulli

Bernoulli Jacob (1654 - 1705):
ξi – индикатор события A:
1 N
n( A)
i N
N i 1
M i
1, если произошло A,
i
0, если не произошло A.
- частота события A.
P (d )
i
( )
P (d ) P( A)
по всем
A
n( A)
2
n( A)
P
P
P( A) 1
P( A)
N
2
N
N
N
Закон больших чисел является мостиком, соединяющим
математическую теорию с физическим содержанием

11. Математические основы метода

1. Неравенство Чебышева Пафнутий Львович (1821-94) в форме Bernoulli Jacob
(27.12.1654-16.08.1705)
1
( 0)( i , i 1, N ) : ( M i a ) ( D i ) P
N
2
2
i a 1
N 2
i 1
N
2. Центральная предельная теорема Moivre, Abraham de (1667-1754)-Laplace, PierreSimon (1749-1827)
1
P
N
t
C0 з
x
1
2
a
e
dt
i
N
2 x
3 N
i 1
N
2
3. Математическая статистика: соотношения справедливы при N , однако на
практике приходится иметь дело с конечной выборкой случайной величины 1,
…, N - статистикой случайной величины.
Не очевидно, что при конечной выборке лучшее выражением для
математического ожидания есть среднее арифметическое

12. Статистика

При конечной статистике лучшим приближением для математического ожидания будет
выражение
N
L ci i - линейность выражения сохранена для перехода в точное при N
i 1
Оценка характеристики случайной величины по статистике является несмещенной, если
ML M
N
c
i 1
i
1
Оценка является эффективной, если ее дисперсия - наименьшая:
N 1
N
N 1 2 N 1 2
N
2
2
2
D L D ci i ci min cN 1 ci D L ci 1 ci min
i 1
i 1
i 1
i 1
i 1
j 1, N 1 :
N 1
N 1
DL 0 2c j 2 1 ci 0 c j 1 ci cN : c1
cj
i 1
i 1
1 N 2
1
N
D
i
i N ( N 1)
N 1 i 1
i 1
2
cN
1
N

13. Расчет интегралов методом Монте-Карло

Любой определенный интеграл можно рассматривать как математическое ожидание:
f ( x )dx
(X)
(X)
f ( x)
p( x )dx,
p( x )
1. x X : p( x ) 0, причем p( x ) 0 только при f ( x ) 0;
2.
p( x )dx 1 - условие нормировки.
(X)
В соответствии с определенной статистикой его можно вычислять как среднее:
(X)
f ( x )dx
(X)
f ( x)
f ( ) 1
p( x )dx M
p( x )
p( ) N
N
i 1
f ( i )
p( i )
Конструктивность случайной величины – создание произвольной случайной
величины из стандартной α [0,1] – генератор случайных чисел.
Процесс создания на ЭВМ случайной величины с заданным
распределением называется ее розыгрышем

14. Общая схема Монте-Карло

1. По N независимым значениям конструируются N случайных величин
распределенных на множестве X с плотностью вероятности p(x);
2. Производится оценка интеграла по математическому ожиданию =f( )/p( ) как
среднего арифметического
1 N f ( i )
I f ( x )dx
N i 1 p( i )
(X)
3. Погрешность оценки проводится по центральной предельной теореме по дисперсии
2
2
D /N:
N f ( i )
1 N f ( i )
1
D
N 1 i 1 p( i )
N ( N 1) i 1 p( i )
Дисперсия метода Монте-Карло зависит от выбора плотности вероятности:
2
f ( x)
f 2 ( x)
f 2 ( x)
2
2
D1
dx I , D2
dx I 2
p1 ( x )dx I
p ( x)
p1 ( x )
p2 ( x )
(X) 1
(X)
(X)
За критерий эффективности алгоритма обычно берут t D ,
где t - время счета одного испытания

15. Моделирование непрерывных случайных величин

Теорема: Случайная величина , удовлетворяющая уравнению
F ( ) p( x )dx
распределена на отрезке [a, b] с плотностью вероятности p(x).
a
Для простоты p(x)>0, тогда F(x) строго монотонно возрастает на [a, b] от 0 до 1
уравнение F(x)= имеет только один корень:
P x x dx P F ( x) F ( x dx) F ( x dx) F ( x) p( x)dx [0,1]
Для многомерных случайных величин F(x1, …, xn)=F(x1) … F(xn) , и каждая координата
разыгрывается независимо друг от друга:
i 1, n : F ( i ) i
При независимых координатах (аргументах) имеем
pQ ( x1 ,
, xn )dx1
dxn p1 ( x1 )
pn ( xn )dx1
dxn FQ ( x1 ,
, xn )
1
p ( x)dx
1
a1
n
pn ( x )dx
an
Эффективность метода Монте-Карло возрастает с ростом
кратности интеграла

16. Пример расчета интеграла

0.8
4
I
0.6
4
sin xdx cos x 0 1
0
2
0.2929
2
0.4
4
I
0.2
0
sin x
1
xdx
x
C0
4
0
sin x
C0 xdx
x
0.0
0.0
0.2
4
C0
0
0.4
2 4
x
xdx 1 C0
2
I C0
1
N
N
i 1
0
0.6
32
32 2
xdx
2
2
0
2
4
2
32
C0
1 C0 2
32
sin 4 i
4
0.8
i
sin 4 i
2
2 1
C0
N i 1 4 i
N
2
I
2
I
I
I N
Метод Монте-Карло позволяет вычислить не только значение
интеграла, но и оценить точность вычислений

17. Многомерные случайные величины

Простейший случай независимых случайных величин, например, q – зенитный угол, j
– азимутальный угол: F(x1, …, xn)=F(x1) … F(xn)
i 1, n : F ( i ) i
pQ ( x1 ,
dxn p1 ( x1 )
, xn )dx1
1
, xn ) p1 ( x)dx
FQ ( x1 ,
a1
i
p ( x)dx ,
i
i
pn ( xn )dx1
dxn
n
pn ( x)dx
an
i 1, n
ai
Розыгрыш многомерной независимой случайной величины
аналогичен совокупности одномерных