背景

计算机软件里有大量需要生成随机数的场景，更准确一点，需要随机性。比如蒙特卡洛方法这样的模拟方法，Bootstrap中经验分布随机采样等等…如何依据想要的分布生成随机数，以及验证随机性是计算机时代大量工作的基础。

线性同余发生器(Linear Congruential Generator)

由递归式定义： X_n+1 = (a*X_n+c) mod m a称为乘数，c为步数， m为模数。

当给定x_0，也就是代码中经常需要设置的seed，随后的”随机数”就是确定的，因此称为伪随机。

在任意给定的<a,c,m>三元组中，由于X_i必然小于m，而X_i可以唯一确定X_i+1， 因此任意上述公式生成的递推序列，必然是有限循环的，并且周期小于等于m。

下面给出线性同余发生器，可取得最大理论周期m的三个条件：

• gcd(c, m) = 1
• 因式分解m所得的质数，是因式分解(a-1)所得的质数的子集。（Each prime factor of m is also a factor of(a-1) ）
• 如果m整除4， (a-1)整除4

具体证明略（因为我也不懂为什么）

分布

均匀分布

由线性同余发生器产生的数字，可以得到一个随机的值域为[0, m-1]的序列。当把产生的随机数/(m-1)，就映射到了[0,1]的区间上

任意分布

以上，可以产生均匀分布，均匀分布的值可以理解成任意0-1的概率，于是可以求反函数，将目标分布的累积分布函数解出应有的函数参数值，将随机性映射到目标分布随机变量的取值。

Box-Muller到正态分布

转换到正态分布并不能使用累积分布函数取反函数的方法，因为正态分布的CDF没有闭式解。BM使用极坐标下的变换，使用两个独立的均匀分布随机变量得到一个二维联合正态分布，且两者独立，因此就可以得到正态分布。