一种基于MC法的随机序列生成及检验

【摘要】  目的：基于MC法生成符合预期概率分布的随机序列，以便应用在以后的仿真系统中。方法: 应用线性同余法在visual studio环境中建立随机模型模拟随机序列生成。并采用χ2拟合优度检验法和自相关检验法检验生成的随机序列的均匀性、独立性。结果：100组随机序列的检验结果表明，独立性检验通过率为96%，均匀性检验通过率达到94%以上。结论：方法生成的随机序列满足随机性要求，以此定义的类模块可应用于今后的仿真实验中。

【关键词】  MC; 线性同余法; 均匀性检验; 独立性检验

　　Abstract  AIM: To generate random sequences that can fit the anticipated probability distribution based on the thinking of MC, METHODS: We establish a method in the IDE of visual studio by the way of Linear Congruential Method to generate random sequences.We also test the  homogeneity and independence by the chi-sqare Goodness of Fit Test and Self-correlation Test. RESULTS: After check of 100 groups of random sequences,the result showed that the random sequence satisfied the demand of homogeneity and independence distribution(the thruput over 96% and 94%). CONCLUSION:The sequences can fit the desire of randomness and the class module defined can be used in further trial.

    Key words   Monte-Carlo;  Linear Congruential Method; test of homogeneity; test of independence

    1  引言

    蒙特卡罗(Monte-Carlo,MC)法［1］是利用机模拟随机现象产生的随机序列来进行近似计算的方法。在医学研究中主要应用于组织学和病随机视野的采样、基因序列分析和数据挖掘、流行病调查和医学统计等领域。当实验数据难以获取或研究基础理论和方法时, 采用计算机仿真模拟研究中的随机模型是一种简单、的方法。为了满足实际应用中仿真系统的要求，我们经常需要采用MC法来产生预期单一概率分布的随机序列［2~4］。基于MC法的原理，本研究应用visual studio建立了随机模型,并将其定义为类模块，可直接应用于今后的仿真系统中。

　　2  材料及方法

　　2.1  均匀分布随机序列产生

    均匀随机数是产生其它随机数的基础，许多其它分布如正态分布、指数分布等的随机数都可以用均匀随机数经过变换得到，因此产生大量的相互独立的均匀随机数至关重要。为得到期望的均匀分布的随机序列，我们在visual studio集成开发环境中应用线性同余法(Linear Congruential Method)生成随机序列［5］，其一般递推公式为：xn=(αxn-1+c）(modM)rn=xn/M　x0(1)

    在（1）式中，M为模数，a为乘子，c为增量，且M,a,c均为非负整数。由初始值x0和递推公式式xn-1+c(modM) 产生的序列xn(n=1, 2,…)就是所要得到的同余序列（本式中xn 和xn-1呈线性关系，称线性同余序列），满足0≤ xn≤M,从而rn∈［0,1］。应用这个思路，在visual studio中以c++编程实现,以下是线性同余法生成随机序列的伪代码：Random（n，m，seed，a，b）{r0 = seed；for i = 1；i<=n；i++）  　ri =(a*ri-1 + b） mod m}

　　随机序列中的每个变量的生成调用标准库〈cstdlib〉（被包含于〈iostream〉中）提供的随机函数srand（seed）来实现，并应用时间函数来确保选用不同的种子参数。其部分伪码如下：void main() {int count=0;for (int i=0;i<10;i++){srand((unsigned)time(NULL));  　　count++;}

　　2.2  试验方法

    我们应用Microsoft Visual C++6在微型计算机和Microsft windows环境下编制了win32程序,数据库系统采用Microsoft Access 2000系统。在计算机上模拟获得了随机序列，再将数据保存入数据库。

　　2.3  数据统计分析

    用SPSS13.0和Originlab origin 7.5对所得数据进行了均匀性和独立性检验。均匀性是指随机数在某个区间出现的概率与在其他区间出现的概率无显著性差异。我们采用χ2 拟合优度检验法对［0,1］区间的随机序列进行了均匀性检验［6~7］，并用Pearson  χ2 检验法检验了区间大小不同的组别间的差异性。独立性是指某个随机数与其出现在其它区间内的概率无关。独立性检验我们采用自相关系数检验。

　　3  结果

　　3.1  均匀性检验

    我们将生成的随机序列极差区间分成k个不相交的等长小区间，n个观察值中落在第j区间的频数为f0j。假设观察值来自均匀分布的总体，那么落在每一小区间的理论频率fej均相等，为n/k。因此当n充分大时，随机数序列渐近服从χ2(k-1)分布。根据n个观察值计算出统计量χ2=∑（f0j-fej)2 /fej，并从χ2 分布表中确定临界值χ2a,k-1。当 χ2>χ2a,k-1时则拒绝原假设，否则接受原假设即认为随机序列总体分布是均匀的。

    表1是一次试验中容量为100、500、1000的3个随机序列的实测频数分布情况，结果表明随机序列来自均匀分布的总体。表1  100个随机数频数分布表（略）注： χ2 0.05,9=15.5;  χ2 (1)=6.0<χ2 0.05,9,P>0.05;  χ2 (2) =5.52< χ2 0.05,9, P>0.05;  χ2 (3) =10.88< χ2 0.05,9,P>0.05。

    按照上述步骤，我们进行了100次重复实验，对每次产生的结果分别进行了均匀性检验。为了判断在选取不同区间大小时频数分布的均匀性，我们依据区间数k将随机序列的值域划分为不同的等长小区间，以分别选取区间数为k=50, k=75, k=100，并用Pearson χ2   检验不同组别均匀性检验通过率的差别。结果表明，随机序列组数为k=50, k=75, k=100时的均匀性检验通过率分别为：94%，97%，98%; χ2 < χ2 0.05,2=5.99, P>0.05。选取不同区间大小之间的序列均匀性差异无统计学意义(P>0.05)。见表2。
表2  100个随机数序列的均匀性检验比较（略）注：* P>0.05，不同区间大小均匀性检验通过率差异无统计学意义。
 
　　3.2  独立性检验

    随机数序列中两数之间的相关性可用自相关系数表示［8］。j阶自相关系数的统计量为ρj=(1   n-jΣxixi+j-x2) /s2。式中x和s分别为样本均值和方差。在原假设ρi=0条件下,统计量uj=ρjn-j 渐近地服从标准正态分布N(0,1)。对拟检验的随机数序列分别j=1,2,..,n时的统计量uj。若取显著水平α=0.05，则当|uj|>1.96时拒绝j阶自相关系数ρi=0的假设，否则接受这一假设，即认为随机数xi与xi+j之间不相关。我们取前10阶相关系数(j=1,2…10),结果见表3，自相关系数与零均无显著性差异，在显著性水平α=0.05下接受随机数不相关的假设。表3  100个随机序列的自相关检验表（略）注：P<0.05，不同阶数自相关系数与0差异无统计学意义。

    按照上述步骤，我们进行了100次重复实验，我们据以上检验原理对每次实验产生的一组随机数序列进行独立性检验。其结果见图2所示，在100次重复实验中独立性检验通过率为96%。

　　4  讨论

    蒙特卡罗法是对一种思想的泛称。它是一种统计试验方法,研究在计算机上产生具有各种概率分布的随机序列,并通过构造随机模型,使得某一随机量的数学期望等于问题中要求的解,其实质是利用服从某种分布的随机序列来模拟现实系统中可能出现的随机现象。

    随机数表由于具有周期性、排序确定性和容量所限，在大样本的计算机仿真医学实验中有时有一定的局限性。虽然可以用物理方法来产生随机序列，但不能重复，使用不便。我们采用由数学递推公式产生，只要方法选择合适，所产生的伪随机序列就能满足均匀性和独立性。产生随机数的方法是先用一定的方法产生均匀分布的随机数，然后通过适当的变换就可以得到符合某一概率模型的随机数。我们在visual studio环境中应用线性同余法生成均匀分布的随机序列，结果表明，在100次重复实验中独立性检验通过率为96%，均匀性检验通过率达到94%以上。

    本检验结果是在Microsoft Visual studio 6.0下取得的,由于种子的选取不同,所以每次运行的结果不可能一致, 但对本研究结论无根本性影响。

【】
  　　1 裴鹿成,王仲奇.蒙特卡罗方法及其应用.北京:海洋出版社,1998.

　　2 金浩宇,周凌宏, 陈光杰,等.一种基于蒙特卡罗模拟的快速剂量计算模型.第四军医大学学报,2006，27(21)：2002~2004.

　　3 黄枫,申洪.基于Intel RNG的真随机数生成器研究.第一军医大学学报,2004,24(9):1091~1095.

　　4 黄枫,申洪.基于CryptoAPI的生物医学真随机数的生成器.第四军医大学学报, 2004,25(19):1819~21.

　　5 陆银根. 用类同余法产生随机数及其检验.数理统计与管理,2002,21(6):50~52.

　　6 Duelli M, Cohn RW. Pseudorandom encoding for real-valued ternary spatial light modulators.Appl Opt， 1999,38(17):3804~3809.

　　7 van Casteren M, Davis MH. Mix, a program for pseudorandomization. Behav Res Methods， 2006,38(4):584~589.

　　8 Bauke H, Mertens S. Random numbers for large-scale distributed Monte Carlo simulations. Phys Rev E Stat Nonlin Soft Matter Phys. 2007,4(1):5~14.