蒙特卡洛算法
💡 随机算法，通过随机样本估算真实值。
一、 Calculate
π
\pi
π
用蒙特卡洛近似估算出
π
\pi
π
的值
-
随机生成平面坐标系中的点
(x
,
y
)
,
x
∈
[
−
1
,
1
]
,
y
∈
[
−
1
,
1
]
(x,y),\space x\in[-1,1],\space y\in[-1,1]
(
x
,
y
)
,
x
∈
[
−
1
,
1
]
,
y
∈
[
−
1
,
1
]
，
x,
y
x,\space y
x
,
y
为
[−
1
,
1
]
[-1,1]
[
−
1
,
1
]
之间的均匀分布，所有的点都有相同的概率密度； -
正方形内切圆半径为1，随机样本落在圆内的概率=圆的面积/正方形的面积：
P=
π
4
P=\frac{\pi}{4}
P
=
4
π
； -
从正方形区域均匀随机抽样
n{\color{d44d37}n}
n
个点，在圆内的点的数量期望为
Pn
=
π
n
4
P{\color{d44d37}n}=\frac{\pi{\color{d44d37}n}}{4}
P
n
=
4
π
n
;-
已知坐标
(x
,
y
)
(x,y)
(
x
,
y
)
判断是否在圆内：若
x2
+
y
2
≤
1
x^2+y^2\le1
x
2
+
y
2
≤
1
则在圆内。
-
已知坐标
-
均匀随机抽样后有
m{\color{d44d37}m}
m
个点在圆内，若
n{\color{d44d37}n}
n
非常大，则真实观测值
m≈
π
n
4
{\color{d44d37}m}\approx\frac{\pi{\color{d44d37}n}}{4}
m
≈
4
π
n
； -
即得到
π≈
4
m
n
\pi\approx\frac{4{\color{d44d37}m}}{
{\color{d44d37}n}}
π
≈
n
4
m
； -
大数定律保证蒙特卡洛的正确性：
4m
n
→
π
,
as
n
→
∞
\frac{4{\color{d44d37}m}}{
{\color{d44d37}n}}\rightarrow\pi,\space \text{as}\space {\color{d44d37}n}\rightarrow\infty
n
4
m
→
π
,
as
n
→
∞
。
【
结论
】：从如图正方形中
均匀
抽样
n
{\color{d44d37}n}
n
个点，观测到
m
{\color{d44d37}m}
m
个点落在内切圆中，可近似得到
π
≈
4
m
n
\pi\approx\frac{4{\color{d44d37}m}}{
{\color{d44d37}n}}
π
≈
n
4
m
。
二、 Buffon’s Needle Problem
近似估算
π
\pi
π
值
-
在纸上画几条距离为
d{\color{337ea9}d}
d
的平行线； -
准备一些长度为
l{\color{337ea9}l}
l
的针； - 随机将针抛到纸上，针可能与平行线相交也可能不相交；
-
假设针的位置和角度都是均匀随机的，通过微积分算出相交的概率
P=
2
l
π
d
P=\frac{2{\color{337ea9}l}}{\pi{\color{337ea9}d}}
P
=
π
d
2
l
； -
随机往纸上扔
n{\color{d44d37}n}
n
根针，与平行线相交的针的数量期望为
Pn
=
2
l
n
π
d
P{\color{d44d37}n}=\frac{2{\color{337ea9}l}{\color{d44d37}n}}{\pi{\color{337ea9}d}}
P
n
=
π
d
2
l
n
； -
真实观测到有
m{\color{d44d37}m}
m
根针与平行线相交，若
n{\color{d44d37}n}
n
非常大，则真实观测值
m≈
2
l
n
π
d
{\color{d44d37}m}\approx\frac{2{\color{337ea9}l}{\color{d44d37}n}}{\pi{\color{337ea9}d}}
m
≈
π
d
2
l
n
； -
即得到
π≈
2
l
n
m
d
\pi\approx\frac{2{\color{337ea9}l}{\color{d44d37}n}}{
{\color{d44d37}m}{\color{337ea9}d}}
π
≈
m
d
2
l
n
。
三、估算阴影面积
-
对如图正方形区域内做均匀随机抽样得到多个点，判断点是否在阴影部分需满足两个条件；
-
在圆内：
(x
−
1
)
2
+
(
y
−
1
)
2
≤
1
(x-1)^2+(y-1)^2\le1
(
x
−
1
)
2
+
(
y
−
1
)
2
≤
1
； -
不在扇形内：
x2
+
y
2
≥
4
x^2+y^2\ge4
x
2
+
y
2
≥
4
；
-
在圆内：
-
假设阴影部分面积为
AA
A
，随机抽样的点落在阴影部分的概率为
P=
A
4
P=\frac{A}{4}
P
=
4
A
； -
均匀随机抽样
n{\color{d44d37}n}
n
个点，点落在阴影部分的期望为
Pn
=
A
n
4
P{\color{d44d37}n}=\frac{A{\color{d44d37}n}}{4}
P
n
=
4
A
n
； -
真实观测到有
m{\color{d44d37}m}
m
个点落在阴影部分，若
n{\color{d44d37}n}
n
非常大，则真实观测值
m≈
A
n
4
{\color{d44d37}m}\approx\frac{A{\color{d44d37}n}}{4}
m
≈
4
A
n
； -
即得到
A≈
4
m
n
A\approx\frac{4{\color{d44d37}m}}{
{\color{d44d37}n}}
A
≈
n
4
m
。
四、 近似积分
1. 用蒙特卡洛求一元函数定积分
Task
：求
I
=
∫
b
a
f
(
x
)
d
x
I=\int^a_bf(x)dx
I
=
∫
b
a
f
(
x
)
d
x
。
-
首先做
随机均匀抽样
：从
[a
,
b
]
[a,b]
[
a
,
b
]
中抽取
nn
n
个样本
x1
,
…
,
x
n
x_1,\dots,x_n
x
1
,
…
,
x
n
； -
计算
Qn
=
(
b
−
a
)
⋅
1
n
∑
i
=
1
n
f
(
x
i
)
Q_n=(b-a)\cdot\frac{1}{n}\sum^n_{i=1}f(x_i)
Q
n
=
(
b
−
a
)
⋅
n
1
∑
i
=
1
n
f
(
x
i
)
； -
Qn
Q_n
Q
n
即为积分
I=
∫
b
a
f
(
x
)
d
x
I=\int^a_bf(x)dx
I
=
∫
b
a
f
(
x
)
d
x
的近似值； -
大数定律保证蒙特卡洛的正确性：
Qn
→
I
,
as
n
→
∞
Q_n\rightarrow I,\space \text{as}\space n\rightarrow\infty
Q
n
→
I
,
as
n
→
∞
2. 用蒙特卡洛求多元函数积分
Task
：给出多元函数
f
(
x
)
f(\bold x)
f
(
x
)
，其中向量
x
∈
R
d
\bold x\in\Bbb R^d
x
∈
R
d
，求函数在集合
Ω
\Omega
Ω
（
Ω
⊂
R
d
\Omega \subset \Bbb R^d
Ω
⊂
R
d
）上的定积分：
I
=
∫
Ω
f
(
x
)
d
x
I=\int _\Omega f(\bold x)d\bold x
I
=
∫
Ω
f
(
x
)
d
x
。
-
随机抽样：从集合
Ω\Omega
Ω
中均匀抽取
nn
n
个样本，记作
x1
,
…
,
x
n
\bold x_1,\dots,\bold x_n
x
1
,
…
,
x
n
； -
计算集合
Ω\Omega
Ω
的体积：
V=
∫
Ω
d
x
V=\int_\Omega d\bold x
V
=
∫
Ω
d
x
；-
求体积
VV
V
也需要定积分，有可能与原问题同样困难，因此需要让集合
Ω\Omega
Ω
是简单的形状（长方体、球体等），用公式直接计算出体积，避免积分运算。
-
求体积
-
计算
Qn
=
V
⋅
1
n
∑
i
=
1
n
f
(
x
i
)
Q_n=V\cdot\frac{1}{n}\sum^n_{i=1}f(\bold x_i)
Q
n
=
V
⋅
n
1
∑
i
=
1
n
f
(
x
i
)
； -
Qn
Q_n
Q
n
即为积分
I=
∫
Ω
f
(
x
)
d
x
I=\int _\Omega f(\bold x)d\bold x
I
=
∫
Ω
f
(
x
)
d
x
的近似估计。
五、 近似期望
-
定义
X{\color{d44d37}X}
X
为
dd
d
维随机变量； -
定义
p(
x
)
{\color{orange}p(\bold x)}
p
(
x
)
为概率密度函数；-
性质：
∫R
d
p
(
x
)
d
x
=
1
\int_{\Bbb R^d}{\color{orange}p(\bold x)}d\bold x=1
∫
R
d
p
(
x
)
d
x
=
1
（连续分布）。
-
性质：
-
函数
f(
x
)
f(\bold x)
f
(
x
)
的期望：
EX
∼
p
[
f
(
X
)
]
=
∫
R
d
f
(
x
)
⋅
p
(
x
)
d
x
\Bbb E_{
{\color{d44d37}X}\sim{\color{orange}p}}[f({\color{d44d37}X})]=\int_{\Bbb R^d}f(x)\cdot{\color{orange}p(\bold x)}d\bold x
E
X
∼
p
[
f
(
X
)
]
=
∫
R
d
f
(
x
)
⋅
p
(
x
)
d
x
； -
首先随机抽样：（注意此处不是均匀抽样）根据概率密度函数
p(
x
)
{\color{orange}p(\bold x)}
p
(
x
)
随机抽取
nn
n
个样本，记作
x1
,
…
,
x
n
\bold x_1,\dots,\bold x_n
x
1
,
…
,
x
n
； -
计算
Qn
=
1
n
∑
i
=
1
n
f
(
x
i
)
Q_n=\frac{1}{n}\sum^n_{i=1}f(\bold x_i)
Q
n
=
n
1
∑
i
=
1
n
f
(
x
i
)
； -
Qn
Q_n
Q
n
即为对期望
EX
∼
p
[
f
(
X
)
]
\Bbb E_{
{\color{d44d37}X}\sim{\color{orange}p}}[f({\color{d44d37}X})]
E
X
∼
p
[
f
(
X
)
]
的估计。（样本数量
nn
n
越大，蒙特卡洛估计越准确）