在什么情况下蒙特卡洛积分优于准蒙特卡洛积分?

计算科学 蒙特卡洛
2021-12-15 03:53:11

一个足够简单的问题:做一个多维积分,考虑到人们已经决定某种蒙特卡罗方法是合适的,使用伪随机数的常规 MC 积分是否比使用准随机序列的准蒙特卡洛积分有任何优势? 如果是这样,我将如何识别这种优势会发挥作用的情况?(如果没有,为什么有人会使用普通的旧蒙特卡洛积分?)

3个回答

我的一些研究涉及求解大规模随机偏微分方程。在这种情况下,感兴趣的积分的传统蒙特卡罗近似收敛速度太慢,以至于它在实际意义上不值得......即我不想为了获得小数点的准确性而运行 100 倍以上的模拟到积分。相反,我倾向于使用其他方法,例如稀疏 smolyak 网格,因为它们在更少的函数评估中提供更好的准确性。这只是可能的,因为我可以假设函数具有一定程度的平滑性。

可以合理地推测,如果您期望要积分的函数具有一定的结构(如平滑度),最好使用利用它的准蒙特卡洛方案。如果你真的不能对函数做出很多假设,那么 monte carlo 是我能想到的唯一处理它的工具。

蒙特卡罗模拟是计算电子散射的首选方法。有时会使用重要性采样等技巧,因此您可能会说这不是普通的旧蒙特卡洛。但要点可能是这里模拟了一个固有的随机过程,而您只询问使用蒙特卡洛进行积分。

因为没有其他人试图提供答案,所以让我尝试扩展一下我的答案。假设我们有一个电子散射模拟,其中只计算一个数字,如反向散射系数。如果我们将其重新表述为多维积分,它可能是一个无限维积分。另一方面,在单个轨迹的模拟过程中,只需要有限数量的随机数(如果考虑到二次电子的产生,这个数字会变得非常大)。如果我们要使用像拉丁超立方体采样这样的准随机序列,我们将不得不使用具有固定维数的近似值,并为每个样本点的每个维生成一个随机数。

所以我认为区别在于是否采样了某种高维单位超立方体,而不是原点周围的无限维概率云。

在 Kocis 和 Whiten 的论文中讨论了传统蒙特卡洛积分相对于准蒙特卡洛积分的优势他们列出了以下原因:

  • qmc 方法的误差界限O(log(N)d/N)“理论上”比O(N1/2)由朴素的蒙特卡洛给出的界限。但是,对于N在当前硬件上可以在合理的时间内实现,O(N1/2)是更好的选择d40. (Kocis 和 Whiten 写于 1997 年,所以大概d从那以后有所增加。)
  • QMC 积分的误差受 Koksma-Hlawka 不等式的约束

    errorV[f]DN
    在哪里V[f]是的变化fDN是差异的明星。但引用 Kocis 的论文,

    不幸的是,现有序列的理论差异界限不适用于中等和较大的 s 值。另一种选择,对大 s 序列的星差异进行数值评估,需要过多的计算工作,即使是对这种差异的合理数值估计也很难获得。

    使用传统的蒙特卡洛积分,我们可以指定一个错误目标并等待,因为错误界限很容易计算。使用 QMC,我们必须指定一些函数评估,并希望错误在我们的目标范围内。(请注意,有一些技术可以克服这一点,例如随机准蒙特卡洛,其中使用多个准蒙特卡洛估计来估计误差。)

  • 由于我们实际上拥有的许多低差异序列的误差范围的“常数项”随着维度呈指数增长,因此 Kocis 和 Whiten 使用另一个度量来估计误差:样本点之间的最大距离。这给出了一个误差估计O(1/N1/2+2/d),他们声称它符合观察到的许多被积函数的行为。

  • 准蒙特卡洛要击败传统蒙特卡洛,被积函数必须具有“低有效维数”。请在此处查看 Art Owen 关于此主题的论文