UA STAT675 统计计算I 随机数生成1 随机数生成器的一般理论

UA STAT675 统计计算I 随机数生成1 随机数生成器的一般理论

• • RNG的抽象表示
  • RNG的质量指标
  • RNG的统计检测

在统计计算中，从某个分布中进行采样通常分为两个步骤：

生成随机数$z_1,z_2,\cdots ,z_n{\sim }_{iid}U(0,1)$

基于$z_1,\cdots ,z_n$，根据某些变换或者某些操作(比如rejection\reweight等)得到服从该分布的随机数

实现第一步的算法通常被称为（伪）随机数生成器，简称RNG (pseudo random number generator)，毫不夸张地说，RNG就是统计计算的基础。按照RNG的采样方式不同，可以把它分为物理RNG与算法RNG；物理RNG就是基于一些具有"random"或者“chaotic”的物理现象得到随机数的生成器，但大家普遍认为物理RNG有下面一些缺点：需要安装一些实验设备，所以比较贵，生成随机数的速率非常慢，并且不能重复生成某一组随机数序列等，因此现在广为使用的是算法RNG。

RNG的抽象表示

L’Ecuyer (1990, 1994, 1996, 1997, 1998, 1999, 2001)对算法RNG进行非常全面的研究，我们可以以他提出的RNG的抽象表示作为基础。假设
$$RNG=(S,\mu ,f,U,g)$$

这里$S$是状态集，$f$是状态转移函数，$f:S\to S$，$U$是输出集，$U(0,1)$的RNG满足$U=(0,1)$，$g:S\to U$是输出函数，$f,g$都是确定性的函数，不产生随机性，$\mu$是$S$的概率分布，是用来选择初始状态(initial state或者seed)的，记选择的seed为$s_0$，则RNG的状态转移序列满足：
$$s_t=f(s_{t-1})$$

从而输出的随机数为$\{u_t:u_t=g(u_t)\}$。

因为$S$是有限集，所以$\forall l\ge 0$， $\exists j>0$，使得$s_l=s_{l+j}$，因为$f,g$不带来随机性，所以$\forall i\ge l$，$s_{i+j}=s_i,u_{i+j}=u_i$，也就是说在这种抽象模型下，RNG并不是完全随机的，当我们生成足够多的随机数之后，一定会出现重复的序列，这也是为什么算法RNG产生的是伪随机数的原因。我们称使得序列重复的最小的$j$为RNG的周期，记为$\rho$，显然$\rho \le |S|$，如果状态在计算中用$k$ bits表示，那么$|S|=2^k$，优秀的RNG的周期一定是接近甚至等于$2^k$的。

RNG的质量指标

在设计RNG的时候，我们总是需要考虑什么样的RNG才是好的RNG。先从算法的角度考虑，既然RNG也是一种算法，那么优秀的RNG一定具备优秀算法的品质：

Efficient：时间复杂度与空间复杂度都低

Repeatable：可以重复产生某一次的输出

Portable：可移植，在不同设备上都能有效工作

然而RNG比一般的算法更特殊一点，我们清晰地知道预期地输出是什么样子的，所以我们必须要加入一些其他的标准。

我们设计RNG的目标是得到$u_0,u_1,u_2,\cdots {\sim }_{iid}U(0,1)$。根据Kolmogorov extension theorem，$u_0,u_1,u_2,\cdots {\sim }_{iid}U(0,1)$等价于$\forall i\in \mathbb{N},t\in \mathbb{N}$，$(u_i,\cdots ,u_{i+t-1})\sim U((0,1{)}^t)$，可以验证算法RNG不一定满足这个条件：

假设我们从$S$中等可能选出一个seed，定义
$${\Psi }_t=\{(u_0,\cdots ,u_{t-1}):u_i=g(s_i),s_0\in S,s_i=f(s_{i-1})\}$$

则$u_{0,t}=(u_0,\cdots ,u_{t-1})\sim U({\Psi }_t)$，根据周期性，$u_{i,t}=(u_i,\cdots ,u_{i+t-1})\sim U({\Psi }_t)$。这是算法RNG生成的随机数服从的真实分布，与理论相比，要让这个RNG成为一个优秀的RNG，我们希望
$${\Psi }_t\approx (0,1{)}^t$$

综上，我们可以得到优秀的RNG应该满足的条件：

Efficient：时间复杂度与空间复杂度都低

Repeatable：可以重复产生某一次的输出

Portable：可移植，在不同设备上都能有效工作

${\Psi }_t=\{(u_0,\cdots ,u_{t-1}):u_i=g(s_i),s_0\in S,s_i=f(s_{i-1})\}\approx (0,1{)}^t$

RNG的统计检测

但我们依据上面四条质量指标设计出一个RNG之后，我们还需要对这个RNG进行统计检测。因为四条质量指标都是确定性的指标，不涉及随机性，但RNG的目标是生成iid的$U(0,1)$样本，所以我们需要用假设检验的思路对RNG进行统计检测。假设$u_0,u_1,\cdots$是RNG生成的样本，原假设为
$$H_0:u_0,u_1,u_2,\cdots {\sim }_{iid}U(0,1)$$

假设$T:(u_0,u_1,u_2,\cdots )\to X\in \mathbb{R}$，则$T$可以作为一个检验统计量，L’Ecuyer证明了不存在能通过所有可能的假设检验的RNG，所以只要一个RNG能通过简单的、常用的检验（比如卡方检验等），我们就称它为一个好的RNG。

总结

以上是生活随笔为你收集整理的UA STAT675 统计计算I 随机数生成1 随机数生成器的一般理论的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。