随机数的线性同余生成器的质量

计算科学 计算物理学
2021-12-15 00:57:21

我正在对各种外力的朗之万方程进行一些模拟。被告知 C's rand()fromstdlib.h会在我的结果中引入偏差,我正在使用 Mersenne Twister。

不过,我想知道(并查看)线性同余生成器在我的模拟中究竟会引入什么样的错误。这些是我尝试过的事情:

  • 生成随机数的 3D 元组以尝试查看超平面。我什么都看不见。
  • 对大的随机数向量进行 FFT。Mersenne Twister 和rand().
  • 检查布朗运动中粒子的均分原理。两个积分器的期望值一致KE=12kBT具有相同数量的有效数字。
  • 看看他们在一些不是二次方的垃圾箱中的垃圾箱有多好。两者都给出相同的定性结果,没有一个更好。
  • 观察布朗路径可以看到明显的分歧x=0. 再次,没有运气。
  • 圆内点的分布。填充,并且仅在外围。在所有人之间以及最近的邻居之间(Shor 的回答,在评论下方)。在这个 gist中可用,只需在安装所需的库后使用 Julia 0.5.0 运行它(有关说明,请参阅 gist)。

我想强调的是,我正在寻找物理模拟中引入的偏差。例如,我已经看到rand()了顽固的测试如何失败,而 Mersenne Twister 没有,但目前这对我来说意义不大。

你有任何物理的、具体的例子来说明一个糟糕的随机数生成器是如何破坏蒙特卡罗模拟的吗?

注意:我已经看到 PRNG 有多RANDU糟糕。我对不明显的例子感兴趣,看起来很无辜但最终会引入偏见的生成器。

2个回答

一个有趣的参考文献描述了由于 RNG 不足(尽管他们没有使用 LCG)而导致物理系统的蒙特卡罗模拟失败:

A. Ferrenberg 和 DP 朗道。蒙特卡罗模拟:来自“好”随机数生成器的隐藏错误。物理评论快报 63(23):3382-3384, 1992。

Ferrenberg 和 Landua 研究的 Ising 模型是对 RNG 的良好测试,因为您可以与一个精确的解决方案(对于二维问题)进行比较,并找出数字中的错误。这些模型应该毫不费力地显示老式 32 位算术 PMMLCG 中的故障。

另一个有趣的参考是:

H. Bauke 和 Stephan Mertens。伪随机硬币正面多于反面。arXiv:cond-mat/0307138 [cond-mat.stat-mech]

Bauke 和 Mertens 强烈反对二进制线性反馈移位寄存器式随机数生成器。Bauke 和 Mertens 还有一些与此相关的其他论文。

在 3D 散点图中很难找到 Marsaglia 平面。您可以尝试旋转绘图以获得更好的视图,有时它们会突然出现在您身上。您还可以进行统计一致性的 3D 测试——对于较旧的 32 位 LCG,这些测试将在数量很少的 bin 中失败。例如,在 3 维中使用 20x20x20 的网格网格进行均匀性测试足以检测到广泛使用的(并且以前备受推崇的)PMMLCG 缺乏均匀性,其中 m=2^31-1, a=7^5。

可以使用PRNG 测试的 TestU01 套件来找出哪些测试rand失败。(有关测试套件的概述,请参阅TestU01:用于随机数生成器实证测试的 AC 库。)这比提出自己的蒙特卡洛模拟要容易。在某种程度上,这也是软件可组合性(和软件正确性)的问题:假设 PRNG 在小型、简单的测试中运行良好,你怎么知道它的病态行为不会被更大的程序触发?

这是代码:

#include "TestU01.h"

int main() {
  // Same as rand() on my machine
  unif01_Gen* gen = ulcg_CreateLCG(2147483647, 16807, 0, 12345);

  bbattery_SmallCrush(gen);
  bbattery_Crush(gen);

  return 0;
}

对于SmallCrush套件,15 次测试中有 3 次失败(请参阅 TestU01中的 guidelongtestu01.pdf 以获得详细描述和所有参考资料;这些是来自 10 次测试的 15 次统计)。

  • 生日间距:binn t维向量成dt垃圾箱,生成dt垃圾箱计数,I1,, 那么之间的碰撞次数{Ij+1Ij}遵循近似已知分布。

  • 碰撞:生成n t维向量[0,1)t, 将它们放入dt相等的超立方体,并计算碰撞次数。

  • MaxOft:生成n团体t中的值[0,1), 计算最大值X并比较各组的分布情况n 具有理论分布的最大值P(X<x)=xt; 值是n=2×106,t=6. 通过卡方检验和 Anderson-Darling 检验进行比较:χ2测试失败,p 值<10300,而 AD 测试通过(此 AD 测试在 Crush 中一些较大的类似测试中失败)。

假设这些都是“典型的”蒙特卡洛模拟(尽管它们可能不像您想到的问题),结论是它们中的 rand一些未知子集失败了。不过,我不知道为什么它特别是那个子集,所以我不可能说它是否适用于你自己的问题。

MaxOft似乎特别可疑,因为描述如此简单。

Crush套件中的测试中,140 次测试中有rand51 次失败(96 次测试中的 140 次统计)。一些失败的测试(如Fourier3)是在位串上完成的,所以它们可能与您无关。另一个失败的奇怪测试是GCD,它测试两个随机整数的 GCD 的分布。(同样,我不知道为什么这个特定的测试会失败,或者你的模拟是否会受到影响。)

PS:还有一点需要注意的是,rand()它实际上比一些成功通过所有SmallCrushCrushBigCrush测试的 PRNG 慢,例如MRG32k3a(参见上面的 L'Ecuyer & Simard 论文)。