多维随机游走及应用
摘要
本文从一维和二维随机游走开始探究,基于组合数学和概率论的有关理论,利用Bernoulli概型及其叠加推导得到了从一确定点出发到达任意随机点的概率；然而在三维随机游走问题上,不能直接利用Bernoulli概型,因而首先引入了一个有放回的摸球问题,再通过该问题得到三维随机变量的分布概型,从而解决了三维随机游走中到达任意随机点的概率问题,并且通过这个思想推导了多维随机游走的相关结论.最后,本文将得到的结论应用在环形随机游走中，得到相关结论.
关键字：多维随机游走 多项式系数 环形随机游走
正文： 引言：
“随机游走”（random walk）是指基于过去的表现,无法预测将来的发展步骤和方向.随机游走问题最早来源于“莱茵街的醉汉”问题：一个醉汉从酒店出发,向左走和向右走分别有一个概率,那么他回到家的概率是多少？这是一个有趣的概率问题,引起了我的兴趣.同时,在思考解决这个问题的基础上,我想是否也可以解决在二维坐标平面内的随机游走问题,甚至是在多维空间内的？在环上进行随机游走又是怎么样的呢？随后我去查阅了有关方面的内容,其中一维随机游走在随机过程中有给出一些结论,而二维,多维随机游走的结论却很少甚至空白；环型随机游走也没有结论.于是,我试图去解决这些问题.
本文的主要理论思想是Bernoulli概型及多维随机变量分布 随机游走理论在实际生活中有广泛的应用,如股票价格的游走模型“R/S分析法” 从对ＥＭＨ的产生及其发展讨论出发,从分形的角度探讨市场特
性的分形市场分析方法及其所反映的市场特性；应用基于边缘检测的随机游走算法对多车辆视频进行精确车辆检测等等.这些也都是今后研究的潜在方向.
本文中,我们假设所讨论的随机过程均为离散的,即每一步之间都是相互独立的.每一次沿坐标轴移动一个单位.
基本理论
1． 一维随机游走
一维随机游走是最简单的,也是最基础的. 由于每一步之间都相互独立,并且每一步有且只有两种可能结果,每种可能情况发生的概率之和为1,所以它符合Bernoulli概型.
定理1：假设从零点出发在数轴x上一维随机游走, 向右走的概率为p,向左走的概率为q,且p,q>0,p+q=1.设事件A：共走了N步,N∈N*,到达了点
a,a≤N. 则：
\a(mod2)⎧0,N≡
⎪
. P(A)=⎨N+aN+aN−a
222⎪⎩CNpq，N≡a(mod2)
证明：
以xn表示第n步后点所在的坐标,则有xn=xn−1+(−1)δn,当第n步为向右时
δn=0,当第n步为向左时δn=1.则xN=∑(−1)δi=α−β.其中α为δi=0的个
i=1
N
数,β为δi=1的个数.则有α−β=a,α+β=N,N−a=2β.故N≡a(mod2).
∴(1)： N≡\a(mod2)时,P(A)=0 . (2): N≡a(mod2)时,
设向右走了k步,则向左走了N−k步,则：k−(N−k)=a⇒k=
N+a2N
N+a2
N−a2
N+a
2.
∴P(A)=Cpq
kN
kN−k
=Cpq,
\a(mod2)⎧0,N≡⎪
综上,P(A)=⎨N+aN+aN−a.
222⎪⎩CNpqN≡a(mod2)
推论1.假设一点从点i出发,在数轴x上一维随机游走, 向右走的概率为p,向左走的概率为q,且p,q>0,p+q=1. 设事件A′：共走了N步,N∈N*,到达了点j,j−i≤N. 则
\j−i(mod2)⎧0,N≡
⎪
. P(A′)=⎨N+(j−i)N+(j−i)N−(j−i)
2⎪p2q2ٛN≡j−i(mod2)⎩CN
此后,我们自然可以想到另外一个问题,在前N步内到达点a的概率是多少？
推论2：从零点出发在数轴x上一维随机游走, 向右走的概率为p,向左走的概率为q,且p,q>0,p+q=1. 设事件A′′：在N步之内（包括第N步）到达了点a,a≤N,N∈N*. 则
P(A′′)=∑C
i=aN
i+a
2i
p
i+a2
q
i−a2
,其中i≡a(mod2).
证明：
事件A′′：在N步之内（包括第N步）到达点a,即在第a步,第a+2步,……,第N步（N≡a(mod2)）或第N−1步（N≡\a(mod2)）中的一步或几步中到达点a.根据定理1,第i步（i≥a,i≡a(mod2)）到达点a的概率为C
i+a
2i
p
i+a2
q
i−a2
.所以,
在N步之内（包括第N步）到达点a的概率即为所有可能情况发生的概率之和,即
P(A′′)=∑C
i=a
N
i+a2i
p
i+a2
q
i−a2
,i≡a(mod2).
2.二维随机游走
与一维随机游走不同的是,二维随机游走的每一步由一维中的2个方向变成了二维中的4个方向,故不能简单地使用Bernoulli概型.但是,我们仍然可以通过两个Bernoulli概型的叠加得到二维随机游走的结论.
定理2：一质点在二维坐标系xOy上进行随机游走,从原点出发,向右走的概率为p,向左走的概率为q,向上走的概率为m,向下走的概率为n,且
p,q,m,n>0,p+q+m+n=1.
设事件B：共走了N步,N∈N*,到达了点(a,b)（假设a,b>0）,a+b≤N.则：
\a+b(mod2)⎧0,N≡
⎪⎪⎪i+ai+ai−aN−i+bN−i+bN−i−b
⎤. P(B)=⎨N−b⎡iiN−i222222
()()++⋅⋅CpqmnCpqCmn⎥ii⎪∑⎢N
⎦⎪i=a⎣
⎪⎩N≡a+b(mod2),i≡a(mod2)
证明：
设总步数为N,其中沿x轴方向走了G步,沿y轴方向走了H步.
∵G+H=N
∴a+b≤N ∴a≤N−b
以xn表示第n步后点所在的坐标,则有xn=xn−1+(−1)δn,当第n步为向右时
δn=0,当第n步为向左时δn=1.则xG=∑(−1)δi=α−β.其中α为δi=0的个
i=1
G
数,β为δi=1的个数.则有α−β=a,α+β=G,G−a=2β.故G≡a(mod2).
I.G≡\a(mod2)时, P(B)=0.
即此时是不可能到达(a,b)的；同时,若G≡\a(mod2),有G≡\−a(mod2),即
G+a
不是整数,在组合中这是不符合要求的,故此时,P(B)=0. 2
II.G≡a(mod2),
这种情况下是可能到达(a,b)点的, (1) G=a,H=N−a.
A1：x轴方向走了a步,y轴方向走了N−a步,共N步.则：
a
(p+q)(m+n)P(A1)=CN
a
N−a
.
B1：x轴方向走的a步均向右.则：
aa0
P(B1)=Capq=pa.
a
(p+q)(m+n)∴P(A1B1)=P(A1)P(B1A1)=CN
a
N−a
⋅pa.
C1：y轴方向走了N−a步,到了b.则： 假设向上走了j步,有 j−(N−a−j)=b⇒j=
N−a+b
, 2
N−a+b2
P(C1)=C
jN−a
mn
jN−a−j
=C
N−a+b2N−a
mn
N−a−b2
,
m
N−a+b2
G
(p+q)(m+n)⋅C∴P(A1C1)=P(A1)P(C1A1)=CN
G
N−a+b
2N−a
n
N−a−b2
.
(2) G=N−b,H=b.
A2： y轴方向只走了b步,x轴方向走了N−b步,共N步.则：
b
(p+q)P(A2)=CN
N−b
(m+n)b.
B2：x轴方向走了N−b步,到了a.则： 假设向右走了i步,有 i−(N−b−i)=a⇒i=
N+a−b
, 2
P(B2)=C
iN−b
pq
iN−b−i
=C
N+a−b2N−b
p
N+a−b2
q
N−a−b2
.
C2：若y轴方向走的b步均向上.则：
bb0
P(C2)=Cbmn=nb.
∴P(A2B2C2)=P(A2)⋅P(B2C2A2)=P(A2)P(B2A2)P(C2A2)
=C
bN
(p+q)(m+n)
N−b
b
⋅C
N+a−b2N−b
p
N+a−b2
q
N−a−b2
⋅nb.
(3) a≤G≤N−b,b≤H≤N−a.
A3： x轴方向走了G步,y轴方向走了H步,共N步.则：
G
(p+q)(m+n)P(A3)=CN
G
N−G
.
B3：x轴方向走了G步,到达a.则： 假设向右走了g步,有 g−(G−g)=a⇒g=
G+a
, 2
P(B3)=Cpq
gG
g
G−g
=C
G+a2G
p
G+a2
q
G−a2
.
C3：y轴方向走了H步,到达b.则： 假设向上走了h步,有 h−(H−h)=b⇒h=
H+b
. 2
P(C3)=Cmn
hH
h
H−h
=C
N−G+b2N−G
m
N−G+b2
n
N−G−b2
.
∴P(A3B3C3)=P(A3)⋅P(B3C3A3)=P(A3)P(B3A3)P(C3A3) =C
GN
(p+q)(m+n)
G
N−G
⋅C
G+a2G
p
G+a2
q
G−a2
⋅C
N−G+b2N−G
m
N−G+b2
n
N−G−b2
.
\a+b(mod2)⎧0,N≡⎪N−bi+ai+ai−aN−i+bN−i+bN−i−b
⎤⎪⎡iiN−i
∴P(B)=⎨∑⎢CN(p+q)(m+n)⋅Ci2p2q2⋅Ci2m2n2⎥,
⎦⎪i=a⎣
⎪N≡a+b(mod2),i≡a(mod2)⎩
推论3. 一质点在二维坐标系xOy上进行随机游走,从点(c,d)出发,向右走的概率为p,向左走的概率为q,向上走的概率为m,向下走的概率为n,且
p,q,m,n>0,p+q+m+n=1.
设事件B′：共走了N步,N∈N*,到达了点(a,b)（假设a,b>0）,a+b≤N.则：
\(a+b)−(c+d)(mod2),⎧0,i≡⎪N−(b−d)i+(a−c)i+(a−c)i−(a−c)N−i+(b−d)N−i+(b−d)N−i−(b−d)
⎡i⎤⎪iN−i
P(B′)=⎨∑⎢CN(p+q)(m+n)⋅Ci2p2q2⋅Ci2m2n2⎥,
⎦⎪i=a−c⎣
⎪i≡(a+b)−(c+d)(mod2).⎩
3. 2n维随机游走
在得到了二维随机游走的结果后,由于2n维可以看作是n个二维情况的简单叠加,因此我们可以以类似的方法将几个Bernoulli概型进行叠加,从而得到2n
k
维随机游走的结论.然而,由于每一次使用Bernoulli概型时,它的分布CNpkqN−k
中的N总是一个变量,所以得到的表达式是十分复杂的,也不易于计算.因此,本文中并没有给出计算.
4. 三维随机游走
三维随机游走无法简单地像二维随机游走直接将几个Bernoulli概型进行叠加,因为它需要的是一个三维随机变量的分布概型,故我们用最基本的方法来推出三维随机游走模型.
首先,我们引出一个有放回摸球问题：
引理1：一个袋子中有A个白球,B个黑球,D个红球（各球形状大小均无差异）. 现有放回地从袋子中摸球,设事件S：在n次摸球中摸到a个白球,b个黑
a,ba,b
⋅paqbrn−a−b=Gn⋅paqb[1−(p+q)]球,（n−a−b个红球）,则P(S)=Gn
(
n−(a+b)
).
证明：由于摸球是有放回的,不妨假设每个球都是有编号的,那么每次摸球都有(A+B+D)种可能的情况,即每一次摸球有(A+B+D)个样本点；又因为共摸了n次,所以共有(A+B+D)个样本点.
n
ab
事件S是n次摸球中摸到a个白球,b个黑球,这样的组合有Cn⋅Cn−a个.
a,b
为了表示方便,我们先引入一个符号Gn,
a,bab
Gn=Cn⋅Cn−a=
(n−a)!=n!n!
. ⋅
a!n−a!b!n−a−b!a!b!n−a−b!
a,b
即这样的组合有Gn个.
a,b而对于每一种组合情况,又都有AaBbDn−a−b个样本点,而且这Gn种情况又a,b
是两两互斥的,所以事件S中有Gn⋅AaBbDn−a−b个样本点.再由古典概型的定义
可得：
P(S)=
a,b
Gn⋅AaBbDn−a−b
A+B+Dn
.
又假设摸到白球的概率是p,摸到黑球的概率是q,摸到红球的概率是r,必然有p+q+r=1,r=1−(p+q).根据古典概型的定义,可知
p=
BDA
,q=,1−(p+q)=r=,则：
A+B+DA+B+DA+B+D
P(S)=
a,b
Gn⋅AaBbDn−a−b
A+B+D⋅A+B+D⋅A+B+Da
b
n−a−b
a,ba,b
=Gn⋅paqbrn−a−b=Gn⋅paqb[1−(p+q)]
n−(a+b)
.
这与二项分布Cnkpkqn−k=b(k;n,p)是很类似的,所以我们不妨记
a,bab
Gnpq[1−(p+q)]
n−(a+b)
=b(a,b;n,p,q).
现在,我们在此基础上讨论三维随机游走问题.
定理3：一质点在一个三维坐标空间Oxyz上随机游走,从原点出发.向x轴正方向移动的概率为p,向x轴负方向移动的概率为q,向y轴正方向移动的概率为
m,向y轴负方向移动的概率为n,向z轴正方向移动的概率为s,向z轴负方向移动的概率为t,且p,q,m,n,s,t>0,p+q+m+n+s+t=1.设事件T：共走了N步,N∈N*,到达了点(a,b,c)（假设a,b,c>0）,a+b+c≤N.则：
\a+b+c(mod2)⎧0,N≡⎪⎪
g+ag+ag−ah+bh+bh−b⎪N−(b+c)N−(a+c)⎡ghN−(g+h)g,h⎪⋅Cg2p2q2⋅Ch2p2q2⋅P(T)=⎨∑∑⎢GN(p+q)(m+n)(s+t)
⎪g=ah=b⎣
⎪N−(g+h)+cN−(g+h)+cN−(g+h)−c⎤
2⎪CN−(g+p2q2⎥,N≡a+b+c(mod2),g≡a(mod2),h≡b(mod2).h)
⎪⎦⎩
证明：
设事件A：沿x轴方向走了g步,沿y轴方向走了h步,沿z轴方向走了j步. 显然有j=N−(g+h),且需a≤g≤N−(b+c), 同理,b≤h≤N−(a+c),c≤j≤N−(a+b). 根据引理1,可知：
g,h
(p+q)(m+n)(s+t)P(A)=GN
g
h
N−g−h
,
设事件B：沿x轴方向走了g步的情况下,x轴上到坐标a. 设向a所在方向移动了i步,则i−(g−i)=a⇒i=
P(BA)=Cpq
ig
ig−i
g+a
. 2
=C
g+a2g
p
g+a2
q
g−a2
.
同理,
事件C：沿y轴方向走了h步的情况下,y轴上到坐标b.
P(CA)=C
h+b2h
m
h+b2
n
h−b2
.
事件D：沿z轴方向走了j步的情况下,z轴上到坐标c
P(DA)=C
j+c2j
s
j+c2
t
j−c2
=C
N−(g+h)+c
2N−(g+h)
s
N−(g+h)+c
2
t
N−(g+h)−c
2
.
综上所述,
∴P(T)=
N−(b+c)N−(a+c)
∑∑
g=a
h=b
g+ag+ag−ah+bh+bh−b
⎡g,hghN−(g+h)
⋅Cg2p2q2⋅Ch2p2q2⋅⎢GN(p+q)(m+n)(s+t)
⎣N−(g+h)−c
2
C
N−(g+h)+c
2N−(g+h)
p
N−(g+h)+c
2
q
⎤⎥. ⎦
推论3：一质点在一个三维坐标空间Oxyz上随机游走,从点(d,e,f)出发.向x轴正方向移动的概率为p,向x轴负方向移动的概率为q,向y轴正方向移动的概率为m,向y轴负方向移动的概率为n,向z轴正方向移动的概率为s,向z轴负方向移动的概率为t,且p,q,m,n,s,t>0,p+q+m+n+s+t=1.设事件T：共走了
N步,N∈N*,到达了点
(a,b,c)
（假设
a,b,c>0,a≥d,b≥e,c≥f）,a+b+c≤N.则：
⎧
⎪
\(a+b+c)−(d+e+f)(mod2)⎪0,N≡⎪⎪
g+(a−d)g+(a−d)g+(a−d)⎪⎪N−[(b+c)−(e+f)]N−[(a+c)−(d+f)]⎡g,hghN−(g+h)
P(T)=⎨⋅Cg2p2q2⋅⎢GN(p+q)(m+n)(s+t)∑∑h=b−e⎣⎪g=a−d
⎪h+(b−e)h+(b−e)h−(b−e)N−(g+h)+(c−f)N−(g+h)+(c−f)N−(g+h)−(c−f)
⎤222⎪C2p2q2⋅Cpq⎥,N−(g+h)
⎪h
⎦
⎪⎪⎩N≡(a+b+c)−(d+e+f)(mod2),g≡a(mod2),h≡b(mod2).
5. 多维随机游走
首先,和三维随机游走一样,我们先将Bernoulli概型推广至n维随机变量分布.
引理2： 一个袋子中有A1个a1球,A2个a2球,…,Ak个ak球（各球形状大小均无差异）. 现有放回的从袋子中摸球, 设事件M：在n次摸球中摸到B1个a1
G
球,B2个a2球,…,Bk个ak球,则 P(M)=
B1,B2,...,Bk
n
k
⋅∏Aj
j=1n
k
⎛⎞
A⎜∑j⎟⎝j=1⎠
.
证明：由于是有放回的,不妨假设每个球都是有编号的,那么每次摸球都有
∑A
j=1
k
j
种可能的情况,每次有∑Aj个样本点,又因为共摸球n次,所以样本点共有
j=1
k
⎛k⎞
⎜∑Aj⎟个. ⎝j=1⎠
CnB1CnB2⋅⋅⋅CnBk=Gn1,
B,B2,...,Bk
n
=
n!
. kk
⎛⎞(Bi!)⋅⎜n−∑Bi⎟∏i=1i=1⎝⎠⋅∏Aj
j=1nk
G
P(M)=
B1,B2,...,Bkn
k
⎛⎞⎜∑Aj⎟⎝j=1⎠
,
设pj=
Aj
∑A
i=1
k
,则：
i
P(M)=G
B1,,B2,...,Bkn
⋅∏pjj.
j=1
k
B
由此,我们不难得到多维随机游走的结果.
可以通过类似于三维的方法证明以下：
猜想：假设在一个n维坐标空间上随机游走,从原点出发.向xi轴正方向移动的概率为pi,向xi轴负方向移动的概率为qi,其中i∈[1,...,n],且
pi,qi>0,
∑(p
i=1
n
i
+qi)=1.设事件R：共走了N步,N∈N*,到达了点
n
(a1,a2,...,an),其中ai表示在坐标轴xi上的坐标（假设ai>0）,∑ai≤N.记
i=1
λ=∑ai,则：
i=1
n
P(R)=
N−λ−a1N−λ−a2
∑∑
j1=a1
...
N−λ−anjn=an
j2=a2
∑
aiji+aiji−ai
⎡B1,,B2,...,BnnBj⎛ji+
222Cpq⋅∏pj⋅∏⎜⋅⎢Gnji⎜
j=1⎢⎝⎣⎞⎤
⎟⎥. ⎟⎠⎥⎦
6．一维随机游走的再讨论
首先，我们需要两条组合数学中T路的基本定理.
引理3 若整点A(a,α)和整点B(b,β)满足T条件,那么A到B的T路条数为
(b−a)!
⎛b−aβ−α⎞⎛b−aβ−α⎞
+−⎜⎟!⋅⎜⎟!2222⎝⎠⎝⎠
.
引理4 （反射原理） 若整点A(a,α)和整点B(b,β)满足T条件,且α>0,β>0,则由A(a,α)到B(b,β)的经过x轴的T路条数等于由A′(a,−α)到B(b,β)得T路条数,
为
(b−a)!
⎛b−aβ+α⎞⎛b−aβ+α⎞
+−⎜⎟!⋅⎜⎟!
2⎠⎝22⎠⎝2
.
这条定理的具体证明并不复杂,可以参见参考书目[5].
定理4 从零点出发在数轴x上一维随机游走,设每一步移动的距离均为一个单位,每一次移动向右走和向左走的概率均为1/2.现已知在一次随机游走中向左走的步数与向右走的步数均为n,即总步数为2n,最后回到了零点.设事件Q:在上述随机游走中仅仅出发时和最后一步经过了零点.则
P(Q)=
(2n−2)!⎤. 2n!n!⎡(2n−2)!−2n!⎢n−1!n−1!n!n−2!⎣⎦
证明: 根据引理3和引理4可知, 由A(a,α)到B(b,β)的不经过x轴的T路条数S等于
(b−a)!
⎛b−aβ−α⎞⎛b−aβ−α⎞⎛b−aβ+α⎞⎛b−aβ+α⎞
+−+−⎜⎟!⋅⎜⎟!⎜⎟!⋅⎜⎟!
2⎠⎝22⎠⎝22⎠⎝22⎠⎝2
−
(b−a)!
.
而所求的路即为从A1(1,1)到B1(2n−1,1)和从A2(1,−1)到B2(2n−1,−1)的不经过x轴的T路条数之和, S1=
(2n−2)!−(2n−2)!,S=(2n−2)!−(2n−2)!,
n−1!n−1!n!n−2!2n−1!n−1!n!n−2!
⎡(2n−2)!(2n−2)!⎤.而由A(a,α)到B(b,β)的T路条数N为(2n)!,
−所以S=2⎢⎥n!n!⎣n−1!n−1!n!n−2!⎦所以P(Q)=
⎡(2n−2)!(2n−2)!⎤÷(2n)! S
=2⎢−⎥N⎣n−1!n−1!n!n−2!⎦n!n!
=
(2n−2)!⎤,证毕. 2n!n!⎡(2n−2)!
−⎥2n!⎢−−−n1!n1!n!n2!⎣⎦
更一般的,我们有以下定理.
定理5从零点出发在数轴x上一维随机游走,设每一步移动的距离均为一个单位,每一次移动向右走为p,向左走的概率为q,p+q=1.设事件R:在上述随机游走中总步数为2n,n∈N*,最后到了点a,a≤2n,且仅仅出发时经过了零点,途中没有经过零点.则
⎧⎪
⎪0,2n≡\a(mod2)⎪⎪⎡a⎞⎛a⎞⎤⎛
+−!nn⎜⎟⎜⎟!⎥n+an+a222n⎪⎢⎞⎛11⎪2⎠⎝2⎠⎝⎥，2n≡a(mod2),a≠0 P(R)=⎨⎜2n+a⎟p2q2⋅⎢−
⎟⎜⎢22n⎛2n+a⎞!⎛2n−a−1⎞!⎥⎪⎝2⎠⎜⎟⎜⎟⎥⎢⎪22⎝⎠⎝⎠⎦⎣
⎪
2n⎞2n+a2n+a2n!n!⎡(2n−2)!⎪⎛(2n−2)!⎤,a=0⎜2n+a⎟p2q2⋅−⎪⎜⎢n−1!n−1!n!n−2!⎥⎟2n!⎣⎦⎪⎩⎝2⎠证明:
首先讨论到达点a的概率P(R1).
不难证明当2n≡（即仅当2n,a奇偶性相同时\a(mod2)时该事件是不可能发生的才有可能发生）.
设共向右走了k步,则向左走了N−k步,则：
2n+a
k−(2n−k)=a⇒k=
2,
P(R1)=Cpq
k2n
k
N−k
=C
2n+a22n
p
2n+a2
q
2n+a2
,
\a(mod2)⎧0,2n≡⎪
由此可得,P(R1)=⎨2n+a2n+a2n+a.
222⎪q，2n≡a(mod2)⎩C2np
接下来,讨论途中不经过零点得概率P(R2).
由于上述讨论中并不需要涉及到每一次移动的先后顺序,所以可以将其看做一个
古典概型.
增加一个步数轴,可以将这个问题转化为一个T路计数问题:由点(0,0)到点
A(2n,a)途中的不经过x轴的T路条数占所有点(0,0)到点A(2n,a)的T路的比例. 由引理3,点(0,0)到点A(2n,a)的T路条数
N1=
(2n)!
a⎞⎛a⎞⎛
⎜n+⎟!⎜n−⎟!
2⎠⎝2⎠⎝
.
由引理4,
若a>0,点(0,0)到点A(2n,a)且中途不经过x轴的T路条数即等于点(1,1)到点
A(2n,a)且中途不经过x轴的T路条数. 点(1,1)到点A(2n,a)且中途经过x轴的T路条数
′=N2
(2n−1)!
⎛2n+a⎞⎛2n−a⎞
−1⎟!⎜⎟!⎜
22⎝⎠⎝⎠
,
则点(0,0)到点A(2n,a)且中途不经过x轴的T路条数
N2=
N1(2n)!(2n−1)!1
′=, −N2−
a⎞⎛a⎞⎛2n+a⎞⎛2n−a⎞22⎛
−1⎟!⎜n+⎟!⎜n−⎟!⎜⎟!⎜
2222⎝⎠⎝⎠⎝⎠⎠⎝
⎡⎤
⎢1⎥(((2n)!2n)!2n−1)!
⎥÷ −P(R2)=⎢
a⎞⎛a⎞⎛2n+a⎞⎛2n−a⎞⎥⎛a⎞⎛a⎞⎢2⎛!!!1!!+−−n+n−nn⎜⎟⎜⎟!⎜⎟⎜⎟⎟⎜⎟⎜⎢⎝⎥2⎠⎝2⎠⎝2⎠⎝22⎠⎝2⎠⎠⎦⎝⎣a⎞⎛a⎞⎛
⎜n+⎟!⎜n−⎟!
112⎠⎝2⎠⎝. =−
22n⎛2n+a⎞⎛2n−a⎞
−1⎟!⎜⎟!⎜
22⎝⎠⎝⎠
a⎞⎛a⎞⎛
⎜n+⎟!⎜n−⎟!
112⎠⎝2⎠⎝若a
−1⎟!⎜⎟!⎜
22⎝⎠⎝⎠
若a=0,与定理6类似地,P(R2)=综上,
(2n−2)!⎤. 2n!n!⎡(2n−2)!
−⎥2n!⎢⎣n−1!n−1!n!n−2!⎦
⎧⎪
\a(mod2)⎪0,2n≡⎪⎡a⎞⎛a⎞⎤⎛⎪2n+a2n+a2n+a⎢⎜n+⎟!⎜n−⎟!⎥
11⎪2⎠⎝2⎠⎝⎥，P(R)=⎨C2n2p2q2⋅⎢−2n≡a(mod2),a≠0,
+−2na2na22n⎞⎛⎞⎛⎢⎪−1⎟!⎥!⎜⎜⎟⎢⎪⎝2⎠⎝2⎠⎥⎣⎦
⎪2n+a2n+a2n+a
⎪C2p2q2⋅2n!n!⎡(2n−2)!−(2n−2)!⎤,a=0
⎥⎪2n2n!⎢⎣n−1!n−1!n!n−2!⎦⎩证毕.
以上似乎是可以推广至高维的，只需要将T路推广即可.
7. 环形随机游走
根据一维随机游走,我们可以对一种特殊的随机游走模型进行推导——环形随机游走,即在一个封闭环上的随机游走.
定理4：在一个环上,有M个点,各点之间的距离相等,且均为一个单位长度.假设一点从某点O出发,每一次沿环上移动一个单位长度,假设向顺时针方向移动一个单位的概率为p,向逆时针方向移动一个单位的概率为q,且走了N步后到达点a（点O与点a顺时针方向相距a,p,q>0,p+q=1.事件A：
逆时针方向相距M−a）,a≤N,N∈N*.则：
P(A)=∑C
i=1u
N+a+iM
2N
N−a−iMN+a+iM
⎛N+a2+iMN−a2−iM⎜pq+p2q2⎜⎝
⎞⎟. ⎟⎠
证明：这是一种比较复杂的一维随机游走,复杂之处有两个：1、存在绕了几圈后再到达这一点的可能；2、往顺时针或是往逆时针方向都可能到达这一点. 所以,在应用一维随机游走是需要进行一些分类与变化.
I. 由顺时针到达点a
设事件B1：走了N步,由顺时针到达点a.
设沿顺时针方向共走了g步,沿逆时针方向共走了h步,则
N+a+kM⎧=g⎪⎧g−h=kM+a,k∈N⎪2⇒⎨. ⎨
⎩g+h=N⎪h=N−a−kM
⎪2⎩
运用一维随机游走的相关结论,可以得到：
P(B1)=∑Cpq
gi
N
gi
i=1
u
N−gi
=∑C
i=1
u
N+a+iM
2N
p
N+a+iM
2
q
N−a−iM
2
,
其中u=max{u:u⋅M≤N,u∈N} .
II. 由逆时针到达点a
设事件B2：走了N步,由逆时针到达点a.
设沿顺时针方向共走了m步,沿逆时针方向共走了n步,则
N+a+kM⎧=n⎪⎧n−m=kM+a,k∈N⎪2⇒⎨, ⎨
n+m=N−−NakM⎩⎪m=
⎪2⎩
运用一维随机游走的相关结论,可以得到：
P(B2)=∑Cp
ni
N
i=1
v
N−ni
q=∑C
ni
i=1
v
N+a+iM
2N
p
N−a−iM
2
q
N+a+iM
2
,
其中v=max{v:v⋅M≤N,u∈N} . 显然,在一次随机游走过程中,以上的u=v. 综上,P(A)=P(B1)+P(B2) =∑C
i=1u
N+a+iM
2N+a+iM
2
u
N+a+iM
2N
pq
N−a−iM
2
+∑C
i=1
v
N+a+iM
2N
p
N−a−iM
2
q
N+a+iM
2
=∑C
i=1
N+a+iM
2N
N−a−iMN+a+iM
⎛N+a2+iMN−a2−iM⎜p+p2q2q⎜⎝⎞⎟, ⎟⎠
其中u=max{u:u⋅M≤N,u∈N}=
参考文献
N−a
. M
[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.