2.6 随机游走chapter2-6

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