统计学/数值方法/随机数生成

定义和用法

随机数 → ”一串整数或数字组，在序列中的任何位置都绝对没有相互关系。在任何时刻，所有整数都有相等的出现机会，并且它们以不可预测的方式出现”

许多统计方法依赖于随机数。然而，随机数的使用已经扩展到随机抽样或随机分配处理到实验单位之外。现在更常见的用途是在物理过程、分析上难以处理的数学表达式或从给定样本中对该总体进行重采样的模拟研究中。这三个应用的总体领域有时被称为模拟、蒙特卡洛和重采样。

均匀随机数生成

给定一个无限序列 $R_{0},R_{1},...,R_{n},...$，大多数人对随机的理解包括这些数字在区间 (0, 1) 中均匀分布。我们用 U(0, 1) 表示这种分布。我将在本文中介绍生成均匀随机数的两种方法：线性同余生成器和Tausworthe 生成器。

线性同余生成器

D. H. Lehmer 在 1948 年提出了线性同余生成器作为随机数的来源。在这个生成器中，每个数字都决定了它的后继者。生成器的形式是

                       $X_{i+1}$ = (a$X_{i}$ + c) mod m   , with  0 ≤ $X_{i}$ ≤ m .

m 称为模数。 $X_{0}$、a 和 c 分别称为种子、乘数和增量。

例如，考虑 m = 31、a = 7、c = 0，并从 $X_{0}$ = 19 开始。序列中的下一个整数是

                      9, 1, 7, 18, 2, 14, 5, 4, 28, 10, 8, 25, 20, 16, 19,

因此，当然，此时序列开始重复。

如果我们取 a = 3 而不是 a = 7，我们将得到

     26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, 15,
              14, 11, 2, 6, 18, 23, 7, 21, 1, 3, 9, 27, 19

从上面的简单例子中，我们可以猜到模数、乘数和增量在线性同余生成器的周期长度中起作用。

周期 → 周期是最小的正整数 λ，对于它 $X_{\lambda }=X_{0}$。周期不能大于 m。因此，m 被选择为等于或接近计算机中可表示的最大整数，以获得较长的周期。

一个全周期生成器是周期为 m 的生成器，当且仅当

1. c 与 m 互质；2. (a-1) 是 m 的每个素因子 q 的倍数；3. 如果 m 是，(a-1) 是 4 的倍数。

增量 →

如果 c > 0，我们可以通过以下方式实现全周期 

1- m = $2^{b}$ → 更快的计算机运算,

2- 设置 (a-1) 作为 4 的倍数,

3- c 应该是奇数值,

4- 设置 b 尽可能高。例如，在 32 位计算机中 b=31。

如果 c = 0，则不可能实现全周期。在这种情况下，可以实现的最大随机变量数量可以通过以下方式实现 

1- 一个最大周期生成器，其中 λ = m − 1，是一个其中 a 是模 m 的一个本原元素的生成器，如果 m 是素数。

                           i. a mod m 6= 0
                           ii. a(m−1)/q modm 6= 1 , for each prime q of (m-1)

2- 鉴于前面的评论，m 通常设置为小于 2b 的最大素数。最常用的模数是梅森素数 $2^{31}-1$。

最大周期 → m = 素数，a = 模 m 的本原元素

生成的数字中的结构

生成的随机数背后的理念是这些数字应该真正随机。这意味着这些数字应该看起来在分布上相互独立；也就是说，序列相关性应该很小。一个序列的结构有多糟糕（也就是说，这种情况导致输出看起来有多不随机）取决于格的结构。

考虑一个生成器，其中m = 31，a = 3，并从$x_{0}$=19 开始。绘制连续的数对。

                               (27, 19), (19, 26), (26, 16)...

从图 1.2 可以很容易地看出，连续的随机数对只位于三条线上。生成的数字似乎并不随机。它们似乎存在相关性。从视觉角度来看，我们可以得出结论，具有少量行的生成器不能很好地覆盖空间，并且具有较差的格点结构。

MacLaren 和 Marsaglia（1965）建议使用另一个生成器来排列原始生成器的子序列，从而对线性同余随机数生成器的输出流进行洗牌。

通过这种方式，可以增加周期，并且输出的洗牌还可以破坏不好的格点结构。

均匀偏差的 Bays-Durham 洗牌

Bays 和 Durham 建议使用单个生成器填充长度为 k 的表格，然后使用单个流从表格中选择一个数字并补充表格。在将表格 T 初始化为包含$x_{1},x_{2},...,x_{k},$ 后，设置 i = k+1 并生成$x_{i}$ 用作表格的索引。然后使用$x_{i+1}$ 更新表格。

例如，使用图 1.3 中的生成器，它产生了序列

             27, 19, 26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, 15,
                           14, 11, 2, 6, 18, 23, 7, 21, 1, 3, 9,

我们选择 k = 8，并将表格初始化为

                                 27, 19, 26, 16, 17, 20, 29, 25.

然后，我们使用下一个数字 13 作为输出流中的第一个值，并作为表格的随机索引。如果我们将索引形成为 13 mod 8 + 1，我们将得到第六个表格值 20，作为输出流中的第二个数字。我们生成原始流中的下一个数字 8，并将其放入表格中，因此我们现在有表格

                                 27, 19, 26, 16, 17, 8, 29, 25.

现在，我们使用 20 作为表格的索引，并得到第五个表格值 17，作为输出流中的第三个数字。通过继续以这种方式生成 10,000 个偏差并绘制连续的数对，我们得到图 1.6。

Tausworthe 生成器

Tausworthe（1965）引入了一种基于 0 和 1 序列的生成器，该序列由以下形式的递归生成

$b_{i}\equiv (a_{p}b_{i-p}+a_{p-1}b_{i-p+1}+...+a_{1}b_{i-1}){\textit {mod}}2$

其中所有变量都取 0 或 1 的值。

为了计算效率，方程式中大多数 a 设置为零。然后我们得到，

                                $b_{i}\equiv (b_{i-p}+b_{i-p+q}){\textit {mod}}2$

在该递归被评估足够多次后，例如l，a 的l 元组被解释为 2 进制数。这被称为 a 序列的l 位抽取。

例如，取一个模 2 的原始三项式，

                                         x4 + x + 1,

并从位序列开始

                                         1, 0, 1, 0.

对于这个多项式，p = 4，q = 3 在递归中。操作生成器，我们得到

                          1, 1, 0, 0,1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0,

此时序列重复。4 位抽取产生数字

                                        12, 8, 15, 5, … 

与线性同余生成器一样，c 的不同值甚至 a 的起始值都可能产生好或坏的生成器。

拟合优度检验

在本部分，我将向您介绍基本的拟合优度检验，通过这些检验我们可以评估使用上述方法创建的随机数序列。

卡方拟合优度检验

            $\chi ^{2}=\sum _{i=1}^{k}{\frac {(o_{i}-e_{i})^{2}}{e_{i}}}$

→ 零假设：随机变量具有均匀 (0,1) 分布

→ 计算每个 10 个区间中观测值的个数

                      (0, 0.1], (0.1, 0.2], ..., (0.9, 1.0)

→ 将这些计数与预期数字进行比较。

→ 如果观测到的数字与预期数字显着不同，我们有理由拒绝零假设。

Kolmogorov-Smirnov 检验

此检验将经验累积分布函数 (c.d.f) ${\hat {F}}(.)$ 与理论 c.d.f F(.) 进行比较。

→ H0：F(x) = x，0 _ x < 1

→ 对观测结果进行排序，以便$R^{(1)}\leq R^{(2)}...\leq R^{n}$

${\hat {F}}(x)={\frac {i}{n}}$ ，并且 $R^{(n+1)}\equiv 1$

→ 其中 $R^{(0)}\equiv 0$ **并且** $R^{(n+1)}\equiv 1$.

→ 检验统计量衡量了这两个之间最大差异的大小

$D_{n}=max_{0\leq x<1}$ $\left|{\hat {F}}(x)-F(x)\right|$

线性依赖性检验

→ 测试序列中数字之间依赖关系的一种方法是将这种检查限制在相隔 k 个数字的观察结果之间的线性依赖关系。

→ 给定 n 个随机数的实现 $R_{0},R_{1},\ldots ,R_{n}$，滞后 k 的样本协方差为

$C_{k}=(n-k)^{-1}\sum _{i=1}^{n-k}(R_{i}-{\frac {1}{2}})(R_{i+k}-{\frac {1}{2}}).$

→ 在随机性下 $E[C_{k}]=0$.