0
JodeZer
source link: https://jodezer.github.io/2019/01/%E4%BC%AA%E9%9A%8F%E6%9C%BA%E6%95%B0%E4%B8%8E%E4%BB%BB%E6%84%8F%E5%88%86%E5%B8%83%E7%9A%84%E7%94%9F%E6%88%90
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
计算机软件里有大量需要生成随机数的场景，更准确一点，需要随机性。比如蒙特卡洛方法这样的模拟方法，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使用极坐标下的变换，使用两个独立的均匀分布随机变量得到一个二维联合正态分布，且两者独立，因此就可以得到正态分布。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK