蒙特卡洛积分法的方差缩减技术——分层采样法的自适应版本
字数 2895 2025-12-21 05:48:33

蒙特卡洛积分法的方差缩减技术——分层采样法的自适应版本

题目描述

考虑计算高维积分

\[I = \int_{\Omega} f(\mathbf{x}) \, d\mathbf{x}, \quad \Omega \subseteq \mathbb{R}^d \]

其中 \(d\) 较大，\(f\) 可能具有复杂的局部变化。分层采样法（Stratified Sampling）是蒙特卡洛积分中一种经典的方差缩减技术，它通过将积分域划分为互不相交的子区域（层），在各层内独立采样来降低估计方差。
本题要求：

  1. 推导分层采样法的基本公式及其方差表达式；
  2. 设计一种自适应分层采样算法，使得算法能根据函数 \(f\) 的局部波动情况自动调整层的划分和每层的采样数，以达到给定误差容限下总采样数最小；
  3. 分析该自适应算法的收敛性与计算复杂度。

解题过程

1. 分层采样法基础

将积分域 \(\Omega\) 划分为 \(m\) 个互不相交的子区域（层）\(\Omega_1, \Omega_2, \dots, \Omega_m\)，满足

\[\Omega = \bigcup_{k=1}^m \Omega_k, \quad \Omega_i \cap \Omega_j = \emptyset \ (i \neq j). \]

设第 \(k\) 层的体积为 \(V_k = \int_{\Omega_k} d\mathbf{x}\)，则积分可写为

\[I = \sum_{k=1}^m \int_{\Omega_k} f(\mathbf{x}) \, d\mathbf{x} = \sum_{k=1}^m V_k \cdot \mu_k, \]

其中 \(\mu_k = \frac{1}{V_k} \int_{\Omega_k} f(\mathbf{x}) d\mathbf{x}\) 是 \(f\) 在第 \(k\) 层的平均值。

在每层 \(\Omega_k\) 内独立抽取 \(n_k\) 个均匀分布样本 \(\mathbf{x}_{k,i} \sim U(\Omega_k)\)，用样本均值估计 \(\mu_k\)：

\[\hat{\mu}_k = \frac{1}{n_k} \sum_{i=1}^{n_k} f(\mathbf{x}_{k,i}). \]

积分估计量为

\[\hat{I}_S = \sum_{k=1}^m V_k \hat{\mu}_k. \]

该估计是无偏的：\(\mathbb{E}[\hat{I}_S] = I\)。

2. 方差分析

设 \(f\) 在 \(\Omega_k\) 内的方差为

\[\sigma_k^2 = \frac{1}{V_k} \int_{\Omega_k} \bigl(f(\mathbf{x}) - \mu_k\bigr)^2 d\mathbf{x}. \]

由于各层独立采样，估计量方差为

\[\mathrm{Var}(\hat{I}_S) = \sum_{k=1}^m V_k^2 \cdot \frac{\sigma_k^2}{n_k}. \]

若总样本数 \(N = \sum_{k=1}^m n_k\) 固定，为使方差最小，应取

\[n_k \propto V_k \sigma_k. \]

此时最小方差为

\[\mathrm{Var}_\text{opt} = \frac{1}{N} \left( \sum_{k=1}^m V_k \sigma_k \right)^2. \]

与简单蒙特卡洛（在整个 \(\Omega\) 均匀采样）的方差 \(\mathrm{Var}_\text{MC} = \sigma^2 / N\) 相比，分层采样方差减小量为

\[\sigma^2 - \frac{1}{N} \left( \sum_{k=1}^m V_k \sigma_k \right)^2. \]

当层内 \(f\) 变化平缓（\(\sigma_k\) 小）时，方差降低显著。

3. 自适应分层采样算法设计

目标：在满足误差容限 \(\epsilon\) 的前提下，最小化总样本数 \(N\)。

步骤 1：初始化划分

  • 将 \(\Omega\) 均匀划分为 \(m_0\) 个初始层（例如每维分成 2 份，共 \(2^d\) 层）。
  • 每层分配初始样本数 \(n_{\text{init}}\)（例如 10 个样本）。

步骤 2：误差估计与层选择

设当前划分有 \(m\) 个层，已得估计 \(\hat{I}_S\) 和方差估计

\[\widehat{\mathrm{Var}}(\hat{I}_S) = \sum_{k=1}^m V_k^2 \cdot \frac{s_k^2}{n_k}, \]

其中 \(s_k^2\) 是第 \(k\) 层样本方差的无偏估计。
若 \(\sqrt{\widehat{\mathrm{Var}}(\hat{I}_S)} < \epsilon\)，则停止；否则选择需要细分的层：
计算每层对总方差的贡献

\[C_k = V_k^2 \cdot \frac{s_k^2}{n_k}, \]

选择贡献最大的若干层进行细分。

步骤 3：自适应细分

对选中的层 \(\Omega_k\)，沿其方差最大的坐标方向（或所有维度）平分，生成两个子层。
更新划分后，重新分配样本：保持总样本数不变，按新估计的各层 \(V_k \hat{\sigma}_k\) 比例分配（\(\hat{\sigma}_k \approx s_k\)）。

步骤 4：迭代采样

在新划分下，对每层补充采样至分配的样本数，更新估计与方差。
返回步骤 2，直至误差满足要求。

4. 收敛性与复杂度分析

  • 收敛性：若 \(f\) 有界且分段连续，随着细分次数增加，层内方差 \(\sigma_k \to 0\)，则 \(\mathrm{Var}(\hat{I}_S) \to 0\)。自适应细分能更快降低方差。
  • 计算复杂度：每轮迭代需评估新样本点，设总迭代轮数为 \(T\)，总样本数 \(N\)，则计算成本为 \(O(N)\)。自适应细分的开销主要是选择细分层（需计算各层统计量），每轮 \(O(m)\)，通常 \(m \ll N\)，故总成本接近 \(O(N + T \cdot m)\)。
  • 优势：对 \(f\) 变化剧烈的区域自动加密采样，在相同 \(N\) 下比均匀分层方差更小，比简单蒙特卡洛收敛更快。

关键点总结

  1. 分层采样通过减少层内方差来降低总方差。
  2. 自适应分层根据局部方差动态调整划分，使资源集中在变化剧烈的区域。
  3. 算法在误差控制下自动决定细分与采样分配，适合高维非均匀函数积分。
  4. 该方法是方差缩减技术与自适应网格的结合，显著提升蒙特卡洛效率。
蒙特卡洛积分法的方差缩减技术——分层采样法的自适应版本 题目描述 考虑计算高维积分 \[ I = \int_ {\Omega} f(\mathbf{x}) \, d\mathbf{x}, \quad \Omega \subseteq \mathbb{R}^d \] 其中 \(d\) 较大，\(f\) 可能具有复杂的局部变化。分层采样法（Stratified Sampling）是蒙特卡洛积分中一种经典的方差缩减技术，它通过将积分域划分为互不相交的子区域（层），在各层内独立采样来降低估计方差。 本题要求： 推导分层采样法的基本公式及其方差表达式； 设计一种 自适应分层采样算法 ，使得算法能根据函数 \(f\) 的局部波动情况自动调整层的划分和每层的采样数，以达到给定误差容限下总采样数最小； 分析该自适应算法的收敛性与计算复杂度。 解题过程 1. 分层采样法基础 将积分域 \(\Omega\) 划分为 \(m\) 个互不相交的子区域（层）\(\Omega_ 1, \Omega_ 2, \dots, \Omega_ m\)，满足 \[ \Omega = \bigcup_ {k=1}^m \Omega_ k, \quad \Omega_ i \cap \Omega_ j = \emptyset \ (i \neq j). \] 设第 \(k\) 层的体积为 \(V_ k = \int_ {\Omega_ k} d\mathbf{x}\)，则积分可写为 \[ I = \sum_ {k=1}^m \int_ {\Omega_ k} f(\mathbf{x}) \, d\mathbf{x} = \sum_ {k=1}^m V_ k \cdot \mu_ k, \] 其中 \(\mu_ k = \frac{1}{V_ k} \int_ {\Omega_ k} f(\mathbf{x}) d\mathbf{x}\) 是 \(f\) 在第 \(k\) 层的平均值。 在每层 \(\Omega_ k\) 内独立抽取 \(n_ k\) 个均匀分布样本 \(\mathbf{x} {k,i} \sim U(\Omega_ k)\)，用样本均值估计 \(\mu_ k\)： \[ \hat{\mu} k = \frac{1}{n_ k} \sum {i=1}^{n_ k} f(\mathbf{x} {k,i}). \] 积分估计量为 \[ \hat{I} S = \sum {k=1}^m V_ k \hat{\mu}_ k. \] 该估计是无偏的：\(\mathbb{E}[ \hat{I}_ S ] = I\)。 2. 方差分析 设 \(f\) 在 \(\Omega_ k\) 内的方差为 \[ \sigma_ k^2 = \frac{1}{V_ k} \int_ {\Omega_ k} \bigl(f(\mathbf{x}) - \mu_ k\bigr)^2 d\mathbf{x}. \] 由于各层独立采样，估计量方差为 \[ \mathrm{Var}(\hat{I} S) = \sum {k=1}^m V_ k^2 \cdot \frac{\sigma_ k^2}{n_ k}. \] 若总样本数 \(N = \sum_ {k=1}^m n_ k\) 固定，为使方差最小，应取 \[ n_ k \propto V_ k \sigma_ k. \] 此时最小方差为 \[ \mathrm{Var} \text{opt} = \frac{1}{N} \left( \sum {k=1}^m V_ k \sigma_ k \right)^2. \] 与简单蒙特卡洛（在整个 \(\Omega\) 均匀采样）的方差 \(\mathrm{Var} \text{MC} = \sigma^2 / N\) 相比，分层采样方差减小量为 \[ \sigma^2 - \frac{1}{N} \left( \sum {k=1}^m V_ k \sigma_ k \right)^2. \] 当层内 \(f\) 变化平缓（\(\sigma_ k\) 小）时，方差降低显著。 3. 自适应分层采样算法设计 目标：在满足误差容限 \(\epsilon\) 的前提下，最小化总样本数 \(N\)。 步骤 1：初始化划分 将 \(\Omega\) 均匀划分为 \(m_ 0\) 个初始层（例如每维分成 2 份，共 \(2^d\) 层）。 每层分配初始样本数 \(n_ {\text{init}}\)（例如 10 个样本）。 步骤 2：误差估计与层选择 设当前划分有 \(m\) 个层，已得估计 \(\hat{I}_ S\) 和方差估计 \[ \widehat{\mathrm{Var}}(\hat{I} S) = \sum {k=1}^m V_ k^2 \cdot \frac{s_ k^2}{n_ k}, \] 其中 \(s_ k^2\) 是第 \(k\) 层样本方差的无偏估计。 若 \(\sqrt{\widehat{\mathrm{Var}}(\hat{I}_ S)} < \epsilon\)，则停止；否则选择需要细分的层： 计算每层对总方差的贡献 \[ C_ k = V_ k^2 \cdot \frac{s_ k^2}{n_ k}, \] 选择贡献最大的若干层进行细分。 步骤 3：自适应细分 对选中的层 \(\Omega_ k\)，沿其 方差最大的坐标方向 （或所有维度）平分，生成两个子层。 更新划分后，重新分配样本：保持总样本数不变，按新估计的各层 \(V_ k \hat{\sigma}_ k\) 比例分配（\(\hat{\sigma}_ k \approx s_ k\)）。 步骤 4：迭代采样 在新划分下，对每层补充采样至分配的样本数，更新估计与方差。 返回步骤 2，直至误差满足要求。 4. 收敛性与复杂度分析 收敛性 ：若 \(f\) 有界且分段连续，随着细分次数增加，层内方差 \(\sigma_ k \to 0\)，则 \(\mathrm{Var}(\hat{I}_ S) \to 0\)。自适应细分能更快降低方差。 计算复杂度 ：每轮迭代需评估新样本点，设总迭代轮数为 \(T\)，总样本数 \(N\)，则计算成本为 \(O(N)\)。自适应细分的开销主要是选择细分层（需计算各层统计量），每轮 \(O(m)\)，通常 \(m \ll N\)，故总成本接近 \(O(N + T \cdot m)\)。 优势 ：对 \(f\) 变化剧烈的区域自动加密采样，在相同 \(N\) 下比均匀分层方差更小，比简单蒙特卡洛收敛更快。 关键点总结 分层采样通过减少层内方差来降低总方差。 自适应分层根据局部方差动态调整划分，使资源集中在变化剧烈的区域。 算法在误差控制下自动决定细分与采样分配，适合高维非均匀函数积分。 该方法是方差缩减技术与自适应网格的结合，显著提升蒙特卡洛效率。