当i<m时,an尚未确定,转至步骤(3);否则,an已经确定。 (5)记录贡献 P+no am< r 其中n(*)表示条件函数当条件*成立时为1否则为零 (6)抽样是否结束 当n<N时(N为样本总数),抽样尚未结束转至步骤(2);否则,抽样结束,进入下一步 骤 (7)给出计算结果与误差 计算结果为 误差则为240 P(IPm. M(*)-Pa(a)1)<1. 96/ -m, M(x)(1-p(s2-095 (5) 其中P(*)表示事件*发生的概率。 进一步比较上述KysM方法和蒙特卡罗方法的优缺点。由于前者所给出的实际上 只是一个渐近公式,若根据式(2)用ln(1+x)/hn2作为所求Pn(x)的近似,当m较小时,相 差可能较大;当m较大时,相差虽然可能较小,可是,在KyMm的结果中只给出了渐近误 差的阶,无法确定误差,因此,要想用ln(1+x)/ln2确定Pn(x)对于任意m的值,除非m足 够大,是靠不住的。蒙特卡罗方法的情况则完全不是这样,它可以给Pn(x)对于任意m的 近似值及其误差估计,因此如果目的仅限于给出关于Rn(x)的数值结果,用蒙特卡罗方法 计算出来的Pnx(x),要比用渐近公式n(1+x)1n2计算出来的更具有实际意义 2随机徘徊问题 处在S维空间格点上的质点,每步向2S个相邻格点中的任一个移动的机会是均等的。 所谓随机徘徊问题是问,质点返回初给位置的概率P(S)(简称回返概率)为多少? 早在191年, Polya曾用分析的方法确定,P(1)=1,P(2)=1,P(3)≠1。可是,大概 是由于计算量太大的原因,直到1940年,事隔19年之久,才由另外两位学者给出了P(3)的 近似值:P(3)≈0.358。下面我们来考虑一般的S维空间的随机徘徊问题。 用Un表示质点随机徘徊于第m步返回初始位置的概率。根据Un的定义,不难看出 当m为奇数时,Um=0;当m为偶数时 40.(4!)2 另一方面,若简单地用P表示回返概率P(S),则根据回返概率和Um的定义,一定有如下等 式成立