Question

1. 蒙特卡洛方法Monte Carlo 可以通过采用随机投点法来求解不规则图形的面积。

   求解结果并不是一个精确值，而是一个近似值。当投点的数量越来越大时，该近似值也越接近真实值。

2. 蒙特卡洛方法也可以用于根据概率分布来随机采样的任务。

1.1 布丰投针问题

1. 布丰投针问题是1777年法国科学家布丰提出的一种计算圆周率的方法：随机投针法。其步骤为：

   • 首先取一张白纸，在上面绘制许多条间距为 $ MathJax-Element-16 $ 的平行线。

   • 取一根长度为 $ MathJax-Element-17 $ 的针，随机地向纸上投掷 $ MathJax-Element-173 $ 次，观测针与直线相交的次数，记做 $ MathJax-Element-19 $ 。

   • 计算针与直线相交的概率 $ MathJax-Element-20 $ 。可以证明这个概率 $ MathJax-Element-21 $ 。因此有：

     $ \pi = 2 \frac{n\times l}{m\times d} $

2. 由于向纸上投针是完全随机的，因此用二维随机变量 $ MathJax-Element-22 $ 来确定针在纸上的具体位置。其中：

   • $ MathJax-Element-102 $ 表示针的中点到平行线的距离，它是 $ MathJax-Element-24 $ 之间的均匀分布。
   • $ MathJax-Element-25 $ 表示针与平行线的夹角，它是 $ MathJax-Element-26 $ 之间的均匀分布。

   

   当 $ MathJax-Element-27 $ 时，针与直线相交。

   由于 $ MathJax-Element-28 $ 相互独立，因此有概率密度函数：

   $ p(X=x,Y=y) = \begin{cases} \frac{4}{\pi d},& 0\le x\le d/2,0\le y\le \pi/2\\ 0,& \text{else} \end{cases} $

   因此，针与直线相交的概率为：

   $ P\{X\lt \frac l2\sin Y\}=\int\int_{x\lt \frac l2 \sin y} p(x,y) dxdy=\int_{x=0}^{x=\frac l2\sin y}\int_{y=0}^{y= \pi/ 2} \frac {4}{\pi d} dxdy=\frac{2l}{\pi d} $

   根据 $ MathJax-Element-29 $ 即可得证。

3. 布丰投针问题中，蒙特卡洛方法是利用随机投点法来求解面积 $ MathJax-Element-30 $ 。因为曲线的积分就是面积，这里的曲线就是概率密度函数 $ MathJax-Element-31 $ 。

1.2 蒙特卡洛积分

1. 对于函数 $ MathJax-Element-81 $ ，其在区间 $ MathJax-Element-77 $ 上的积分 $ MathJax-Element-34 $ 可以采用两种方法来求解：投点法、期望法。

2. 投点法求积分：对函数 $ MathJax-Element-81 $ ，对其求积分等价于求它的曲线下方的面积。

   此时定义一个常数 $ MathJax-Element-42 $ ，使得 $ MathJax-Element-37 $ ，该常数在区间 $ MathJax-Element-77 $ 上的面积就是矩形面积 $ MathJax-Element-39 $ 。

   随机向矩形框中随机的、均匀的投点，设落在函数 $ MathJax-Element-81 $ 下方的点为绿色，落在 $ MathJax-Element-81 $ 和 $ MathJax-Element-42 $ 之间的点为红色。则有：落在 $ MathJax-Element-81 $ 下方的点的概率等于 $ MathJax-Element-81 $ 的面积比上矩形框的面积 。

   具体做法是：从 $ MathJax-Element-77 $ 之间的均匀分布中采样 $ MathJax-Element-171 $ ，从 $ MathJax-Element-47 $ 之见的均匀分布中采样 $ MathJax-Element-48 $ ， $ MathJax-Element-49 $ 构成一个随机点。

   • 若 $ MathJax-Element-50 $ ，则说明该随机点在函数 $ MathJax-Element-81 $ 下方，染成绿色。
   • 若 $ MathJax-Element-52 $ ，则说明该随机点在函数 $ MathJax-Element-81 $ 上方，染成红色。

   假设绿色点有 $ MathJax-Element-54 $ 个，红色点有 $ MathJax-Element-55 $ 个，总的点数为 $ MathJax-Element-56 $ ，因此有： $ MathJax-Element-57 $ 。

   

3. 期望法求积分：假设需要求解积分 $ MathJax-Element-58 $ ，则任意选择一个概率密度函数 $ MathJax-Element-116 $ ，其中 $ MathJax-Element-116 $ 满足条件：

   $ \int_a^b p(x) dx = 1\\ \text{if} \;f(x)\ne 0\;\text{then}\; p(x)\ne 0 ,\quad a\le x\le b $

   令：

   $ f^*(x)=\begin{cases} \frac{f(x)}{p(x)},& p(x)\ne 0\\ 0,& p(x)=0 \end{cases} $

   则有： $ MathJax-Element-61 $ ，它刚好是一个期望：设随机变量 $ MathJax-Element-102 $ 服从分布 $ MathJax-Element-63 $ ，则 $ MathJax-Element-64 $ 。

   则期望法求积分的步骤是：

   • 任选一个满足条件的概率分布 $ MathJax-Element-116 $ 。
   • 根据 $ MathJax-Element-116 $ ，生成一组服从分布 $ MathJax-Element-116 $ 的随机数 $ MathJax-Element-68 $ 。
   • 计算均值 $ MathJax-Element-69 $ ，并将 $ MathJax-Element-70 $ 作为 $ MathJax-Element-71 $ 的近似。

4. 在期望法求积分中，如果 $ MathJax-Element-72 $ 均为有限值，则 $ MathJax-Element-116 $ 可以取均匀分布的概率密度函数：

   $ p(x) = \begin{cases} \frac {1}{b-a},& a\le x\le b\\ 0,& \text{else} \end{cases} $

   此时 $ MathJax-Element-74 $ ， $ MathJax-Element-75 $ 。

   其物理意义为： $ MathJax-Element-76 $ 为在区间 $ MathJax-Element-77 $ 上函数的平均高度，乘以区间宽度 $ MathJax-Element-78 $ 就是平均面积。

   

5. 对于期望 $ MathJax-Element-79 $ ，如果 $ MathJax-Element-116 $ 或者 $ MathJax-Element-81 $ 的表达式比较复杂，则也可以转化为另一个期望的计算。

   选择一个比较简单的概率密度函数 $ MathJax-Element-120 $ ，根据：

   $ \mathbb E_p[f(X)]=\int f(x) p(x)dx=\int f(x)\frac {p(x)}{q(x)}q(x)dx $

   令 $ MathJax-Element-83 $ ，则原始期望转换为求另一个期望 $ MathJax-Element-84 $ 。此时可以使用期望法求积分的策略计算。

1.3 蒙特卡洛采样

1. 采样问题的主要任务是：根据概率分布 $ MathJax-Element-116 $ ，生成一组服从分布 $ MathJax-Element-116 $ 的随机数 $ MathJax-Element-87 $ 。

   • 如果 $ MathJax-Element-116 $ 就是均匀分布，则均匀分布的采样非常简单。

   • 如果 $ MathJax-Element-116 $ 是非均匀分布，则可以通过均匀分布的采样来实现。其步骤是：

     • 首先根据均匀分布 $ MathJax-Element-124 $ 随机生成一个样本 $ MathJax-Element-91 $ 。

     • 设 $ MathJax-Element-106 $ 为概率分布 $ MathJax-Element-116 $ 的累计分布函数： $ MathJax-Element-113 $ 。

       令 $ MathJax-Element-95 $ ，计算得到 $ MathJax-Element-96 $ ，其中 $ MathJax-Element-97 $ 为反函数，则 $ MathJax-Element-121 $ 为对 $ MathJax-Element-116 $ 的采样。

     

2. 通过均匀分布的采样的原理：假设随机变量 $ MathJax-Element-100 $ 满足 $ MathJax-Element-101 $ ，则 $ MathJax-Element-102 $ 的概率分布为：

   $ p_Z(z) \frac{d}{d x} \tilde P(x) $

   因为 $ MathJax-Element-103 $ 是 $ MathJax-Element-104 $ 上面的均匀分布，因此 $ MathJax-Element-105 $ ； $ MathJax-Element-106 $ 为概率分布 $ MathJax-Element-116 $ 的累计分布函数，因此 $ MathJax-Element-108 $ 。因此上式刚好等于 $ MathJax-Element-116 $ ，即： $ MathJax-Element-121 $ 服从概率分布 $ MathJax-Element-116 $ 。

   这其中有两个关键计算：

   • 根据 $ MathJax-Element-116 $ ，计算累计分布函数 $ MathJax-Element-113 $ 。
   • 根据 $ MathJax-Element-114 $ 计算反函数 $ MathJax-Element-115 $ 。

   如果累计分布函数无法计算，或者反函数难以求解，则该方法无法进行。

3. 对于复杂的概率分布 $ MathJax-Element-116 $ ，难以通过均匀分布来实现采样。此时可以使用接受-拒绝采样 策略。

   • 首先选定一个容易采样的概率分布 $ MathJax-Element-120 $ ，选择一个常数 $ MathJax-Element-118 $ ，使得在定义域的所有位置都满足 $ MathJax-Element-119 $ 。

   • 然后根据概率分布 $ MathJax-Element-120 $ 随机生成一个样本 $ MathJax-Element-121 $ 。

   • 计算 $ MathJax-Element-122 $ ，以概率 $ MathJax-Element-123 $ 接受该样本。

     具体做法是：根据均匀分布 $ MathJax-Element-124 $ 随机生成一个点 $ MathJax-Element-125 $ 。如果 $ MathJax-Element-126 $ ，则接受该样本；否则拒绝该样本。

     或者换一个做法：根据均匀分布 $ MathJax-Element-328 $ 生成一个随机点，如果该点落在灰色区间（ $ MathJax-Element-358 $ ）则拒绝该样本；如果该点落在白色区间（ $ MathJax-Element-353 $ ）则接受该样本。

   

4. 接受-拒绝采样 在高维的情况下会出现两个问题：

   • 合适的 $ MathJax-Element-365 $ 分布比较难以找到。
   • 难以确定一个合理的 $ MathJax-Element-118 $ 值。

   这两个问题会导致拒绝率很高，无效计算太多。