第四届丘成桐中学数学奖获奖论文－多维随机游走及应用

多维随机游走及应用 摘要 本文从一维和二维随机游走开始探究,基于组合数学和概率论的有关理论, 利用 Bernoulli 概型及其叠加推导得到了从一确定点出发到达任意随机点的概 率；然而在三维随机游走问题上,不能直接利用 Bernoulli 概型,因而首先引入了 一个有放回的摸球问题,再通过该问题得到三维随机变量的分布概型,从而解决 了三维随机游走中到达任意随机点的概率问题,并且通过这个思想推导了多维随 机游走的相关结论.最后,本文将得到的结论应用在环形随机游走中，得到相关结 论.   关键字：多维随机游走 多项式系数 环形随机游走 正文： 引言： “随机游走”（random walk）是指基于过去的 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 现,无法预测将来的 发展步骤和方向.随机游走问题最早来源于“莱茵街的醉汉”问题：一个醉 汉从酒店出发,向左走和向右走分别有一个概率,那么他回到家的概率是多 少？这是一个有趣的概率问题,引起了我的兴趣.同时,在思考解决这个问 题的基础上,我想是否也可以解决在二维坐标平面内的随机游走问题,甚至 是在多维空间内的？在环上进行随机游走又是怎么样的呢？随后我去查阅 了有关方面的内容,其中一维随机游走在随机过程中有给出一些结论,而二 维,多维随机游走的结论却很少甚至空白；环型随机游走也没有结论.于是, 我试图去解决这些问题. 本文的主要理论思想是 Bernoulli 概型及多维随机变量分布 随机游走理论在实际生活中有广泛的应用,如股票价格的游走模型“R/S 分析法” 从对ＥＭＨ的产生及其发展讨论出发,从分形的角度探讨市场特 性的分形市场分析方法及其所反映的市场特性；应用基于边缘检测的随机 游走算法对多车辆视频进行精确车辆检测等等.这些也都是今后研究的潜 在方向. 本文中,我们假设所讨论的随机过程均为离散的,即每一步之间都是相互独 立的.每一次沿坐标轴移动一个单位. 基本理论 1． 一维随机游走 一维随机游走是最简单的,也是最基础的. 由于每一步之间都相互独立,并 且每一步有且只有两种可能结果,每种可能情况发生的概率之和为1,所以它符合 Bernoulli 概型. 定理 1：假设从零点出发在数轴 x上一维随机游走, 向右走的概率为 ,向左 走的概率为 ,且 p q 1,0, =+> qpqp .设事件 A：共走了 步, ,到达了点N *NN ∈ Naa ≤, . 则： ⎪⎩ ⎪⎨ ⎧ ≡ ≡ = −++ )2(modN )2(mod\,0 )( 222 aqpC aN AP aNaNaN N ， . 证明： 以 表示第 步后点所在的坐标,则有 ,当第 步为向右时 ,当第 步为向左时 nx n nnn xx δ − −+= )1(1 n 0=δn n 1=δn .则 .其中 为 的个 数,β为 的个数.则有 ∑ = δ β−α=−= N i N ix 1 )1( α 0=δi 1=δi a=β−α , N=β+α , β=− 2aN .故 . )2(modN a≡ ∴(1)： )2(mod\ aN ≡ 时, ( ) 0=AP . (2): 时, )2(modN a≡ 设向右走了 步,则向左走了k kN − 步,则： akNk =−− )( 2 aNk +=⇒ . ∴ 222)( aNaNaN N kNkk N qpCqpCAP −++ − == , 综上, ⎪⎩ ⎪⎨ ⎧ ≡ ≡ = −++ )2(modN )2(mod\,0 )( 222 aqpC aN AP aNaNaN N ， . 推论 1.假设一点从点 i出发,在数轴 x上一维随机游走, 向右走的概率为 , 向左走的概率为 ,且 p q 1,0, =+> qpqp . 设事件 A′：共走了 步, ,到达了 点 N *NN ∈ Nijj ≤−, . 则 ( ) ( ) ( ) ⎪⎩ ⎪⎨ ⎧ −≡ −≡ =′ −−−+−+ )2(modN )2(mod\,0 )( 222 ijqpC ijN AP ijNijNijN N ٛ . 此后,我们自然可以想到另外一个问题,在前 步内到达点 的概率是多 少？ N a 推论 2：从零点出发在数轴 x上一维随机游走, 向右走的概率为 ,向左走的 概率为 ,且 . 设事件 p q 1,0, =+> qpqp A ′′ ：在 步之内（包括第 步）到达了 点 N N Naa ≤, , . 则 *NN ∈ ∑ = −++ =′′ N ai aiaiai i qpCAP 222)( ,其中 ( )2modai ≡ . 证明： 事件 A ′′ ：在 步之内（包括第 步）到达点 a ,即在第 步,第 步,……, 第 步（ ）或第 N N a 2+a N )2(modaN ≡ 1−N 步（ )2(mod\ aN ≡ ）中的一步或几步中到达 点 a .根据定理 1,第 i步（ )2(mod, aiai ≡≥ ）到达点 a的概率为 222 aiaiai i qpC −++ .所以, 在 步之内（包括第 步）到达点 a的概率即为所有可能情况发生的概率之和, 即 N N ∑ = −++ =′′ N ai aiaiai i qpCAP 222)( , ( )2modai ≡ . 2.二维随机游走 与一维随机游走不同的是,二维随机游走的每一步由一维中的 个方向变成 了二维中的4个方向,故不能简单地使用 Bernoulli 概型.但是,我们仍然可以通 过两个 Bernoulli 概型的叠加得到二维随机游走的结论. 2 定理 2：一质点在二维坐标系 上进行随机游走,从原点出发,向右走的概 率为 ,向左走的概率为 ,向上走的概率为 ,向下走的概率为 ,且 xOy p q m n 1,0,,, =+++> nmqpnmqp . 设事件B：共走了 步, ,到达了点N *NN ∈ ( )ba, （假设 ）,0, >ba Nba ≤+ .则： ( ) ( ) ( ) ( ) ( ) ( )⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ ≡+≡ ⎥⎦ ⎤⎢⎣ ⎡ ⋅⋅++ +≡ = ∑− = −−+−+−−++ − 2mod,2mod 2mod\,0 222222 aibaN nmCqpCnmqpC baN BP bN ai biNbiNbiN i aiaiai i iNii N . 证明： 设总步数为 ,其中沿N x轴方向走了G步,沿 轴方向走了y H 步. NHG =+∵ Nba ≤+∴ bNa −≤∴ 以 表示第 步后点所在的坐标,则有 ,当第 步为向右时 ,当第 n步为向左时 nx n nnn xx δ − −+= )1(1 n 0=δn 1=δn .则 .其中 α为 的个 数,β为 ∑ = −=−= G i G ix 1 )1( βαδ 0=δi 1=iδ 的个数.则有 a=β−α , G=β+α , β=− 2aG .故 )2(modG a≡ . I. 时, )2(mod\ aG ≡ ( ) 0=BP . 即此时是不可能到达 ( 的；同时,若)ba, )2(mod\ aG ≡ ,有 )2(mod\ aG −≡ ,即 2 aG + 不是整数,在组合中这是不符合要求的,故此时, 0)( =BP . II. , )2(modaG ≡ 这种情况下是可能到达 ( 点的, (1) )ba, aNHaG −== , . 1A ： x轴方向走了 步, 轴方向走了a y aN − 步,共 步.则： N ( ) ( ) ( ) aNaaN nmqpCAP −++=1 . 1B ： x轴方向走的 步均向右.则： a ( ) aaaa pqpCBP == 01 . ∴ ( ) ( ) ( ) ( ) ( ) aaNaaN pnmqpCABPAPBAP ⋅++== −11111 . 1C ： 轴方向走了 步,到了 .则： y aN − b 假设向上走了 步,有 j ( ) 2 baNjbjaNj +−=⇒=−−− , ( ) 2221 baNbaNbaN aN jaNjj aN nmCnmCCP −−+−+− − −− − == , ∴ ( ) ( ) ( ) ( ) ( ) 22211111 baNbaNbaN aNGGN nmCnmqpCACPAPCAP −−+−+−−⋅++== . (2) . bHbNG =−= , 2A ： 轴方向只走了b步,y x轴方向走了 bN − 步,共 步.则： N ( ) ( ) ( )bbNbN nmqpCAP ++= −2 . 2B ： x轴方向走了 步,到了 .则： bN − a 假设向右走了 i 步,有 ( ) 2 baNiaibNi −+=⇒=−−− , ( ) 2222 baNbaNbaN bN ibNii bN qpCqpCBP −−−+−+ − −− − == . 2C ：若 轴方向走的b步均向上.则： y ( ) bbbb nnmCP == 02C . )()()()B()()B( 222222222222 ACPABPAPACPAPCAP =⋅=∴ ( ) ( ) bbaNbaNbaN bNbbNbN nqpCnmqpC ⋅⋅++= −−−+−+ − − 222 . (3) aNHbbNGa −≤≤−≤≤ , . 3A ： x轴方向走了G步, 轴方向走了y H 步,共 步.则： N ( ) ( ) ( ) GNGGN nmqpCAP −++=3 . 3B ： x轴方向走了G步,到达 .则： a 假设向右走了 g 步,有 ( ) 2 aGgagGg +=⇒=−− , ( ) 2223 aGaGaG G gGgg G qpCqpCBP −++ − == . 3C ： 轴方向走了y H 步,到达b .则： 假设向上走了 步,有 h ( ) 2 bHhbhHh +=⇒=−− . ( ) 2223C bGNbGNbGN GN hHhh H nmCnmCP −−+−+− − − == . )()()()B()()B( 333333333333 ACPABPAPACPAPCAP =⋅=∴ ( ) ( ) 222222 bGNbGNbGN GN aGaGaG G GNGG N nmCqpCnmqpC −−+−+− − −++ − ⋅⋅++= . ( ) ( ) ( ) ( ) ( ) ( ) , 2mod,2mod 2mod\,0 222222 ⎪⎪⎩ ⎪⎪⎨ ⎧ ≡+≡ ⎥⎦ ⎤⎢⎣ ⎡ ⋅⋅++ +≡ =∴ ∑− = −−+−+−−++ − aibaN nmCqpCnmqpC baN BP bN ai biNbiNbiN i aiaiai i iNii N 推论 3. 一质点在二维坐标系 上进行随机游走,从点xOy ( )dc, 出发,向右走 的概率为 ,向左走的概率为 ,向上走的概率为 ,向下走的概率为 ,且p q m n 1,0,,, =+++> nmqpnmqp . 设事件B′：共走了 步, ,到达了点N *NN ∈ ( )ba, （假设 ）,0, >ba Nba ≤+ .则： ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( )( ) , .2mod ,2mod\,0 222222 ⎪⎪⎩ ⎪⎪⎨ ⎧ +−+≡ ⎥⎦ ⎤⎢⎣ ⎡ ⋅⋅++ +−+≡ =′ ∑−− −= −−−−+−−+−−−−+−+ − dcbai nmCqpCnmqpC dcbai BP dbN cai dbiNdbiNdbiN i caicaicai i iNii N 3. 维随机游走 n2 在得到了二维随机游走的结果后,由于 维可以看作是 个二维情况的简单 叠加,因此我们可以以类似的方法将几个 Bernoulli 概型进行叠加,从而得到 维随机游走的结论.然而,由于每一次使用Bernoulli概型时,它的分布 中的 总是一个变量,所以得到的表达式是十分复杂的,也不易于计算.因此,本 文中并没有给出计算. n2 n n2 kNkk N qpC − N 4. 三维随机游走 三维随机游走无法简单地像二维随机游走直接将几个 Bernoulli 概型进行 叠加,因为它需要的是一个三维随机变量的分布概型,故我们用最基本的方法来 推出三维随机游走模型. 首先,我们引出一个有放回摸球问题： 引理 1：一个袋子中有 A个白球,B个黑球, 个红球（各球形状大小均无差 异）. 现有放回地从袋子中摸球,设事件 ：在 次摸球中摸到 个白球,b个黑 球,（ 个红球）,则 D S n a ban −− ( ) ( )[ ] (( ) )ba+nbabanbanbaban qpqpGrqpGSP −−− +−⋅=⋅= 1,, ) . 证明：由于摸球是有放回的,不妨假设每个球都是有编号的,那么每次摸球都 有 ( 种可能的情况,即每一次摸球有DBA ++ ( )DBA ++ 个 样本 保单样本pdf木马病毒样本下载上虞风机样本下载直线导轨样本下载电脑病毒样本下载 点；又因为共摸 了n次,所以共有 ( )nDBA ++ 个样本点. 事件 是 次摸球中摸到 个白球,b个黑球,这样的组合有 个. S n a b anan CC −⋅ 为了表示方便,我们先引入一个符号 , banG , ( ) ( ) ( ) ( )!!! ! !! ! !! !, banba n banb an ana nCCG b an a n ba n −−=−− −⋅−=⋅= − . 即这样的组合有 个. banG , 而对于每一种组合情况,又都有 banba DBA −− 个样本点,而且这 种情况又 是两两互斥的,所以事件 中有 个样本点.再由古典概型的定义 可得： ba nG , S banbaban DBAG −−⋅, ( ) ( )n banbaba n DBA DBAGSP ++ ⋅= −−, . 又假设摸到白球的概率是 ,摸到黑球的概率是 q ,摸到红球的概率是p r ,必 然 有 ,1=++ rqp )(1 qpr +−= . 根 据 古 典 概 型 的 定 义 , 可 知 DBA Ap ++= , DBA Bq ++= , ( ) DA B Drqp ++==+−1 ,则： ( ) ( ) ( ) ( ) banba banbaba n DBADBADBA DBAGSP −− −− ++⋅++⋅++ ⋅= , ( )[ ] ( )banbabanbanbaban qpqpGrqpG +−−− +−⋅=⋅= 1,, . 这 与 二 项 分 布 ( )pnkbqpC knkkn ,;=− 是 很 类 似 的 , 所 以 我 们 不 妨 记 . ( )[ ] ( ) ),,;,(1, qpnbabqpqpG banbaban =+− +− 现在,我们在此基础上讨论三维随机游走问题. 定理 3：一质点在一个三维坐标空间 上随机游走,从原点出发.向Oxyz x轴正 方向移动的概率为 ,向p x轴负方向移动的概率为 ,向 轴正方向移动的概率为 ,向 轴负方向移动的概率为 ,向 轴正方向移动的概率为 ,向 轴负方向 移动的概率为 t ,且 , q y m y n z s z 0,,,,, >tsnmqp 1=+++++ tsnmqp .设事件T ：共走了 步, ,到达了点 （假设 ）, N *NN ∈ ( cba ,, ) 0,, >cba Ncba ≤++ .则： ( ) ( ) ( ) ( ) ( ) ( )( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎨ ⎧ ≡≡++≡⎥⎦ ⎤ ⎢⎣ ⎡ ⋅⋅⋅+++ ++≡ = −+−++−++− +− +− = +− = −++−++ +−∑ ∑ .2mod,2mod,2mod, 2mod\,0 222 222222, bhagcbaNqpC qpCqpCtsnmqpG cbaN TP chgNchgNchgN hgN cbN ag caN bh bhbhbh h agagag g hgNhghg N 证明： 设事件 A：沿 x轴方向走了 g步,沿 轴方向走了h步,沿 轴方向走了 步. y z j 显然有 ( hgNj + )−= ,且需 ( )cbNga +−≤≤ , 同理, ,( )caNhb +−≤≤ ( )baNjc +−≤≤ . 根据引理 1,可知： ( ) ( ) ( ) ( ) hgNhghgN tsnmqpGAP −−+++= , , 设事件B：沿 x轴方向走了 g步的情况下, x轴上到坐标 . a 设向a所在方向移动了 步,则i ( ) 2 agiaigi +=⇒=−− . ( ) 222 agagaggigiig qpCqpCABP −++− == . 同理, 事件C：沿 轴方向走了h步的情况下, 轴上到坐标b . y y ( ) 222 bhbhbhh nmCACP −++= . 事件 ：沿 轴方向走了 步的情况下, 轴上到坐标 D z j z c ( ) ( )( ) ( ) ( )222222 chgNchgNchgN hgNcjcjcjj tsCtsCADP −+−++−++− +−−++ == . 综上所述, ( ) ( ) ( ) ( ) ( )( )( )∑ ∑+− = +− = −++−++ +−⎢⎣ ⎡ ⋅⋅⋅+++=∴ cbN ag caN bh bhbhbh h agagag g hgNhghg N qpCqpCtsnmqpGTP 222222 , ( ) ( ) ( ) ( ) ⎥⎦ ⎤−+−++−++− +− 222 chgNchgNchgN hgN qpC . 推论3：一质点在一个三维坐标空间 上随机游走,从点Oxyz ( )fed ,, 出发.向 x 轴正方向移动的概率为 ,向p x轴负方向移动的概率为 q ,向 轴正方向移动的概 率为 ,向 轴负方向移动的概率为 n ,向 轴正方向移动的概率为 ,向 轴负 方向移动的概率为 t ,且 , y m y z s z 0,,,,, >tsnmqp 1=+++ + + tnmqp s .设事件T ：共走 了 步 , , 到 达 了 点N *NN ∈ ( )cba ,, （ 假 设 , , , ）,0,, >cba da ≥ eb ≥ fc ≥ Ncba ≤++ .则： ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( )[ ]( ) ( )[ ] ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( )⎪⎪ ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎪⎪ ⎨ ⎧ ≡≡++−++≡ ⎥⎦ ⎤⋅ ⎢⎣ ⎡ ⋅⋅+++ ++−++≡ = −−+−−++−−++− +− −−−+−+ +−+− −= +−+− −= −+−+−+ +−∑ ∑ .2mod,2mod,2mod , 2mod\,0 222222 222, bhagfedcbaN qpCqpC qpCtsnmqpG fedcbaN TP fchgNfchgNfchgN hgN ebhebhebh h fecbN dag fdcaN ebh dagdagdag g hgNhghg N 5. 多维随机游走 首先,和三维随机游走一样,我们先将Bernoulli概型推广至 维随机变量分 布. n 引理 2： 一个袋子中有 个 球, 个 球,…, 个 球（各球形状大小 均无差异）. 现有放回的从袋子中摸球, 设事件 1A 1a 2A 2a kA ka M ：在 次摸球中摸到 个 球, 个 球,…, 个 球,则 n 1B 1a 2B 2a kB ka ( ) 1 2, ,..., 1 1 k k B B B n j j n k j j G A P M A = = ⋅ = ⎛ ⎞⎜ ⎟⎝ ⎠ ∏ ∑ . 证明：由于是有放回的,不妨假设每个球都是有编号的,那么每次摸球都有 1 k j j A = ∑ 种可能的情况,每次有 个样本点,又因为共摸球 次,所以样本点共有 1 k j j A = ∑ n 1 n k j j A = ⎛ ⎞⎜⎝ ⎠∑ ⎟ 个. ( ) ⎟⎠ ⎞⎜⎝ ⎛ −⋅ ==⋅⋅⋅ ∑∏ == k i i k i i BBB n B n B n B n BnB nGCCC kk 11 ,...,, ! !2,121 . ( ) 1 2, ,..., 1 1 k k B B B n j j n k j j G A P M A = = ⋅ = ⎛ ⎞⎜ ⎟⎝ ⎠ ∏ ∑ , 设 ∑ = = k i i j j A A p 1 ,则： ( ) ∏ = ⋅= k j B j BBB n jk pGMP 1 ,...,, 2,1 . 由此,我们不难得到多维随机游走的结果. 可以通过类似于三维的方法证明以下： 猜想：假设在一个 维坐标空间上随机游走,从原点出发.向 轴正方向移动 的 概 率 为 , 向 轴 负 方 向 移 动 的 概 率 为 , 其 中 , 且 , .设事件 n ix ip ix iq [ ni ,...,1∈ ] 0, >ii qp ( )∑ = =+ n i ii qp 1 1 R ：共走了 步, ,到达了点 ,其中 表示在坐标轴 上的坐标（假设 ）,∑ .记 ,则： N *NN ∈ ( naaa ,...,, 21 ) ia ix 0>ia = ≤ n i i Na 1 ∑ = =λ n i ia 1 ( ) ∑ ∑ ∑ ∏∏−λ− = −λ− = −λ− = −++ = ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ⋅⋅⋅= 1 11 2 22 2,1 222 1 ,...,,... aN aj aN aj aN aj ajajaj j n j B j BBB n n nn iiiiii i jn qpCpGRP . 6．一维随机游走的再讨论    首先，我们需要两条组合数学中 T路的基本定理.  引理 3    若整点 ( )α,aA 和整点 ( )β,bB 满足 T条件,那么 A到B的 T路条数为  ( ) ! 22 ! 22 ! ⎟⎠ ⎞⎜⎝ ⎛ −−−⋅⎟⎠ ⎞⎜⎝ ⎛ −+− − αβαβ abab ab .  引理 4  （反射原理）  若整点 ( )α,aA 和整点 ( )β,bB 满足 T条件,且 0,0 >> βα ,则 由 ( )α,aA 到 ( )β,bB 的经过 x轴的 T路条数等于由 ( )α−′ ,aA 到 ( )β,bB 得 T路条数, 为 ( ) ! 22 ! 22 ! ⎟⎠ ⎞⎜⎝ ⎛ +−−⋅⎟⎠ ⎞⎜⎝ ⎛ ++− − αβαβ abab ab .  这条定理的具体证明并不复杂,可以参见参考书目[5].    定理 4  从零点出发在数轴 x上一维随机游走,设每一步移动的距离均为一个单位, 每一次移动向右走和向左走的概率均为 .现已知在一次随机游走中向左走的 步数与向右走的步数均为 ,即总步数为 ,最后回到了零点.设事件Q :在上述随 机游走中仅仅出发时和最后一步经过了零点.则  2/1 n n2 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ⎥⎦ ⎤⎢⎣ ⎡ − −−−− −= !2! !22 !1!1 !22 !2 !!2 nn n nn n n nnQP .  证明:  根据引理 3 和引理 4 可知,  由 ( )α,aA 到 ( )β,bB 的不经过 x轴的 T 路条数 等于 S ( ) ( ) ! 22 ! 22 ! ! 22 ! 22 ! ⎟⎠ ⎞⎜⎝ ⎛ +−−⋅⎟⎠ ⎞⎜⎝ ⎛ ++− −− ⎟⎠ ⎞⎜⎝ ⎛ −−−⋅⎟⎠ ⎞⎜⎝ ⎛ −+− − αβαβαβαβ abab ab abab ab .  而所求的路即为从 到( )1,11A ( )1,121 −nB 和从 ( )1,12 −A 到 ( )1,122 −−nB 的不经过 x轴 的 T路条数之和,  ( )( ) ( ) ( ) ( )!2! !22 !1!1 !22 1 − −−−− −= nn n nn nS , ( )( ) ( ) ( ) ( )!2! !22 !1!1 !22 2 − −−−− −= nn n nn nS ,  所以 ( )( ) ( ) ( ) ( ) ⎥⎦ ⎤⎢⎣ ⎡ − −−−− −= !2! !22 !1!1 !222 nn n nn nS .而由 ( )α,aA 到 ( )β,bB 的 T 路条数 为N ( ) !! !2 nn n , 所以 ( ) ( )( ) ( ) ( ) ( ) ( ) !! !2 !2! !22 !1!1 !222 nn n nn n nn n N SQP ÷⎥⎦ ⎤⎢⎣ ⎡ − −−−− −==                           ( ) ( ) ( ) ( ) ( ) ( ) ⎥⎦ ⎤⎢⎣ ⎡ − −−−− −= !2! !22 !1!1 !22 !2 !!2 nn n nn n n nn ,证毕.    更一般的,我们有以下定理.    定理 5 从零点出发在数轴 x上一维随机游走,设每一步移动的距离均为一个单位, 每一次移动向右走为 ,向左走的概率为 ,p q 1=+ qp .设事件R :在上述随机游走中 总步数为 , ,最后到了点 ,n2 *Nn∈ a na 2≤ ,且仅仅出发时经过了零点,途中没有经 过零点.则  ( ) ( ) ( ) ( ) ( ) ( ) ( )⎪⎪ ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎪⎪ ⎨ ⎧ =⎥⎦ ⎤⎢⎣ ⎡ − −−−− −⋅⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ + ≠≡ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ −−⎟⎠ ⎞⎜⎝ ⎛ + ⎟⎠ ⎞⎜⎝ ⎛ −⎟⎠ ⎞⎜⎝ ⎛ + −⋅⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ + ≡ = ++ ++ 0, !2! !22 !1!1 !22 !2 !!2 2 2 2 0),2(mod2 !1 2 2! 2 2 ! 2 ! 2 2 1 2 1 2 2 2 )2(mod\2,0 2 2 2 2 2 2 2 2 a nn n nn n n nnqpan n aan anan anan n qpan n an RP anan anan ，   证明:    首先讨论到达点 的概率 . a ( )1RP 不难证明当 时该事件是不可能发生的（即仅当 , 奇偶性相同时 才有可能发生）. )2(mod\2 an ≡ n2 a 设共向右走了 步,则向左走了k kN − 步,则： 2 2)2( ankaknk +=⇒=−− , 2 2 2 2 2 2 221)( ananan n kNkk n qpCqpCRP +++ − == , 由此可得, ⎪⎩ ⎪⎨ ⎧ ≡ ≡ = +++ )2(mod2 )2(mod\2,0 )( 2 2 2 2 2 2 2 1 anqpC an RP ananan n ， . 接下来,讨论途中不经过零点得概率 ( )2RP .  由于上述讨论中并不需要涉及到每一次移动的先后顺序,所以可以将其看做一个 古典概型.  增加一个步数轴 ,可以将这个问题转化为一个 T 路计数问题:由点 到点 途中的不经过 ( 0,0 ) )( anA ,2 x轴的 T路条数占所有点 ( )0,0 到点 ( )anA ,2 的 T路的比例.  由引理 3,点 ( 到点 的 T路条数 ) )0,0 ( anA ,2 ( ) ! 2 ! 2 !2 1 ⎟⎠ ⎞⎜⎝ ⎛ −⎟⎠ ⎞⎜⎝ ⎛ + = anan nN .  由引理 4,    若 ,点 到点 且中途不经过0>a ( 0,0 ) )( anA ,2 x 轴的 T 路条数即等于点 ( 到点 且中途不经过 )1,1 ( anA ,2 ) x轴的 T 路条数.  点 ( )1,1 到点 ( )anA ,2 且中途经过 x轴的 T 路条数  ( ) !1 2 2! 2 2 !12 2 ⎟⎠ ⎞⎜⎝ ⎛ −−⎟⎠ ⎞⎜⎝ ⎛ + −=′ anan nN ,  则点 到点 且中途不经过( 0,0 ) )( anA ,2 x轴的 T路条数  ( ) ( ) !1 2 2! 2 2 !12 ! 2 ! 2 !2 2 1 2 2 1 2 ⎟⎠ ⎞⎜⎝ ⎛ −−⎟⎠ ⎞⎜⎝ ⎛ + −− ⎟⎠ ⎞⎜⎝ ⎛ −⎟⎠ ⎞⎜⎝ ⎛ + =′−= anan n anan nNNN ,  ( ) ( ) ( ) ( ) ! 2 ! 2 !2 !1 2 2! 2 2 !12 ! 2 ! 2 !2 2 1 2 ⎟⎠ ⎞⎜⎝ ⎛ −⎟⎠ ⎞⎜⎝ ⎛ + ÷ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ −−⎟⎠ ⎞⎜⎝ ⎛ + −− ⎟⎠ ⎞⎜⎝ ⎛ −⎟⎠ ⎞⎜⎝ ⎛ + = anan n anan n anan nRP                       !1 2 2! 2 2 ! 2 ! 2 2 1 2 1 ⎟⎠ ⎞⎜⎝ ⎛ −−⎟⎠ ⎞⎜⎝ ⎛ + ⎟⎠ ⎞⎜⎝ ⎛ −⎟⎠ ⎞⎜⎝ ⎛ + −= anan anan n .  若 ,根据对称性可知, 0qp 1=+ qp A：走了 步后到达点 （点O与点a顺时针方向相距 , 逆时针方向相距 ）, .则： N a a aM − *, NNNa ∈≤ ( ) ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ += ++−−−−++ = ++∑ 2222 1 2 iMaNiMaNiMaNiMaNu i iMaN N qpqpCAP . 证明：这是一种比较复杂的一维随机游走,复杂之处有两个：1、存在绕了几 圈后再到达这一点的可能；2、往顺时针或是往逆时针方向都可能到达这一点. 所 以,在应用一维随机游走是需要进行一些分类与变化. I. 由顺时针到达点a 设事件 ：走了 步,由顺时针到达点a. 1B N 设 沿 顺 时 针 方 向 共 走 了 g 步 , 沿 逆 时 针 方 向 共 走 了 步 , 则h ⎩⎨ ⎧ =+ ∈+=− Nhg NkakMhg , ⎪⎪⎩ ⎪⎪⎨ ⎧ −−= ++= ⇒ 2 2 kMaNh kMaNg . 运用一维随机游走的相关结论,可以得到： ( ) 22 1 2 1 1 iMaNiMaNu i iMaN N u i gNgg N qpCqpCBP iii −−++ = ++ = − ∑∑ == , 其中 { }NuNMuuu ∈≤⋅= ,:max . II. 由逆时针到达点a 设事件 ：走了 步,由逆时针到达点 . 2B N a 设 沿 顺 时 针 方 向 共 走 了 步 , 沿 逆 时 针 方 向 共 走 了 步 , 则m n ⎩⎨ ⎧ =+ ∈+=− Nmn NkakMmn , ⎪⎪⎩ ⎪⎪⎨ ⎧ −−= ++= ⇒ 2 2 kMaNm kMaNn , 运用一维随机游走的相关结论,可以得到： ( ) 22 1 2 1 2 iMaNiMaNv i iMaN N v i nnNn N qpCqpCBP iii ++−− = ++ = − ∑∑ == , 其中 { }NuNMvvv ∈≤⋅= ,:max . 显然,在一次随机游走过程中,以上的 vu = . 综上, ( ) ( ) ( ) 221 iMaNBPBPAP +++= 22 1 222 1 2 iMaNiMaNv i iMaN N iMaNiMaNu i iMaN N qpCqpC ++−− = ++−−++ = ++ ∑∑ += ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ += ++−−−−++ = ++∑ 2222 1 2 iMaNiMaNiMaNiMaNu i iMaN N qpqpC , 其中 { } M aNNuNMuuu −=∈≤⋅= ,:max . 参考文献 [1] 魏宗舒.概率论与数理统计[M].北京：高等教育出版社,1983. [2] 刘次华.随机过程,第四版[M].武汉：华中科技大学出版社,2008. [3] 孙荣恒.趣味随机问题[M].北京：科学出版社,2004. [4] 卢开澄,卢华明.组合数学,第三版[M].北京：清华大学出版社,2002. [5] 曹汝成.组合数学[M].华南理工大学出版社,2006 [6] L.LOVÁSZ. Random walks on graphs: a survey [J].Keszthely (Hungary),1993.