2.6 随机游走 随机游走也是一种基于运用[0，1]区间的均匀分布随机数序 列来进行的计算。 醉汉行走问题 醉汉开始从一根电线杆的位置出发（其坐标为 ，0=x x 坐标 向右为正，向左为负），假定醉汉的步长为l ，他走的每一步的 取向是随机的，与前一步的方向无关。如果醉汉在每个时间间 隔内向右行走的一步的几率为 ，则向左走一步的几率为 q 。 我们记录醉汉向右走了 步，向左走了 步，即总共走了 步。那末醉汉在行走了 步以后，离电线杆的距离为 其中 离电线杆的距离为 n L ， 。然而我们更感兴趣的是醉汉在行走 步以后， x 的概率 。 N = nR − n + R lnL ) ≤≤ Rn N p−= 1 x N Nl Nl Ln (= − x p )(xPN 下面便是醉汉在走了 步后的位移和方差的平均值 N （ < x N x , ∆<> 2 N > ）的计算公式。 < x >= N < x ∆ 2 N 其中 < x 2 N >= Nl ∑ xP N x Nl −= >=< x 2 N Nl ∑ x −= x )( , <−> x N > , 2 xPx )( 2 Nl N . 公式中的求平均是指对 步中所有可能的行走过程的平均。 . < 注意到在向左、向右对称的情况下，即 ， N 2xN∆ 4 pqNl qp ( − 。 ，得到 < 2/1== q >= >= xN Nl < p ) 2 0>=Nx 查点法和蒙特卡洛方法 在查点法中，对给定的行走总步数 及总位移 x ，要求把游走 时可能的每一步的坐标和几率都确定下来。这是可以用概率理 论精确计算的。 3=N 3 (xP 例如，对于 ,l 的醉汉一维行走问题，由概率理论可以得 到 ，由此可以 xP ( 3 算出 =−= )1 =− xP ( 3 xP ( 3 , , ， 3pq qp 2 1= )3 )3 )1 N = = = = = q q 3 3 2 3 < < 则 2 x 3 x 3 ∆< >= ∑ >= ∑ x 2 3 xP x )( 3 xPx )( 2 3 x 2 3 >=< 3 + x 3 − 2 + pq 3 pq 3 3 2 + 12 2 => + 3 qp 2 pq qp 3 2 p 9 + . 3 q 3 −= q 9 3 = <−> N 3 p = = 12 (3 pq qp − [ (3 ) qp ， ]2 − + ) . 查点法只有在总步数 较小时才可以使用。N 比较大时用起来 1 

就比较困难了。 蒙特卡洛方法就可以克服在游走中的这个困难，具有更广泛 N 10~ 的可操作性。蒙特卡洛方法可以对许多步的游走过程进行抽样， 例如 。我们可以按照正确的概率，对确定的 产生出 各种可能的行走样本。原则上只要我们增加抽样的个数，要达 到较高的精度总是可能的。 2 10 − N 5 随机游走的蒙特卡洛方法求解泊松型微分方程 2  ∂φ  x  ∂  q x y ( , = F s ( ) 2 ∂φ y 2 ∂ | = φ Γ + ) 2 ， Γ 为求解区域 D 的边界，s 为边界 Γ 上的点。 h 这里我们采用等步长 的正方形格点划分的差分法。在区域 D 内 的任意正则内点 0 (其相邻的节点都在区域 D 内)的函数值可以 用周围四个邻近点 1，2，3，4 上的函数值来表示。如同在第四 章中将要介绍的，这个表达式有如下差分方程表示 − h q . ( φ φ φ φ 4 φ 0 ) = + + + 1 2 3 2 0 1 4 ( q x y 的值。公式右边 ) , 0 其中 q 是在区域 D 的正则内点 0 上的函数 的系数 1/4 可以解释为概率。即我们有 φ ，W j ∑ = ， ∑W W j0 , φ j j ,( = − 1 = = j 0 0 4 0 4 0 , h q 2 4 j = 1 j = 1 . , , , ) 1 2 3 4 1 4 游走的判据是：选定一个[0，1]区间的均匀分布的随机数ξ， 若满足条件ξ≤ 1 4 ，我们选定下一个游走到达点为第 1 点；若满 足条件 1 4 < ≤ξ ，选游走到的下一个点为 2 点；若满足条件 1 2 1 2 < ≤ξ ， 3 4 选定游走到下一个点为 3 点；ξ在其他的情况下，我们则选游走 到第 4 点。 如果我们按上面的判据选择了 O 点周围四个点中之一 m 点， 则 O 点函数φ0 的估计值为 =φη m o − qh 2 4 0 ； m 从 点上又按判据选择周围四个点中的 n 点时， m 点函数 mφ ，此时 O 点函数φ0 的估计值也可以写为 =φη n m 的估计值为 − qh 2 4 m =φη n o − 2h 4 q + ( 0 q m ) ,……。 按上面的原则和步骤，如果从 0 点开始进行游走并记下该 2 

0 oq= )1( 点函数值 q ；在第 j 步游走到第 j 点时，记下该点 q(x,y)的 函数值 q ；直到该游走到第 J ( )1 步，到达边界 Γ 的 s( )1 点时，停止该 次游走，记下边界上这点的函数值 。此时我们可以得到 0 点上的函数 F s( ( )1 ) ( )1 j J 1 ( ) ∑ j = 0 q j 1 ( ) . 1 ( ) η0 φ0 的一个估计值 h 2 4 F s ( = − 1 ( ) ) φ0 如此反复从 0 点开始进行 N 次上述的随机游走，我们得到一个函 数 的估计值序列 { ,... 其中 η0 ∑ , n=1,2,...,N. ( η η η η 0 } ， F s ( ,... n ( ) 0 2 ( ) 0 n ( ) j 1 ( ) 0 = − q n ( ) n ( ) ) , N J ) n ( ) h 2 4 j = 0 则 0 点的函数φ0 的期望值为 ∑ ( η 0 N N n ) φ 0 = E { η 0 } ≈ ∑ n = 1 N    sF ( ( n ) ) − h 2 4 N ( n ) J ∑ j = 0 n ) q ( j    . n = 1 = 这个计算出的φ0 值的估计值序列的方差为 . −> E 2 σ ]}{ 2 η 0 [ < 2 η 0 = N N − 1 这种随机游走的做法，实际上是个人为的概率过程。它是一个 具有吸收壁的随机游走。 上面这种方法可以推广应用到更一般的二维、三维的椭圆 形方程的求解。在所需求解方程的边界条件特别复杂，而我们 所需求解的仅仅是系统中的若干点的函数值时，该方法是可供 选择的有效方法。 在随机游走的蒙特卡洛方法中，有一种最常用方法称为 Metropolis 方法。它是前面介绍过的重要抽样法的一个特殊情 况。采用此方法可以产生任意分布的随机数，包括无法归一化 的分布密度函数。 以一维的 Metropolis 方法为例，它所采用的游走规则是选择 ′→ ，使得它在游走中 的分布收敛到系统达到平衡时的分布 。 ,w 的选择加 ( 一个从 x 点游走到 点的“过渡几率”w ( 所走过的点 要达到这样分布的重要抽样，就需要对过渡几率 上适当的限制。 x′ ..... )xx ′ x x , 1 f x( ) x x x ) , 0 2 可以证明：只要游走所选的“过渡几率”满足如下的细致平 3 

衡条件， 就可以达到平衡时的分布为 这样的目的。 xwxf ) ( ( ′ f x( ) xwxf ( )( =′→ . →′ x x ) ) 实际上满足细致平衡条件只是一个充分条件，并不是一个 。所以， 的选择具有很大的自由度。选取不同的过渡几 必要条件。该条件并不能唯一地确定过渡几率 w ( 过渡几率 w ( 率就是不同的游走方法。 x ) ′→ x ) ′→ x x Metropolis 方法采用一个简单的选择过渡几率的方法，即 xw ( =′→ x )  ,1min   xf ) ( ′ xf )(    . 具体操作： (1)首先选取一个试探位置，假定该点位置为 x 其中ηn 为在间隔[ f x ( ) (2)计算 r try f x ) ( −δδ, 内均匀分布的随机数。 ] 的数值。 = n = x n +η ， n try 。 t ry r x try n x n x x n x xn = 1, + =1 )→ try xw try ( → = ， w x ( 2+nx )→ try )→ = 1），那么就 ），那就接受这一步游走，并取 满足（由公式(2.6.15)可以知道：此时 r (3)如果不等式 r ≥ 1 w x ( /1) = 然后返回（1）开始对游走到 点的试探。 (4)如果 r < 1（此时， w x ( n 再另产生一个[0，1]区间均匀分布的随机数ξ。 (5)如果此时ξ≤ r 到达的点为 的游走。 (6)如果此时ξ> r ，就拒绝游走到 这一点，即仍留在 点 的位置不变。 (7)返回到步骤(1)，重新开始对游走到 点的具体位置的 又一次试探。 ，那么也还接受这步游走，并取这步游走所 。然后返回到步骤(1)，开始下一步到达 点 xn+ =1 xn+2 xn+1 xtry xtry xn 采用这样的游走过程时，只有在产生了大量的点 后，才能得到收敛到满足分布 的点集。 f x( ) x x x , 0 , 1 ..... 2 如何选择δ的大小，以提高游走的效率? δ 选得太大，那么绝大部分试探的步子都将会被舍弃， 就很难达到平衡分布； δ 取得太小，那么绝大部分试探步子都会被接受，这同 4 

样难以达到所要求的平衡分布。 根据实际应用中的经验，选取δ的一个粗略标准应当是： 选择适当δ大小的原则是要在游走的试探过程中，有 1/3 到 1/2 的试探步子将被接受。 按照这样的标准选择得到的δ，就可以大大提高游走的效 率。 进行这样的随机游走，从哪一点出发才可以比较快地达到平衡 分布呢? 原则上讲，从任何一个初始位置出发均可达到平衡分布， 但是为了尽快地达到平衡分布，我们最好是要选择一个合适 的初始位置，这个初始位置应当是在游走范围内所要求的几 率分布密度 最大的区域。 f x( ) 5