本节对应原书 PDF 第 304–307 页。定义、公式、算法及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

13.2.1 产生均匀伪随机数的方法

做 n 次独立重复试验，得到随机变量 X 的 n 个值 x_1,x_2,\cdots,x_n. 把这 n 个数称为随机变量 X 的样本或随机数. 例如，掷一枚硬币，若硬币的正面向上，得到一个 1；若硬币的背面向上，得到一个 0. 掷 n 次，得到 n 个 0,1. 假设硬币是均匀的，则这是参数 \frac{1}{2} 的 0-1 分布的随机数. 更一般地，设正面向上的概率为 p(0<p<1)，则这是参数 p 的 0-1 分布的随机数.

计算机模拟需要大量的随机数. 掷硬币就是一种产生随机数的方法. 随机数可以用专门的物理装置产生，如放射性粒子计数器，电子管随机数发生器等. 这些方法的成本都很高且使用不方便，因此通常是用计算机计算产生随机数. 但是，这样得到的数不是真正的随机数，不过它们具有类似随机数的性质，可以当作随机数使用，把这样的数称作伪随机数. 伪随机数的性能可以用数理统计方法加以检验.

解读：物理装置产生的是真随机数，代价是慢且不可复现；计算机按确定公式算出的数列完全由种子决定，本质上是"可预测"的，所以只能叫伪随机数。它的价值在于统计性质足够像随机数，并且同一种子能重放同一序列，便于调试。

设随机变量 X 的取值范围是 (0,1) 且对任意的 0<a<1，P\{0<X\leqslant a\}=a，则称 X 服从 (0,1) 上的均匀分布，记作 X\sim U(0,1). 直观上，服从 (0,1) 上均匀分布的随机变量等可能地取到 (0,1) 上的每一个值.

可以用 (0,1) 上均匀分布的随机数产生各种随机数. 本小节介绍产生 (0,1) 上均匀分布伪随机数的方法，下一小节介绍如何利用 (0,1) 上均匀分布伪随机数产生各种离散型伪随机数.

最常用的产生 (0,1) 上均匀分布伪随机数的方法是线性同余法. 选择 4 个非负整数：模数 m，乘数 a，常数 c 和种子数 x_0，其中 2\leqslant a<m，0\leqslant c<m，0\leqslant x_0<m，按照下述递推公式产生伪随机数序列

x_n=(ax_{n-1}+c) \bmod m \quad n=1,2,\cdots \tag{13.1}

为了得到 (0,1) 上均匀分布伪随机数，取

u_n=x_n/m \quad n=1,2,\cdots \tag{13.2}

种子数 x_0 在计算时随机给出，其他 3 个参数 m，a 和 c 是固定不变的，它们的取值决定了所产生的伪随机数的质量.

式(13.1)至多能产生 m 个不同的数，因此得到的序列一定会出现循环，即存在正整数 n_0 和 l，使得所有的 n\geqslant n_0 都有 x_{n+l}=x_n. 使得上式成立的最小正整数 l 称作该序列的周期. 例如，取 m=8，a=3，c=1，x_0=2，由公式(13.1)得到 7,6,3,2,7,6,\cdots. 这个序列的周期等于 4. 若保持 m=8，c=1，x_0=2 不变，把 a 改为 a=5，则得到 3,0,1,6,7,4,5,2,3,0,1,\cdots，周期为 8. 显然，伪随机数序列的周期越长越好.

解读：x_n 只由 x_{n-1} 决定，取值又只有 m 种，所以序列迟早回到某个走过的值，此后便原样重复——周期存在是递推式的必然结果，而非参数没选好。参数的作用只是把周期尽量逼近上界 m。

此外，若取 a=0 和 a=1，分别得到序列 c,c,c,\cdots 和 x_0+c，x_0+2c，x_0+3c，\cdots. 这 2 个序列根本无随机性可言，因而总限定 a\geqslant 2. 实际上，采用不同的参数得到的伪随机数序列的随机性是不同的，因此要想得到满意的伪随机数，必须选取一组好的参数 m，a 和 c.

取 c=0，式(13.1)简化为

x_n=ax_{n-1} \bmod m \quad n=1,2,\cdots \tag{13.3}

称作乘同余法. 采用乘同余法时，显然不能取 x_0=0. 取 m=2^{31}-1，a=7^5 的乘同余法是最常用的均匀伪随机数发生器，它的周期是 2^{31}-2. 取种子数 x_0=1，得到伪随机数如下：

x_nu_n
16 8070.000 007 826
282 475 2490.131 537 788
1 622 650 0730.755 605 322
984 943 6580.458 650 131
1 144 108 9300.532 767 237
470 211 2720.218 959 186
101 027 5440.047 044 616
1 457 850 8780.678 864 716
\vdots\vdots

解读：乘同余法取 x_0=0 会得到恒为 0 的死序列，因为 0 乘以任何数仍是 0，这也是它比线性同余法多一条使用禁忌的原因。

13.2.2 产生离散型伪随机数的方法

设随机变量 U\sim U(0,1)，给定 p_1,p_2,\cdots 和 a_1,a_2,\cdots，这里对每一个 k，p_k>0 且 \sum\limits_k p_k=1，而 a_1,a_2,\cdots 都不相同. 对 k=1,2,\cdots，当 \sum\limits_{i=1}^{k-1}p_i<U\leqslant\sum\limits_{i=1}^{k}p_i 时，令 X=a_k，则

P\{X=a_k\}=p_k \quad k=1,2,\cdots

因此，可以利用 (0,1) 上均匀分布伪随机数产生任意给定分布律的离散型伪随机数. 算法如下.

算法 13.1 离散型伪随机数产生算法.

输入：分布律 (a_k,p_k)，k=1,2,\cdots.

输出：伪随机数 x.

  1. 产生一个 (0,1) 上均匀分布伪随机数 u
  2. F\leftarrow p_1，k\leftarrow 1
  3. while u>F do
  4. \quad k\leftarrow k+1，F\leftarrow F+p_k
  5. x\leftarrow a_k

解读：这个算法的实质是把 (0,1) 区间按 p_1,p_2,\cdots 切成首尾相接的小段，随机点 U 落进第 k 段就输出 a_k。落在第 k 段的概率正好是段长 p_k，所以输出分布被精确复现。

下面是几个常用离散型伪随机数的算法.

(1) 离散型均匀分布

设 a_1,a_2,\cdots,a_n 是 n 个不同的数，\{a_1,a_2,\cdots,a_n\} 上均匀分布的分布律为

P\{X=a_k\}=\frac{1}{n} \quad k=1,2,\cdots,n

(0,1) 上均匀分布就是 p=\frac{1}{2} 的 0-1 分布.

算法 13.2 离散型均匀分布伪随机数的产生算法.

输入：n 个不同的数 a_1,a_2,\cdots,a_n.

输出：伪随机数 x.

  1. 产生一个 (0,1) 上均匀分布伪随机数 u
  2. for k\leftarrow 1 to n do
  3. \quad if u\leqslant k/n then x\leftarrow a_k，计算结束

(2) 泊松分布

泊松分布的分布律为

P\{X=k\}=\frac{\lambda^k}{k!}\mathrm{e}^{-\lambda} \quad k=0,1,2,\cdots,\ \lambda>0

有下述递推公式

\begin{cases} p_0=\mathrm{e}^{-\lambda} \\ p_{k+1}=\dfrac{\lambda}{k+1}p_k & k=0,1,2,\cdots \end{cases}

算法 13.3 泊松分布伪随机数的产生算法.

输入：\lambda>0.

输出：伪随机数 x.

  1. 产生一个 (0,1) 上均匀分布伪随机数 u
  2. p\leftarrow \mathrm{e}^{-\lambda}，F\leftarrow p，k\leftarrow 0
  3. while u>F do
  4. \quad k\leftarrow k+1，p\leftarrow \lambda p/k，F\leftarrow F+p
  5. x\leftarrow k

(3) 二项分布

方法一：二项分布的分布律为

p_k=P\{X=k\}=\binom{n}{k}p^kq^{n-k} \quad k=0,1,\cdots,n，\text{其中 } q=1-p，\ 0<p<1

有下述递推公式

\begin{cases} p_0=q^n \\ p_{k+1}=\dfrac{(n-k)p}{(k+1)q}p_k & k=0,1,\cdots,n-1 \end{cases}

算法 13.4 二项分布伪随机数的产生算法Ⅰ.

输入：整数 n\geqslant 2 和 p(0<p<1).

输出：伪随机数 x.

  1. 产生一个 (0,1) 上均匀分布伪随机数 u
  2. c\leftarrow p/(1-p)，t\leftarrow(1-p)^n，F\leftarrow t
  3. for k\leftarrow 0 to n do
  4. \quad if u\leqslant F then x\leftarrow k，计算结束
  5. \quad else t\leftarrow tc(n-k)/(k+1)，F\leftarrow F+t

方法二：在例 12.12 中已经证明，二项分布 B(n,p) 可以表示成 n 个相互独立的参数 p 的 0-1 分布的和. 因此，可用下述算法产生二项分布的伪随机数.

算法 13.5 二项分布伪随机数的产生算法Ⅱ.

输入：整数 n\geqslant 2 和 p(0<p<1).

输出：伪随机数 x.

  1. x\leftarrow 0
  2. for i=1 to n do
  3. \quad 产生一个 (0,1) 上均匀分布伪随机数 u
  4. \quad if u\leqslant p then x\leftarrow x+1

解读：算法 13.4 与 13.5 算的是同一个分布，代价却不同。13.4 只抽一个 u，用递推的累积概率一次定位，O(n) 但常数小；13.5 要抽 n 个 u，思路直接却更贵。前者靠递推公式省下了重复计算组合数的开销。