2.6随机游走 随机游走也是一种基于坛用[0,1]区间的均勻分布隨机数序 列来选行的计算。 醉汉行走闷题 醉汉开始从一根电能析的位置出墩(其坐标为x=0,x坐标 向右为正,向左为负),假定醉汉的乡长为,他先的每一步的 取向是随机的,与前一步的方向无关。如录醉汊在每个时间间 隔内向右行走的一步的几率为p,则向左走一步的几率为q=1-po 我们记录醉汉向右走了n2步,向左先了n步,即总共走了N=n2+n 步。那来醉汉在行走了N步以后,高电能杆的距高为x=(n2-n2), 其中-M≤x≤M。裘而我们水兴趣的是醉汉在行走N步以后, 高电能杆的距高为x的概率P(x) 下面是醉汊在走了N步后的移和方的平均值 (xx<A>)的计算公式。 <xx>=∑xP3(x) <△r>=<xN>-<xy> 其中 ∑x2P(x) 公式中的求平均是指对N步中所有可能的行走过程的平均 <xN >=(P-qN △x2>=4pqN2 注定到在向左、向右对称的儕况下,即p=q=12,得到<x>=0 查点法和象特卡洛方法 在查点法中,对定的行走总少数N及总位移x。要求把游走 时可能的每一步的坐标和几率都确定下来。这是可以用概率理 论确计算的。 例如,对于N=3,l=1的醉汉一錐行走问是,由概率理论可以得 到 由此可以 出 <x>=∑xP(x)=-3y3-3p2+3pq+3p2=3p-q), ∑xP(x)=9 3pq+9p3=12p+[3(p-q >-<x3 查氚法只有在总步数N較小时才可以使用。N比较大时用起来
2.6 随机游走 随机游走也是一种基于运用[0，1]区间的均匀分布随机数序 列来进行的计算。 醉汉行走问题 醉汉开始从一根电线杆的位置出发（其坐标为 x = 0， x坐标 向右为正，向左为负），假定醉汉的步长为l，他走的每一步的 取向是随机的，与前一步的方向无关。如果醉汉在每个时间间 隔内向右行走的一步的几率为 ，则向左走一步的几率为q 。 我们记录醉汉向右走了 步，向左走了 步，即总共走了 步。那末醉汉在行走了 步以后，离电线杆的距离为 ， 其中 。然而我们更感兴趣的是醉汉在行走 步以后， 离电线杆的距离为 p = 1− p R n + n n l L ) R n N L n N = L n x R − N = ( − Nl ≤ x ≤ Nl x的概率P (x)。 N 下面便是醉汉在走了 步后的位移和方差的平均值 （ ）的计算公式。 N < > < ∆ > 2 , N N x x ∑ , =− < >= Nl x Nl N N x xP (x) < , 2 2 2 ∆xN >=< xN > − < xN > 其中 ∑ . =− < >= Nl x Nl N N x x P (x) 2 2 公式中的求平均是指对 步中所有可能的行走过程的平均。 ， . N 2 x p q Nl ∆ N xN < >= ( − ) 2 < >= 4 pqNl 注意到在向左、向右对称的情况下，即 p = q = 1/ 2，得到< xN >= 0。 查点法和蒙特卡洛方法 在查点法中，对给定的行走总步数N 及总位移x，要求把游走 时可能的每一步的坐标和几率都确定下来。这是可以用概率理 论精确计算的。 例如，对于 ,l 的醉汉一维行走问题，由概率理论可以得 到 ， , , ，由此可以 算出 N = 3 3 P (x = 1 −1) = 3 3 P (x = −3) = q 2 = 3pq P x p q 2 3 ( = 1) = 3 3 3 P (x = 3) = q < ( ) 3 3 3 3 3( )， 3 2 2 3 x3 >= ∑xP3 x = − q − pq + p q + p = p − q [ ] 3 2 2 3 2 3 2 2 3 < x >= ∑x P (x) = 9q + 3pq + 3p q + 9p =12pq + 3( p − q) . 则 x x x 12 pq . 2 3 2 3 2 < ∆ 3 >=< > − < > = 查点法只有在总步数N 较小时才可以使用。N 比较大时用起来 1
就比較困难了。 象特卡洛方法就可以克服在游走中的这个困难。具有J广 的可操作性。家饽卡洛方法可以对许多步的游走过程进行抽样, 例如N~102-105。我仉可以换照正确的概率,对确定的N产生出 各翀可能的行走祥本。原则上只要觉仉增加抽样的个数,达 到较高的贛度总是可能的。 随机游走的象彎卡洛方法求解铂松型徼分方翟 09 og ax a' q(xy),r为求解区域D的边界,S为边昦r上的点a PIr= F(s) 这里皝们采用普步长h的正方形格点划分的鑾分法。在区城D内 的任意正则內点0(其相邻的节胤都在区域D內)的函数值可以 用周围四↑邻近点1,2,3,4上的函教值来表示。如同在第四 章中将要介绍的。这个褒达式有如下塾分方程表示 p=(中1+2+φ3+中-h2 其中q是在区域D的正则内点0上的函数q(xy)的值。公式右边 的系数1/4可以解释为概率。即我们有 W,=1W 游走的判据是:选定一个[0,1区间的均訇分布的隨机数 考满足永件5≤,我们选定下一个游走到达点为第1点;若满 足永件1<1,选游走到的下一个点为2羸;若满足永件1<s3 选定游走到下一个点为3点;在其他的情况下,我们则选游走 到第4点 如果我们换上面的判据选择了0点周围四个点中之一m点, 则0点函数。的估计值为n。= 从m点上又换判据选择國四个点中的n点时,m点函数p 的佔计值为nn=pn 此时0点函数的佑计值也可以写为 7=中n 换上面的原则和步骤。如鼎从0点开始选行游走外记下该
就比较困难了。 蒙特卡洛方法就可以克服在游走中的这个困难，具有更广泛 的可操作性。蒙特卡洛方法可以对许多步的游走过程进行抽样， 例如 。我们可以按照正确的概率，对确定的 产生出 各种可能的行走样本。原则上只要我们增加抽样的个数，要达 到较高的精度总是可能的。 2 5 N ~10 −10 N 随机游走的蒙特卡洛方法求解泊松型微分方程 ∂ φ ∂ ∂ φ ∂ φ 2 2 2 2 x y q x y F s + = = ( , ) | ( ) Γ ， Γ为求解区域 D 的边界，s 为边界Γ上的点。 这里我们采用等步长 的正方形格点划分的差分法。在区域 D 内 的任意正则内点 0 (其相邻的节点都在区域 D 内)的函数值可以 用周围四个邻近点 1，2，3，4 上的函数值来表示。如同在第四 章中将要介绍的，这个表达式有如下差分方程表示 h φ φ 0 1 ( ) φ 2 φ 3 φ 4 2 0 1 4 = + + + − h q . 其中q0是在区域 D 的正则内点 0 上的函数q x( , y)的值。公式右边 的系数 1/4 可以解释为概率。即我们有 φ 0 0 φ 1 4 2 0 4 = − = ∑W h j q j , j ， W j ， j 0 1 4 1 = ∑ = W j . 0 j 1 4 1 2 3 4 , = = ,( , , , ) 游走的判据是：选定一个[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 ηo = φ m − ； 从m点上又按判据选择周围四个点中的n点时，m点函数φ m 的估计值为 m n qm h 4 2 η = φ − ，此时 O 点函数φ 0的估计值也可以写为 ( ) o n 0 m η = φ − q + q 4 2 h ,……。 按上面的原则和步骤，如果从 0 点开始进行游走并记下该 2
朿函数值=q";在蕈j步游走到簟j羸时,记下该点q(x,y)的 函数寶q直到该游走到第步,到达边界的s点时,序止该 次游走,记下边界上这点的函教值F(y)。此时们可以得到0 点上的函。的一个佔讣值 m=F(s)-∑ 如此风复从0点开始进行N次上述的随机游走,我们得到一个函 数p的估计序列 ,m,m…m”, 其中 7=F(")-4∑q,n=1,2…,N 则0点的函数的期望值为 m∑|F(-)-b2y q 中o=E{70} N 这个计算出的寶的估计序列的方为 >=E团小 这种机游走的散法,安际上是个人为的概率过程。它是一个 具有吸收壁的随机游走。 上面这种方法可以推广应用到更一舭的二维、三维的椭圆 形方程的求解。在所求解方程的边界永件符别复亲,而我仉 所鼎求解的仅仅是系統中的若干点的函教值时,该方法是可供 选择的有效方法。 在随机游走的象特卡洛方法中。有一种量鼎用方法称为 Metropolis方法。它是前面介绍过的量要抽禅法的一个殊情 况。采用此方法可以产生任龙分布的随机数,包括无法归一化 的分布度函数。 以一维的 Metropolis方法为例,咆所采用的游宠规则是选择 个从x点游走到x点的“过渡几率”w(x→x),使得它在游走中 所走过的xx1,x2的分布收敛到系能达到平衡时的分布f(x)o 要达到样分布的重抽样,就卿耍对过渡几率v(x,x)的选择加 上当的限侧。 可以证明:只要游定所选的“过渡几率”满足如下的细政平
点函数值q ；在第 j 步游走到第 j 点时，记下该点 q(x,y)的 函数值q ；直到该游走到第 (1) 0 o = q j ( ) 1 J ( ) 1 步，到达边界Γ的s ( ) 1 点时，停止该 次游走，记下边界上这点的函数值 。此时我们可以得到 0 点上的函数 F s( ( ) 1 ) φ 0的一个估计值 η 0 1 1 2 1 4 0 1 ( ) ( ) ( ) ( ) ( ) = − = F s ∑h q j j J . 如此反复从 0 点开始进行 N 次上述的随机游走，我们得到一个函 数φ 0的估计值序列 { } η 0 η η η ， 1 0 2 0 0 ( ) ( ) ( ) ( ) , ,... ,... n N 其中 η 0 2 4 0 ( ) ( ) ( ) ( ) ( ) n n j n j J F s h q n = − = ∑ , n=1,2,...,N. 则 0 点的函数φ 0的期望值为 N q h F s N E N n J j n j n N n n n ∑ ∑ ∑ = = = − = ≈ = 1 0 ( ) 2 ( ) 1 ( ) 0 0 0 ( ) 4 ( ) { } η φ η . 这个计算出的φ 0值的估计值序列的方差为 [ ] { } 1 2 0 2 0 2 σ η E η N N < > − − = . 这种随机游走的做法，实际上是个人为的概率过程。它是一个 具有吸收壁的随机游走。 上面这种方法可以推广应用到更一般的二维、三维的椭圆 形方程的求解。在所需求解方程的边界条件特别复杂，而我们 所需求解的仅仅是系统中的若干点的函数值时，该方法是可供 选择的有效方法。 在随机游走的蒙特卡洛方法中，有一种最常用方法称为 Metropolis 方法。它是前面介绍过的重要抽样法的一个特殊情 况。采用此方法可以产生任意分布的随机数，包括无法归一化 的分布密度函数。 以一维的 Metropolis 方法为例，它所采用的游走规则是选择 一个从x点游走到x′点的“过渡几率”w(x → x′)，使得它在游走中 所走过的点 的分布收敛到系统达到平衡时的分布 。 要达到这样分布的重要抽样，就需要对过渡几率 x x x 012 , , ..... f x( ) w(x, x′)的选择加 上适当的限制。 可以证明：只要游走所选的“过渡几率”满足如下的细致平 3
衡永件, f(x)w(x→x')=f(x')w(x→x) 就可以达到平衡时的分布为f(x)x样的目的。 实际上演足细政平衡永件只是一个充分永件,外不是一 必要永件。该永件不能唯一地确定过渡几率(x→x)。所以, 过渡几率训(x→x)的选择具有很大的自由度。选取不同的过渡几 率就是不同的游走方法。 Metropolis方法用一↑单的选择过渡几率的方法,即 v(x→x)=min/,<(x) f(x) 具体操作: (1)首先选取一个试探位量,假定该点世置为xn=x+n, 其中n为在间丽[-8。内均分布的隨机数。 (2)计算,。∫(x)的数。 (3)如景不普式r21澌足(由公式(2.6.15)可以知:此时 n(xn→xn)=1,m(x→x)=1/r),那就换受这一乡游定,外取xn=xno 然后巡回(1)开始对游走到xn2点的试捍。 (4)如果r<1(此时,(xn→xn)=r,mx→x)=1),那么就 再另产生一个[0,1]区间均訇分布的隨机数。 (5)如景此时sr,那么也还接曼这步游走,并取这步游走所 到达的点为xm1=x。痰后巡回到步骤(1),开始下一步到达xn2点 的游走。 (6)如景此时>r,就拒绝游走到x这一点,即仍留在x京 的位量不变。 (7)巡回到步骤(1),重新开始对游走到x点的具体位量的 叉一次试探。 采用这样的游走过程时,只有在产生了大量的京x0,x1,x 后,寸能得到收敛到灡足分布∫(x)的。 如向选择δ的大小,以提高游宠的效率? δ选;太大,那么绝大部分试探的步子部将食被會弃, 就很难达到平衡分布; δ取得太小,那么绝大部分试探步子都会被接受,这同
衡条件， f (x)w(x → x′) = f (x′)w(x′ → x) . 就可以达到平衡时的分布为 f x( )这样的目的。 实际上满足细致平衡条件只是一个充分条件，并不是一个 必要条件。该条件并不能唯一地确定过渡几率w 。所以， 过渡几率w 的选择具有很大的自由度。选取不同的过渡几 率就是不同的游走方法。 (x → x′) (x → x′) Metropolis 方法采用一个简单的选择过渡几率的方法，即 ′ → ′ = ( ) ( ) ( ) min 1, f x f x w x x . 具体操作： (1)首先选取一个试探位置，假定该点位置为x x try = +n η n ， 其中η n为在间隔[−δ ,δ ]内均匀分布的随机数。 (2)计算r f x 的数值。 f x try n = ( ( ) ) (3)如果不等式r ≥ 1 xn ) = 1/ 满足（由公式(2.6.15)可以知道：此时 ），那就接受这一步游走，并取 。 然后返回（1）开始对游走到 点的试探。 w x x n try ( ) → = 1, w x r try ( → x x n t +1 = ry n+2 x (4)如果r < 1（此时，w x x r n try ( ) → = ，w x x try n ( → ) = 1），那么就 再另产生一个[0，1]区间均匀分布的随机数ξ。 (5)如果此时ξ ≤ r xtry ，那么也还接受这步游走，并取这步游走所 到达的点为 。然后返回到步骤(1)，开始下一步到达 点 的游走。 xn+1 = xn+2 (6)如果此时ξ > r，就拒绝游走到 这一点，即仍留在 点 的位置不变。 xtry xn (7)返回到步骤(1)，重新开始对游走到 点的具体位置的 又一次试探。 xn+1 采用这样的游走过程时，只有在产生了大量的点 后，才能得到收敛到满足分布 的点集。 x x x 0 1 2 , , ..... f x( ) 如何选择δ 的大小，以提高游走的效率? δ 选得太大，那么绝大部分试探的步子都将会被舍弃， 就很难达到平衡分布； δ 取得太小，那么绝大部分试探步子都会被接受，这同 4
样难以达到所要求的平膏分布。 棂据实际应用中的经验,选取δ的一个粗略标准应当是 选择造当δ大小的原则是要在游走的试擐过程中,有1/3到 1/2的试探步子将被接曼 换照这样的橄准选择仆到的δ,就可以大大提高游走的效 选行这桦的随机游先,从哪一点出可以比较快地达到平衡 分布呢? 原则上讲,从任何一个物始量出发均可达到平衡分布 但是为了尽快地达到平衡分布,我们最好是戛选一个合适 的初始量,这个初始位量应当是在游走范國内所耍求的几 率分布鲁度f(x)最大的区域
样难以达到所要求的平衡分布。 根据实际应用中的经验，选取δ 的一个粗略标准应当是： 选择适当δ 大小的原则是要在游走的试探过程中，有 1/3 到 1/2 的试探步子将被接受。 按照这样的标准选择得到的δ ，就可以大大提高游走的效 率。 进行这样的随机游走，从哪一点出发才可以比较快地达到平衡 分布呢? 原则上讲，从任何一个初始位置出发均可达到平衡分布， 但是为了尽快地达到平衡分布，我们最好是要选择一个合适 的初始位置，这个初始位置应当是在游走范围内所要求的几 率分布密度 f x( )最大的区域。 5