伪均匀随机数的计算机检验

伪均匀随机数的计算机检验伪均匀随机数的计算机检验 摘要摘要 现代社会中 计算机能力的提高使得随机数发生器在众多领域中有了较为广泛的应 用 如蒙特卡罗方法 统计抽样技术和密码学等 同时关于随机数发生器也产生了很多 的理论和方法 本文将简单介绍一些常见的伪均匀随机数发生器 线性同余发生器 LCG 方法 和反馈位移寄存器法 FSR 方法 然后对伪均匀随机数序列进行统计检验 主要 检验方法有参数检验 包括均值 方差或各阶距 均匀性检验 包括卡方 柯氏和序列 检验 独立性检验 包括相关系数 列联表和游程检验 最后 本文将利用 Matlab 生 成一列随机数 并运用 SPSS 统计软件对此列随机数的统计特性择其适合的方法进行检验 关键词 伪随机数 随机数发生器 统计检验 SPSS 统计分析 Abstract In modern society the improvement of computer capabilities make random number generator widely used in many areas such as the Monte Carlo method statistical sampling techniques and cryptography At the same time there are a lot of theories and methods on the random number generator I will introduce some of the common random number generators briefly in this article linear congruential generator LCG method and feedback shift register method FSR method Then I will do statistical tests with the sequence of random numbers Main methods are parameter test involving the mean variance or the order from the test of homogeneity involving Chi square Coriolis and sequence test test for independence involving the correlation coefficient contingency table and the runs test Finally this paper will use the Matlab generate a sequence of random numbers use SPSS and select the appropriate test methods to test statistical properties of the sequence of random numbers Key words random number random number generator statistical test SPSS statistical analysis 目录 摘要 I Abstract II 一 引言 1 1 基本概念和定理 1 2 伪随机数 2 二 产生随机数的一般方法 3 2 1 取中法 3 2 1 1 平方取中法 3 2 1 2 乘积取中法 3 2 2 同余发生器 3 2 2 1 混合同余法 4 2 2 2 乘同余法 4 2 2 3 加同余法 4 2 3 反馈位移寄存器法 4 三 伪均匀随机数的统计检验 6 3 1 检验步骤 6 3 2 检验统计量 6 3 3 统计检验方法 7 3 3 1 参数检验 7 3 3 2 均匀性检验 8 3 3 3 独立性检验 10 3 3 4 其他经验检验 12 四 实例分析 13 4 1 数据产生及录入 13 4 2 参数检验 单样本 t 检验 13 4 3 均匀性检验 卡方检验 14 4 4 独立性检验 16 4 5 本章小结 18 五 结论 19 参考文献 20 附录 21 一 引言 在科学研究和工程设计中广泛应用到计算机模拟方法 从而常常需要产生 大量的具有特定统计性质的随机数 这种随机数通常是由计算机以某种数学方 法产生 他们实质上是完全确定的 但可以满足一定的统计特征 故也称为伪 随机数 而如何产生达到统计要求的随机数 则有不同的方法 硬件方法和软 件方法 硬件方法可以在计算机上附上一个硬件设备或者采用移位寄存器来产 生伪随机数 软件方法一般都采用数学公式法 至今关于随机数发生器有很多的理论和方法 其中除了传统的Fibonacci法 平方取中法 线性同余法 位移寄存器法和组合方法外 最近还有非线性同余 法 取小数法 进位加和错位减法 广义反馈位移寄存器法等等 尽管这个领 域己经有很多的理论研究 但是仍存在很多的实际问题 甚至最近提出的随机 数发生器也有一些缺点 近年来在计算机中 比较广泛使用的方法就是同余法 而在高级程序设计 语言中常采用线性同余法 每次生成的伪随机数需要满足独立的条件及给定分 布函数的要求 但高级程序设计语言中提供的库函数产生的伪随机数都是满足 一定条件的均匀分布随机数 且在同一次程序运行中 每次产生的伪随机数是 完全相同的 通过在微机上对用乘同余法和混合同余法产生的随机数进行大量的试验 发现通过适当选择算法中的各常量 用这两种方法产生的随机数 其分布特性 一般容易通过统计捡验 用随机模拟方法解决实际问题时 首先要清楚随机数的产生方法 或者说 是随机变量的抽样方法 1 基本概念和定理 定义 1 设随机变量 则称随机变量随机抽样序列为分布 xF i 的随机数 xF 若 则称来自的随机抽样序列为正态分布随机数 N 2 21 若服从指数分布 则称为指数分布的随机数 若区间均匀 21 ba 分布 则称为区间上的均匀分布随机数 21 ba 定理 1 设是连续且严格单调上升的分布函数 它的反函数存在 且记 xF 为即 1 xF xxFF 1 若随机变量的分布函数为 则 xFF 1 0 U 若随机变量 则的分布函数为 R 1 0 U 1 RF xF 推论 已知 设是一个分布函数 且反函数存在 则 xG xF 1 xF 1 xFGF 定理 2 设服从二点分布相互独立 且 i X 21 i 0 1 0 ii XPXP 令 2 1 X 2 2 X 2 k X 用二进制表示 k XXX 21 0 则 1 0 U 定义 2 准均匀分布 设离散随机变量的概率密度为 kk i PP 2 1 12 1 12210 k i 则称为准均匀分布 且 12 12 12 1 2 1 k k VarE 2 伪随机数 显然 用计算机只能产生准均匀随机分布数 但是当很大时 和均匀k 随机变量的统计性质差异很小 可以把准均匀随机数做伪均匀随机数 二 产生随机数的一般方法二 产生随机数的一般方法 2 1 取中法 2 1 1 平方取中法 平方取中法又称自然取中法 首先由 Von Neuman 于 1940 年提出 此法开 始取一个 2 位十进制整数作为种子 将其平方得到的一个 4 位数 不足 4ss 位的高位补 0 然后取该 4 位中间 2 位作为下一种子数 并对此数进行sss 规格化 化成小于 1 的 2 位的实数值 依上述过程类推便得到一维随机数列 s 其一般的递推公式是 的中间 2 位数字 2 1 nn ww s 按此公式依次得到一列数据 然后把这列数据的每一个元素都除以 可 2 10 s 得到 0 1 区间上均匀分布的随机数列 n uuu 21 2 1 2 乘积取中法 乘积取中法是通过平方取中法改进得到的一种产生随机数的方法 其一般 递推公式为 s n n s s nn n x R xx x 2 1 1 2 1 1 10 10 mod 10 式中 第 n 1 个十进制的正整数 1 n x 第 n 1 个伪随机数 1 n R 此方法虽然简单 但均匀性不好 且序列很快趋于零 其长度难以确定 故目前已很少使用 2 2 同余发生器 该发生方法是目前应用最广泛的方法之一 通常我们把它简称为 LCG Linear Congruence Generator 方法 它是由 Lehmer 在 1951 年提出的 此方法是利用数论中的同余运算来产生随机数的 故称之为同余发生器 LCG 方法的一般递推公式为 21 mod 1 n M x r Mcaxx n n nn 其中初值为 为模数 为乘子 乘数 为增量 加数 且 0 xMac n xM 均为非负整数 显然由上式得到的 1 2 满足 从ac n xnMxn 0 而 当然 递推公式中的参数 的选择十分关键 否则 10 n rac 0 xM 进行了一定次数的迭代之后会出现短周期的重复现象 因而我们应慎重选取 当参数 选择不同时 对应的方法会有稍稍的不同 具体的讨论如下 ac 2 2 1 混合同余法 当上面的式中参数 0 1 时 则称之为混合同余法 或者称为混 c a 合式 LCG 2 2 2 乘同余法 当式中 0 时的 LCG 方法称为乘同余法 或是积式发生器 具体表示 c 式如下 初值为 21 mod 1 n M x r Maxx n n nn 0 x 2 2 3加同余法 当式中时 称之为加同余法 具体表示式为 10 ac 初值为 21 mod 1 n M x r Mcxx n n nn 0 x 虽说此方法可于以达到最大的周期 而且计算机实现比较方便 但是和M 上面的混合同余法 乘同余法对比 验证得出 该方法得到的随机数列性质相 对较差 所以 一般常用的是混合同余法和乘同余法 2 3 反馈位移寄存器法 随着 LCG 方法的应用 人们渐渐发现其缺陷并开始寻找新的随机数发生 方法 因此 通过大家的努力 在 1965 年以 Tausworthe 的相关论文为基础 出现了几种比较好的随机数发生器 它的主要原理是通过对寄存器进行位移 直接在存储单元中形成随机数 我们称这种方法为反馈位移寄存器法 Feedback Shift Register Methods 简称之为 FSR 方法 其线性递推公式为 2 mod 1111 xpippxpi xcxcxcx 210 i 其中为给定正整数 或为给定的常数 p1 p c0 i c1 121 p 1971 年 Toot hill Robinson 和 Adams 又给出了 FSR 的另一递推公式 1 mod 1 1 0 mn ii xxxxx x 210 i 其中是次数小于的且系数为 0 或 1 的多项式 而且 0 为正整数 i xnnm 三 伪均匀随机数的统计检验 伪均匀随机数的有效性在于它们与真正的区间上均匀随机数的性质是 1 0 否有显著差异 这是一个重要的问题 因为二者若有显著差异 这时以这种随 机数发生器产生的随机数为基础的随机变量所得到的样本就不能够反映该随机 变量的性质 从而无法得到可靠的随机模拟结果 因此随机数发生器的检验是 一项很重要的工作 一般情况下 会有两种不同的检验方法 经验检验和理论检验 经验检验 是一种统计检验 它是以发生器产生的均匀随机数序列为基础的 根据 i r 区间上均匀总体简单随机样本的性质 如特征向量 均匀性 随机性 1 0 i u 等 研究我们产生的随机序列的相应性质 进行比较 借鉴 视其差异是否 i r 显著决定取舍 理论检验从统计意义上说并不是一种检验 它用一种综合的方 法来评估发生器的参数值 而根本不必产生任何随机数序列 即它只是一种 i r 理论上的研究 由于理论检验方法需要专门学科的知识 数学上又相当难 我 们这里只讨论经验检验的几种方法 通常称为统计检验 3 1 检验步骤 首先假设总体具有某种统计特性 然后由样本值检验这个假设是否可信 此法又称假设检验 具体步骤如下 提出假设 总体分布为 0 H 10 U 选取适当的统计量 其中是样本 并求出在成 1n xxTT n xx 1 T 0 H 立时的分布 给定显著水平 确定检验方法 即给出否定域 使得 WW WxxTP n 1 由观测值 样本值 计算值 T 做统计判断 当时否定 当时 相容 T W 0 HWT 0 H 3 2 检验统计量 根据中心极限定理得到近似正态分布统计量 设是相互独立同分布 且 n21 xF E i 2 i Var 记 则以为极限分布 n i i n 1 1 n U 1 0 N 统计量 2 将总体的简单子样按一定规则分为互不相交的个组 记 n21 m 第 组的观测频数为 若随机变量属于第 组的概率为 记i i n 21 mi i i p 理论频数 由构造统计量渐进服从 其中 ii np ii n m i i ii n V 1 2 2 f 是附加在概率分布上独立约束条件的个数 即确定概率时llmf 1 i p i p 利用样本估计总体参数的个数 当时 30 f 1 0 122NfVU 3 3 统计检验方法 3 3 1 参数检验 均匀随机数的参数检验是检验由某个发生器产生的随机数序列的均值 i r 方差和各阶矩阵等与均匀分布的理论值是否有显著差异 若随机变量 则若 1 0 UR 3 1 12 1 2 1 2 RERVarRE 是均匀总体的简单随机样本 即相互独立同 n RRR 21 R n RRR 21 分布 记 1 0 U n i i R n R 1 1 n i i R n R 1 2 2 1 2 1 2 2 1 1 n i i R n s 则有 n RVarRE 12 1 2 1 n RVarRE 45 4 3 1 22 n sVarsE 180 1 12 1 22 设是某个发生器产生的随机数 首先对特征量作统计检验 在 n rrr 21 是均匀总体的简单随机样本的假设下 统计量 i r 2 1 12 1 rn rVar rEr u 渐进服从 3 1 2 45 3 1 2 2 2 2 r n rVar r u 12 1 180 12 1 2 2 2 3 sn sVar s u 给定显著性水平后 查标准正态数值表得 1 0 N 否定域 由随机数序 i uP 1 0 Nui 3 2 1 iuW ii 列计算的值 若 则认为产生的随机数序列的特征向量与均 i r 321 uuu i u 匀总体的特征量没有显著差异 否则 由于的特征量与均匀总体的特征量 i r 有显著差异 故不能认为是均匀总体的简单样本 i r 我们用 SPSS 做参数检验时用单样本 t 检验 单样本 t 检验的目的是利用来 自某总体的样本数据 推断该样本的均值是否与指定的检验值之间存在显著差 异 它是对总体均值的假设检验 单样本 t 检验的原假设为 总体均值与检 0 H 验值之间不存在显著差异 表述为 为总体均值 为检验值 0 H 0 0 对单个总体均值的推断是建立在单个样本均值基础上的 也就是希望利用样本 均值去估计总体均值 构造 t 检验统计量为 其中为样本方差 n S X t 2 2 S 式中 t 统计量服从 n 1 个自由度的 t 分布 SPSS 将自动计算出 t 统计量的观 测值和对应的概率 P 值 给定显著性水平 与检验统计量的概率 P 值比较 若概率 P 值小于显著性水平 则应拒绝原假设 认为总体均值与检验值之间 存在显著差异 反之 则不应拒绝原假设 认为总体均值与检验值之间无显著 差异 3 3 2 均匀性检验 随机数的均匀检验又称为频率检验 它用来检验由某个发生器产生的随机 数序列是否均匀的分布在区间上 也就是检验经验频率与理论频率的 i r 1 0 差异是否显著 检验 2 卡方检验基本思想的理论依据是 如果从一个随机变量中随机抽取若干R 个观察样本 这些观察样本落在的个互不相交的子集中的观察频数服从一Rm 个多项分布 这个多项分布在趋向于无穷时近似服从卡方分布 m 设使待检验的一组随机数 假设 为均匀总体的简 n rrr 21 0 H n rrr 21 单样本 将区间分为m个小区间 以表示第 个小区间 1 0 1 m i m i 2 1 mi i 设落入第 个小区间的数目为 j r 2 1 nj i i n 2 1 mi 根据均匀性假设 落入每个小区间的概率为 第 个小区间的理论频 j r m 1 i 数 统计量渐进服从 2 1 mi m n i m i i ii n V 1 2 2 1 m n n n m m i i 给定显著性水平 查分布表得临界值后 即可对经验频率与 1 2 m 2 理论频率的差异作显著性检验 若的概率 P 值小于显著性水平 则应拒 2 绝原假设 认为样本来自的总体分布与期望分布或某一理论分布存在显著差异 反之 则不能拒绝原假设 可以认为样本来自的总体分布与期望分布或某一理 论分布不存在显著差异 K S 检验 柯氏检验 K S 柯尔莫哥洛夫 斯米尔诺夫 检验的原假设是 样本来自的总体与指 定的理论分布无显著差异 其基本思路是 首先 在原假设成立的前提下 计 算各样本观测值在理论分布中出现的累计概率值 其次 计算各样本观测 xF 值的实际累计概率值 计算实际累计概率值与理论累计概率值的差 xS xD 最后 计算差值序列中最大绝对差值 即 统计量也 ii xFxSD maxD 称为 K S 统计量 在小样本下 原假设成立时 统计量服从柯氏分布 在大样本下 原假D 设成立时 近似服从分布 当小于 0 时 为 0 当大于 0Dn xKD xKD 时 xK j xj 22 2exp1 若统计量的概率 P 值小于显著性水平 则应拒绝原假设 认为样本来自的D 总体分布与给定的分布存在显著差异 反之 则不能拒绝原假设 可以认为样 本来自的总体分布与给定的分布不存在显著差异 序列检验 Serial test 序列检验实际上是用于多维分布的均匀性检验 它也间接地检验序列的独 立性 已知随机数序列 将容量为的随机数一次配对为 i r 221 ni n2 212432211nnn rrvrrvrrv 如果是均匀随机数序列 那么他们应该构成平面上正方形内的二维均匀随 i r 机向量的样本 将单位正方形分成个等面积的小正方形 表示 2 k ij n 落入第个小正方形的频数 理论频数 则检验统 2 1 ntvi ji 2 k n ij 计量在为均匀分布的独立抽样序列成历史渐进的服 2 2 11 2 k n n n k V k i k j ij i r 从 1 22 k 以上二维的序列检验可以推广到三维 四维直至一般的维 即对依d i r 次用不相交的阶组合 d tuptesd 211d rrrv 2212ddd rrrv 2 1 1 1 kddkdkk rrrv 它们应该是在单位维超立方体中均匀分布的独立随机样本 把d d 1 0 区间分为个相等的小区间 相应地把单位维超立方体分成个小立方 1 0 md d m 体 用表示落入第个超立方体的个数 统计量 d jjj n 21 k v 21d jjj 渐进服从 这种维均匀分布 2 11 21 1 d m j jjj m j d m n n n m V d d 1 2 nmd d 的检验 序列检验 间接地检验了的独立性 i r 3 3 3 独立性检验 独立性检验主要检验随机数序列之间的统计相关性是否显著 它 n rrr 21 通常包括以下几种检验方法 相关系数检验 两个随机变量的相关系数反映它们之间线性相关程度 若两个随机变量独 立 则它们的相关系数必为零 反之不一定 故可以利用相关系数检验随机数 的独立性 设是待检验的一组随机数 原假设 相关系数 考虑样 n rrr 21 0 H0 本的阶自相关系数 j n i i ji jn i i rr n rrrr jn j 1 2 1 1 1 21 mj 相关系数范围为 当时 表示变量的线性相关性较弱 11 3 0 SPSS 将自动计算自相关系数及标准误差 概率 P 值 若检验统计量的概率 P 值小于给定的显著性水平 应拒绝原假设 认为变量存在线性相关性 若 相反 则不应拒绝原假设 认为变量间不存在线性相关性 当充分大 且成立时 渐进服从分布jn 0 jnjuj 1 0 N 利用统计量可以进行相关 20 10 2 1 mmj 在实际检验中 常取 j u 性检验 相关系数检验 另外 的阶自相关系数还可以定义为 n rrr 21 j j n i ki j s rrrr n 1 2 1 21 mj 其中 njikmod n i i rr n s 1 22 1 记 则 n i kij rr n C 1 1 12 4 1 2 2 j j j C s rC 可以证明 这时检验假设可以用 n CVarCE jj 144 13 4 1 0 0 J EH 检验假设来代替 统计检验量为 利用统计 4 1 0 j CEH n C T j 144 13 4 1 1 0 N 量可进行相关性检验 T 列联表检验 在平面上 将单位正方形分成个相等的小正方形 把个随机数 2 mn 按先后顺序两两分组 例如取 n rrr 21 11e rr 22e rr nen rr 11 rr en en rr 其中 为大于 1 的正数 记这些数对落入第个小正方形内的数目为e ji 令 用表示落入第个小正方形 1 mjinij m j iji nn 1 m i ijj nn 1 ij p ji 内的概率 当独立性假设成立时 其中 表示 jiij ppp 2 1 mji i p 随机数落入第 列的概率 表示落入第行的概率 用最大似然法可得 i j p j n n p i i n n p j j 检验统计量 渐进服从 1 11 2 11 2 11 m i m j ji ij m i m jji j i ij m i m j ji jiij nn n n n nn n n n n nn ppn ppnn V 其中 是用样本来估计的个数 故 所以 1 22 lm l ji pp 和 22 ml 1 22 mV 3 3 4 其他经验检验 如最值检验 最值检验主要是检验伪均匀随机数序列的最大值和最小值 四 实例分析四 实例分析 本文利用 Matlab 中的 Rand 函数来产生随机数序列并运用作者学过的 SPSS 统计软件对随机数序列做统计检验 4 1 数据产生及录入 打开 Matlab 在工作窗口输入指令 shuju 1 rand 1000 1 0 点击 Enter 即得到 1000 个数据 而由于 SPSS 无法直接读取 MATLAB data file 格式的数据 因此我们先将产生的随机数导入一个电子表格中 命名为 shuju 这样 SPSS 就可以直接读取了 步骤为 选择菜单 File Open Data 选择数据文件的类型 xls 并输入文件名 shuju 出现下图 我们默认将 Excel 工作表中的全部数据读入 直接点击 ok 得到界面如下 4 2 参数检验 单样本 t 检验 单样本 t 检验在本例中的原假设可以表述为 0 5 操作步骤 选择 0 H 菜单 Analyze Compare Means One samples T Test 出现如下 图所示的窗口 将数据选择到 Test Variable s 并将 Test Value 中的 0 改为 0 5 点击 ok 得到以下结果 由第一张表可知 Matlab 产生的 1000 个 0 1 之间的随机数的均值是 0 51723 标准差是 0 28536 均值标准误差是 0 09024 从第二张表我们看 到这组数的 t 统计量的观测值是 1 909 自由度为 999 t 统计量的双尾概率 P 值是 0 057 显然 P 0 05 则不应拒绝原假设 即认为总体均值与检验 值之间无显著差异 样本均值与检验值的差是 0 01723 它除以均值标准误差 0 09024 后得到 t 统计量的观测值 最后两列是总体均值与原假设值差的 95 的 置信区间为 0 00048 0 03494 由此计算出总体均值的 95 的置信区间 为 0 49952 0 53494 这表示我们有 95 的把握认为总体均值在 0 49952 0 53494 之间 0 5 包含在这个区间内 这也证明了总体均值与检验 值之间无显著差异 4 3 均匀性检验 卡方检验 本例中卡方检验的原假设可以表述为 样本数据的分布与 0 1 上的 0 H 均匀分布无显著差异 但在做卡方检验之前 需要将数据分组 我们将这 1000 个数据分为十组 即各组为 0 0 10000 0 10001 0 20000 0 20001 0 30000 0 90001 1 操作步骤如下 选择菜单 Tansform Recode Into Different Variables 选择分组变量到 Numeric Variable Output 框中 在 Output Variable 框中的 Name 后输入存放分组结果的变量名 并按 change 确认 也可在 Lable 后输入相应的变量名标签 再按 Old and New values 按钮进行分组区间的定义 如下图 然后进行卡方检验 操作步骤如下 选择菜单 Anal