2.6随机游走 随机游走也是一种基于运用[0，1]区间的均匀分布随机数序 列来进行的计算。 醉汉行走问题 醉汉开始从一根电线杆的位置出发（其坐标为，0=x x坐标 向右为正，向左为负），假定醉汉的步长为l，他走的每一步的 取向是随机的，与前一步的方向无关。如果醉汉在每个时间间 隔内向右行走的一步的几率为，则向左走一步的几率为 q 。 我们记录醉汉向右走了步，向左走了步，即总共走了 步。那末醉汉在行走了步以后，离电线杆的距离为， 其中。然而我们更感兴趣的是醉汉在行走步以后， 离电线杆的距离为 p p?=1 R nn + ln L ) R n N L n L N = n R ?x N (= NlxNl ≤≤? x的概率。 )(xP N 下面便是醉汉在走了步后的位移和方差的平均值 （）的计算公式。 N >?<>< 2 , NN xx , ∑ ?= >=< Nl Nlx NN xxPx )( < , 222 ><?>>=<? NNN xxx 其中 . ∑ ?= >=< Nl Nlx NN xPxx )( 22 公式中的求平均是指对步中所有可能的行走过程的平均。 ， . N 2 x N ?Nlqpx N )( ?>=< 2 4pqNl>=< 注意到在向左、向右对称的情况下，即 2/1== qp ，得到 < 。 0>= N x 查点法和蒙特卡洛方法 在查点法中，对给定的行走总步数及总位移N x，要求把游走 时可能的每一步的坐标和几率都确定下来。这是可以用概率理 论精确计算的。 例如，对于,l的醉汉一维行走问题，由概率理论可以得 到，, , ，由此可以 算出 3=N 3 (xP 1= )1 =? 3 3 )3( qxP =?= 2 3pq= qpxP 2 3 3)1( == 3 3 )3( qxP == <， )(33333)( 3223 33 qppqppqqxxPx ?=++??=>= ∑ [ ] 23223 3 22 3 )(3129339)( qppqpqppqqxPxx ?+=+++=>= ∑ < . 则 . pqxxx 12 2 3 2 3 2 3 =><?>>=<?< 查点法只有在总步数较小时才可以使用。N比较大时用起来N 1 就比较困难了。 蒙特卡洛方法就可以克服在游走中的这个困难，具有更广泛 的可操作性。蒙特卡洛方法可以对许多步的游走过程进行抽样， 例如。我们可以按照正确的概率，对确定的产生出 各种可能的行走样本。原则上只要我们增加抽样的个数，要达 到较高的精度总是可能的。 52 1010~ ?N N 随机游走的蒙特卡洛方法求解泊松型微分方程 ?φ ? ?φ ? φ 2 2 2 2 xy qxy Fs += = ? ? (,) |() Γ ? ? ? ， Γ为求解区域D的边界，s为边界Γ上的点。 这里我们采用等步长的正方形格点划分的差分法。在区域D内 的任意正则内点0 (其相邻的节点都在区域D内)的函数值可以 用周围四个邻近点1，2，3，4上的函数值来表示。如同在第四 章中将要介绍的，这个表达式有如下差分方程表示 h () φφφφφ 01234 2 0 1 4 =+++?hq . 其中q是在区域D的正则内点0上的函数 0 ( ),qxy的值。公式右边 的系数1/4可以解释为概率。即我们有 φφ 00 1 4 2 0 4 =? = ∑ W h q j j j, ， ， W j j 0 1 4 1 = ∑ = Wj . j0 1 4 1234 , ,( ,,,)== 游走的判据是：选定一个[0，1]区间的均匀分布的随机数ξ， 若满足条件ξ ≤ 1 4 ，我们选定下一个游走到达点为第1点；若满 足条件 1 4 1 2 <≤ξ ，选游走到的下一个点为2点；若满足条件 1 2 <≤ξ 3 4 ， 选定游走到下一个点为3点；ξ在其他的情况下，我们则选游走 到第4点。 如果我们按上面的判据选择了O点周围四个点中之一m点， 则O点函数 φ 0 的估计值为 0 2 4 q h mo ?=φη ； 从点上又按判据选择周围四个点中的n点时，m点函数m m φ 的估计值为 mnm q h 4 2 ?=φη，此时O点函数φ 0 的估计值也可以写为 )( 0 mno qq +?=φη 4 2 h ,……。 按上面的原则和步骤，如果从0点开始进行游走并记下该 2 点函数值 q ；在第j步游走到第j点时，记下该点q(x,y)的 函数值 q ；直到该游走到第 )1( 0 o q= j ()1 J ()1 步，到达边界Γ的s ()1 点时，停止该 次游走，记下边界上这点的函数值。此时我们可以得到0 点上的函数 Fs( ()1 ) φ 0 的一个估计值 η 0 11 2 1 0 4 1 () () () () () =? = ∑ Fs h q j j J . 如此反复从0点开始进行N次上述的随机游走，我们得到一个函 数的估计值序列 φ 0 {} ， ηηηη 0 1 0 2 00 () () () ( ) , ,... ,... nN 其中 η 0 2 0 4 () () () () () nn j n j J Fs h q n =? = ∑ , n=1,2,...,N. 则0点的函数φ 0 的期望值为 N q h sF N E N n J j n j n N n n n ∑∑ ∑ == = ? ? ? ? ? ? ? =≈= 10 )( 2 )( 1 )( 0 00 )( 4 )( }{ η ηφ . 这个计算出的 φ 0 值的估计值序列的方差为 []}{ 1 2 0 2 0 2 ηησ E N N ?>< ? = . 这种随机游走的做法，实际上是个人为的概率过程。它是一个 具有吸收壁的随机游走。 上面这种方法可以推广应用到更一般的二维、三维的椭圆 形方程的求解。在所需求解方程的边界条件特别复杂，而我们 所需求解的仅仅是系统中的若干点的函数值时，该方法是可供 选择的有效方法。 在随机游走的蒙特卡洛方法中，有一种最常用方法称为 Metropolis方法。它是前面介绍过的重要抽样法的一个特殊情 况。采用此方法可以产生任意分布的随机数，包括无法归一化 的分布密度函数。 以一维的Metropolis方法为例，它所采用的游走规则是选择 一个从x点游走到点的“过渡几率”wx′ )( xx ′→，使得它在游走中 所走过的点的分布收敛到系统达到平衡时的分布。 要达到这样分布的重要抽样，就需要对过渡几率 xxx 012 , , ..... fx() ( )xx ′,w的选择加 上适当的限制。 可以证明：只要游走所选的“过渡几率”满足如下的细致平 3 衡条件， )()()()( xxwxfxxwxf → ′′=′→ . 就可以达到平衡时的分布为这样的目的。 fx() 实际上满足细致平衡条件只是一个充分条件，并不是一个 必要条件。该条件并不能唯一地确定过渡几率w。所以， 过渡几率w的选择具有很大的自由度。选取不同的过渡几 率就是不同的游走方法。 )( xx ′→ )( xx ′→ Metropolis方法采用一个简单的选择过渡几率的方法，即 ? ? ? ? ? ? ′ =′→ )( )( ,1min)( xf xf xxw . 具体操作： (1)首先选取一个试探位置，假定该点位置为xx try n n =+η， 其中η n 为在间隔 [] ?δ δ, 内均匀分布的随机数。 (2)计算 r 的数值。 fx fx try n = ( () ) (3)如果不等式r ≥1 x n /1) = 满足（由公式(2.6.15)可以知道：此时 ），那就接受这一步游走，并取。 然后返回（1）开始对游走到点的试探。 wx x ntry ()→=1, rxw try ( → xx nt+ = 1 ry 2+n x (4)如果r <1（此时，wx x r ntry ()→ =，wx x try n ()→ = 1），那么就 再另产生一个[0，1]区间均匀分布的随机数ξ。 (5)如果此时ξ ≤ r x try ，那么也还接受这步游走，并取这步游走所 到达的点为。然后返回到步骤(1)，开始下一步到达点 的游走。 x n+ = 1 x n+2 (6)如果此时 ξ >r，就拒绝游走到这一点，即仍留在点 的位置不变。 x try x n (7)返回到步骤(1)，重新开始对游走到点的具体位置的 又一次试探。 x n+1 采用这样的游走过程时，只有在产生了大量的点 后，才能得到收敛到满足分布的点集。 xxx 012 ,,... fx() 如何选择δ的大小，以提高游走的效率? δ 选得太大，那么绝大部分试探的步子都将会被舍弃， 就很难达到平衡分布； δ 取得太小，那么绝大部分试探步子都会被接受，这同 4 样难以达到所要求的平衡分布。 根据实际应用中的经验，选取δ的一个粗略标准应当是： 选择适当δ大小的原则是要在游走的试探过程中，有1/3到 1/2的试探步子将被接受。 按照这样的标准选择得到的δ，就可以大大提高游走的效 率。 进行这样的随机游走，从哪一点出发才可以比较快地达到平衡 分布呢? 原则上讲，从任何一个初始位置出发均可达到平衡分布， 但是为了尽快地达到平衡分布，我们最好是要选择一个合适 的初始位置，这个初始位置应当是在游走范围内所要求的几 率分布密度最大的区域。 fx() 5