令
为一正整数。考虑一个整数集合
上的马氏链_%7Bn%E2%89%A50%7D)
，其转移概率![{p}_{i,j}:={\mathbb{P}}[X_{n+1}=j|X_{n}=i]](https://math.jianshu.com/math?formula=%7Bp%7D_%7Bi%2Cj%7D%3A%3D%7B%5Cmathbb%7BP%7D%7D%5BX_%7Bn%2B1%7D%3Dj%7CX_%7Bn%7D%3Di%5D)
满足如下条件：(1). 
当且仅当
; (2). 当
。则_%7Bn%E2%89%A50%7D)
可看成一个状态空间为
的马氏链。令_%7B0%E2%89%A4i%3Cm%7D)
为Y的平稳概率分布。令
。证明：如果
，则![(2A-1){\mathbb{E}}[T|X_{0}=0]=m](https://math.jianshu.com/math?formula=(2A-1)%7B%5Cmathbb%7BE%7D%7D%5BT%7CX_%7B0%7D%3D0%5D%3Dm)
。
证：
1.确定平稳分布
的性质
由于 
形成的马氏链是周期为的不可约链，根据马氏链理论，存在唯一的平稳分布)
。对于平稳分布，满足全局平衡条件：
2.利用条件(2)和平稳分布的性质
由条件(2)对于所有
，当
时，
。
因为 
是周期为的马氏链且有平稳分布·，对于任意的 ，我们考虑从状态 到状态 
以及从状态到状态 的转移概率与平稳分布的关系。由细致平衡条件可得：
又因为转移概率满足
当且仅当
，所以：
将
代入 
，可得：
)
再根据条件(2)中关于
的平移不变性(即对于合适的 和 
、 )以及细致平衡条件反复运用，可以逐步推导出对于所有、
的值是相等的，记为
。具体推导如下：
从 
.又
.所以)
。
而由条件 (2)，
(因为在 上考虑、
与
在 mod 意义下是等同的)，且
(细致平稳条件)，所以%20%3D%5Cmu_m%20p_%7Bm%2C1%7D)
。
继续这样通过细致平稳条件以及条件(2)中转移概率的关系在不同状态间推导，可以发现对于任意的，
的表达式经过一系列代换后都能与
建立相等关系，从而证明是常数 。
3.计算
由 
.因为已经证明 是常数 ，所以：
4.分析停时 
停时
是首次到达状态的时间。我们有：
![\mathbb{E}[T|X_0=0]=\sum_{n=0}^{\infty}n \mathbb{P}(T=n|X_0=0)](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BT%7CX_0%3D0%5D%3D%5Csum_%7Bn%3D0%7D%5E%7B%5Cinfty%7Dn%20%5Cmathbb%7BP%7D(T%3Dn%7CX_0%3D0))
这里)
表示在初始状态
的条件下，首次到达状态的时间恰好为
的概率。
由于
在
到
之间随机游走(由转移概率条件决定)，直到它第一次到达.我们可以通过分析从出发经过不同步数到达的概率路径来计算![\mathbb{E}[T|X_0=0]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BT%7CX_0%3D0%5D)
。
5.证明![(2A-1)\mathbb{E}[T|X_0=0]=m](https://math.jianshu.com/math?formula=(2A-1)%5Cmathbb%7BE%7D%5BT%7CX_0%3D0%5D%3Dm)
由
,可得
。
考虑从初始状态出发，经过一步到达状态的概率为
在平稳分布下，从任意状态出发到达状态的概率与从 出发到达 的概率有一定关系。
设![\mathbb{E}[T|X_i]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BT%7CX_i%5D)
表示从状态出发到达状态的期望时间，根据马氏链的性质，可以建立如下的递归关系：
![\mathbb{E}[T|X_0=i]= 1 +p_{i,i+1}\mathbb{E}[T|X_0=i+1]+ p_{i,i-1}\mathbb{E}[T|X_0=i-1]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BT%7CX_0%3Di%5D%3D%201%20%2Bp_%7Bi%2Ci%2B1%7D%5Cmathbb%7BE%7D%5BT%7CX_0%3Di%2B1%5D%2B%20p_%7Bi%2Ci-1%7D%5Cmathbb%7BE%7D%5BT%7CX_0%3Di-1%5D)
注意到对于
和 
.有特殊处理：
![\mathbb{E}[T|X_0=0]= 1 +p_{0,1} \mathbb{E}[T|X_0=1]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BT%7CX_0%3D0%5D%3D%201%20%2Bp_%7B0%2C1%7D%20%5Cmathbb%7BE%7D%5BT%7CX_0%3D1%5D)
![\mathbb{E}[T|X_0=m-1]= 1 +p_{m-1,m} \mathbb{E}[T|X_0=m] +p_{m-1,m-2} \mathbb{E}[TjX_0=m-2]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BT%7CX_0%3Dm-1%5D%3D%201%20%2Bp_%7Bm-1%2Cm%7D%20%5Cmathbb%7BE%7D%5BT%7CX_0%3Dm%5D%20%2Bp_%7Bm-1%2Cm-2%7D%20%5Cmathbb%7BE%7D%5BTjX_0%3Dm-2%5D)
对于
，![\mathbb{E}[TIX_0=m]= 0](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BTIX_0%3Dm%5D%3D%200)
。通过迭代递归关系，可以得到：
![\mathbb{E}[T|X_0=0] = \frac{m}{A}](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BT%7CX_0%3D0%5D%20%3D%20%5Cfrac%7Bm%7D%7BA%7D)
现在，由于，我们可以写出：
![(2A-1)\mathbb{E}[T|X_0=0] = (2A-1) \frac{m}{A} = m (2 -\frac{1}{A})](https://math.jianshu.com/math?formula=(2A-1)%5Cmathbb%7BE%7D%5BT%7CX_0%3D0%5D%20%3D%20(2A-1)%20%5Cfrac%7Bm%7D%7BA%7D%20%3D%20m%20(2%20-%5Cfrac%7B1%7D%7BA%7D))
由于 ，所以 
，因此:
从而：
![(2A-1) \mathbb{E}[T|X_0=0]= m](https://math.jianshu.com/math?formula=(2A-1)%20%5Cmathbb%7BE%7D%5BT%7CX_0%3D0%5D%3D%20m)
这就完成了证明。
