伪随机数生成器

伪随机数生成器是一种确定性递归，它从一个初始种子开始，生成一个长的、可重现的数字序列，该序列模拟了单位区间上均匀分布的独立抽取。

Definition

伪随机数生成器是一种算法，由一个状态、一个推进状态的转换函数以及一个将每个状态映射到数字的输出函数定义，从而产生一个周期序列，旨在统计上与均匀随机数无法区分。

Scope

本主题涵盖了均匀生成器（线性同余、滞后斐波那契、广义反馈移位寄存器和组合生成器）的构造，决定其质量的结构特性，如周期长度和格点或均匀分布行为，以及用于验证它们的经验和理论测试。加密安全的生成器仅作为对比设计目标提及。

Core questions

• 哪些递归能产生长周期和良好的高维均匀性？
• 如何通过格点结构和均匀分布来衡量生成器的质量？
• 哪些经验测试集能检测出偏离随机性的情况？
• 如何对生成器进行播种和组合以延长周期并改善统计特性？

Key concepts

• 种子和状态
• 周期长度
• 均匀分布
• 格点结构
• 谱检验
• 组合生成器

Key theories

线性递归生成器

线性同余和移位寄存器递归通过模运算推进整数状态；它们的周期和连续输出的格点结构由乘数和模数的数论特性决定。

均匀分布与梅森旋转算法

基于扭曲广义反馈移位寄存器的生成器实现了巨大的周期和在多个维度上的可证明的均匀分布，使其成为统计模拟中广泛采用的默认选择。

Clinical relevance

统计软件包中的默认生成器决定了其产生的每次模拟、自举和蒙特卡洛结果的可重现性和有效性；理解周期和均匀分布有助于实践者避免使用那些隐藏规律可能破坏高维模拟的生成器。

History

Lehmer于1949年提出了线性同余法；后来的分析揭示了参数选择不当的格点缺陷，这促使了谱检验、组合生成器以及最终在1998年出现的梅森旋转算法等长周期均匀分布设计的产生。

Key figures

• Donald Knuth
• Pierre L'Ecuyer
• Makoto Matsumoto
• Derrick Henry Lehmer

Seminal works

• knuth1997
• matsumoto1998

Frequently asked questions

为什么一个伪随机数生成器比另一个更好？

一个好的生成器具有非常长的周期，即使在多个维度上也能均匀分布其输出，通过标准统计测试集，并且快速且可重现。差的生成器可能具有短周期或明显的格点模式，从而使模拟产生偏差。

为什么种子很重要？

种子固定了起始状态，因此整个序列都由它决定。记录种子可以使模拟完全可重现，而随意选择种子可能导致并行运行中出现重叠或相关的序列。