P mp°(1-P) 1-P 由此方程立即得到关于回返概率P的解析表达式如下: /(1 (8) 计算回返概率的确定性方法就是,用下式 (9) 作为P的近似估计,其中M是一个足够大的数 按照随机徘徊问题的基本假设,与上述计算回返概率的确定性方法(9)相对应的,蒙特 卡罗方法计算回返概率的详细步骤如下 (1)为计算作准备 令n=1,R=0 (2)开始第n个质点的随机徘徊 令m=1,l1=0,i=1,2,…,5 (3)确定质点的新位置 令[],其中[]表示取大于数*的最小整数 l2+1当}>1/2 (4)第n个质点的随机徘徊是否结束 当n<M时,或 l;|≠0 时,第n个质点的随机徘徊尚未结束,令m=m+1,转至步骤(3);否则第n个质点的随机 徘徊结束,记录贡献 R=R+n(∑1l21=0) (12) 进入下一步骤。 (5)N个质点的随机徘徊是否已完成 当n<N时,N个质点的随机徘徊尚未完成,令n=n+1,转至步骤(2);否则,N个质 点的随机徘徊已完成,进入下一步骤。 (6)给出计算结果 Pa≈Py=R 比较解决随机徘徊问题的上述两种不同方法,以S=3和M=2000.例,在平均每秒可 完成250万次四则运算的 CYBER70/825机上计算,确定性方法的情况是,需要计算机CP 时间26081分钟(其中所有阶乘计算都采用了节省机时的办法:事先算好N!存放在数组 元素F(N)中,需要N!时,直接调用F(N),P≈0.341;蒙特卡罗方法的情况是,抽样总 数N=1000,要计算机CPU时间74.43分钟,P≈0.3345,误差为0.002924(置信率为 0.95)。 5