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

定义和用法

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

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

均匀随机数生成

给定一个无限序列 $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. (a-1) 是 4 的倍数，如果 m 是。

增量 →

如果 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 mod8 + 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）分布

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

                      (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$.