【Mento Carlo 2】随机数发生器

本文介绍概念：
随机数生成器（均匀分布）
随机性的统计学证明

需要知识：
对分布的检验（卡方检验）

历史

机械结构

利用机械结构，例如彩票摇号机，缺点：

• 生成速度慢
• 不能被计算机直接调用
• 无法重复（有时要用同一组随机数测试两套模型策略）

预先生成随机数

预先生成随机数，并且保存到一个外置设备上。
例如兰德公司(RAND)出版过一本书《百万乱数表》

现代方法

用确定的整数递归方程生成 伪随机数 ，优点：

• 只用存储公式和种子

线性同余发生器

Xi=(aXi−1+c)modmXi=(aXi−1+c)modm

• mm:模数

• a∈[0,m−1]a∈[0,m−1]:乘子
• X0∈[0,m−1]X0∈[0,m−1]:种子
• c∈[0,m−1]c∈[0,m−1]:增量

当c>0c>0时，叫做 混合线性同余发生器
当c=0c=0时，叫做 乘性同余发生器

周期

易知，上面的线性同余发生器是存在周期的，这个周期小于m
实践中，当然想让 周期越大越好，

（Hull和Dobell，1962），线性同余发生器生成一个满周期随机序列，当且仅当：

• c与m互素
• a-1可以被m所有的素因子q整除
• 如果m是4的整数倍，a-1也是4的整数倍

混合线性同余发生器

当c>0c>0时，叫做 混合线性同余发生器

最好的做法是：
m=2bm=2b,b是计算机可以存放整数的最大位数,例如有些系统用32位表示正整数，最大为为符号为，那么b=31
c是奇数，便可以满足c与m互素的条件
a-1是4的倍数

Python实现

def random_func(seed,n):
    x=[]
    a=906185749
    m=2**31
    c=1
    temp = seed
    for i in range(n):
        temp=(a*temp+c)%m
        x.append(temp/m)
    return x

import matplotlib.pyplot as plt
seed=43322
plt.hist(random_func(seed,10000),bins=20)
plt.show()

乘性同余发生器

当c=0c=0时，叫做 乘性同余发生器

Xi=(aXi−1)modmXi=(aXi−1)modm

XiXi不能取到0，因此可能的最大周期是m-1
周期达到m-1的充要条件是：

• a是m的素元

随机数理论的检验

格子结构

def random_func(seed,n):
    x=[]
    a=906185749
    m=2**8
    c=1
    temp = seed
    for i in range(n):
        temp=(a*temp+c)%m
        x.append(temp/m)
    return x

import matplotlib.pyplot as plt
seed=43322
a=random_func(seed,1000)
x=a+[0]
y=[0]+a
plt.plot(x,y,'.')
plt.show()

横、纵坐标分别是xt−1,xtxt−1,xt

统计检验

算法生成了一组随机数RiRi,如何确定这个算法

卡方检验

前提：RiRi独立同分布
H0：RiRi服从均匀分布U(0,1)
方法：卡方检验
χ2=∑i(fi−ei)2eiχ2=∑i(fi−ei)2ei
fifi是离散化后的，每个区间的样本个数。
eiei是离散化后，每个区间的理论个数。

序列检验

前提：RiRi独立同分布，且服从均匀分布U(0,1)
H0：(Ri,Ri+1)(Ri,Ri+1)服从均匀分布U(0,1)2U(0,1)2
方法：卡方检验
划分为网格，统计每个小格子内的样本数量，进行同样的卡方检验。

其它的随机数发生器

组合发生器

例如：
Xi+1=(171Xi)mod30269Xi+1=(171Xi)mod30269
Yi+1=(172Yi)mod30307Yi+1=(172Yi)mod30307
Zi+1=(170Zi)mod30323Zi+1=(170Zi)mod30323

组合发生器就是这个：
Ri=(Xi30269+Yi30307+Zi30323)mod1Ri=(Xi30269+Yi30307+Zi30323)mod1

组合发生器的周期是3个发生器周期的最小公倍数。

斐波那契发生器

Xi+1=(Xi+Xi−1)modmXi+1=(Xi+Xi−1)modm

1. 最大可能周期是多少呢？ (Xi,Xi−1)(Xi,Xi−1)有m2m2种可能性

优点：
无须乘法运算
缺点：
序列随机性不高
改进：
混合其它发生器