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

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

计算机模拟需要大量随机输入。伪随机数由确定的递推产生,同一种子和参数会产生同一序列;它们通过统计性质模拟随机,而不是因此成为相互独立的真正随机变量。本节讨论教材中的线性同余方法,目标是理解模运算、周期及参数选择的影响。

线性同余递推为

其中 ,教材取 、、。 是模数, 是乘数, 是增量, 是种子;前三者固定,种子确定一条具体轨道。

应修正输出范围的说法:一般 可以为0,所以 落在 的有限网格上,并不自动严格位于 ,也不自动服从连续均匀分布。只有采用排除零状态的相应参数与种子,才会得到严格正的输出。不能因除以 就断言已获得满足所有应用要求的均匀随机样本。

状态最多有 个,确定的更新规则使序列最终进入周期;在循环之前还可能有非周期的前段。周期是进入循环后最小的正重复长度,不是单纯观察几个相似数就能判定。

取 ,依次产生 ,周期4;只把 改成5,得到 ,周期8,且其中明确出现0。这也直接说明一般输出不能声称全部在开区间内。周期更长通常有利,但长周期不等于不存在相关性,更不等于密码安全。

若 ,下一步直接成为固定的 ;若 ,则按模 进行等差步进。这些情形容易暴露简单规律。参数选择还应检查分布及连续输出之间的相关性,而不只计算一个周期数字。

取 ,得乘同余法 。零种子会永久停在0,必须排除。教材给出的经典参数为 ,非零种子下周期为 ;“经典参数”不应被解释为对任何场景都最合适。

从 开始,前八个状态依次为16807、282475249、1622650073、984943658、1144108930、470211272、101027544、1457850878。除以 后,保留9位小数依次约为0.000007826、0.131537788、0.755605322、0.458650132、0.532767237、0.218959186、0.047044616、0.678864717。每一步先做精确整数模运算,再进行浮点换算;不能把已舍入的小数反复代回整数递推。

该发生器适合用来学习确定性递推与周期分析;可预测的线性同余序列不能用作RSA等密码系统的秘密随机来源。这里的限制来自算法结构,不能靠简单更换种子就消除。