计算科学 - VEGAS 中的重组算法 - 吾爱随笔录

我试图了解 VEGAS 的重组算法（原始出版物（LKlevin 的预印本）和实施说明）蒙特卡洛集成。我将尝试首先解释我认为我理解的内容，然后提出我的问题。

为简单起见，假设我们有一个一维函数 $f(x)$ 在整个区间内都是正数 $[0,1]$ . 这个区间被分成，比方说， $n$ 垃圾箱。这些箱最初大小相同。垃圾箱尺寸 $\Delta x_i$ 定义概率密度

ρ (x) = {\begin{cases} 0 \leq x < Δ x_{1} : \frac{1}{n Δ x_{1}} \\ ⋮ \\ Δ x_{n - 1} \leq x < Δ x_{n} : \frac{1}{n Δ x_{n}} \end{cases} .

$\rho(x) = \begin{cases} 0 \le x < \Delta x_1 : \frac{1}{n \Delta x_1} \\ \vdots \\ \Delta x_{n-1} \le x < \Delta x_n : \frac{1}{n \Delta x_n} \end{cases} .$

bin 大小必须加起来等于间隔的长度才能使 $\rho(x)$ 适当归一化：

\sum_{i = 1}^{n} Δ x_{i} = 1 \Rightarrow \int_{0}^{1} d x ρ (x) = 1.

$\sum_{i=1}^n \Delta x_i = 1 \quad \Rightarrow \quad \int\limits_0^1 \mathrm{d}x \, \rho(x) = 1.$

使用 $N$ 随机选择的数字 $\{ x_i \}$ 从分布 $\rho(x)$ VEGAS 计算一个近似值 $S^{(1)}$ 积分：

S^{(1)} = \frac{1}{N} \sum_{{x_{i}}} \frac{f (x_{i})}{ρ (x_{i})} \approx \int_{0}^{1} d x f (x)

$S^{(1)} = \frac{1}{N} \sum_{\{x_i\}} \frac{f(x_i)}{\rho(x_i)} \approx \int\limits_0^1 \mathrm{d}x \, f(x)$

到目前为止，这只是使用可变大小网格的重要性抽样（我对分层抽样不感兴趣）。VEGAS 中有趣的部分是 rebinning 算法，即根据之前迭代中累积的函数值重新计算 bin 大小的算法：

对于每个 bin，平方函数值 (?) 被求和（在原始出版物中，绝对值被求和）。
每个值还有一个阻尼函数，以“避免快速、不稳定的变化”。
之后，每个值都使用相邻的 bin 进行平滑处理。我想这也为某些函数的重新分箱算法增加了一些稳定性（但我无法解释原因）。让我们调用最终值 $b_i$ .
现在设置 bin 大小，使得每个新 bin 都包含大约平均值：

\bar{b} = \frac{1}{n} \sum_{i = 1}^{n} b_{i}

$\overline{b} = \frac{1}{n} \sum_{i=1}^n b_i$

该算法使 bin 在函数“小”的地方增长，在函数“大”的地方缩小。小和大是相互关联的，例如，函数的最大值被认为是“大”，而其他一切都被认为是“更小”。由于一个点的概率 $x$ 最终在任何 bin 中都是相等的（编写 VEGAS 是为了展示这种行为），函数在最大的地方被采样最多，从而减少了误差。

为什么会这样写？为什么不更直接地解决问题，例如将平均和分箱函数作为下一次迭代的概率密度？