中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 第二章 Markov过程 本章我们先讨论一类特殊的参数离散状态空间离散的随机过 程,参数为T=01,2,…}=N,状态空间为可列S={1,2,…}或有限 S={1,2,…,n}的情况,即讨论的过程为 Markov链。 Markov链最 初由 Markov于1906年引入,至今它在自然科学、工程技术、 生命科学及管理科学等诸多领域中都有广泛的应用。之后我们将 讨论另一类参数连续状态空间离散的随机过程,即纯不连续 Markov过程。 1. Markov链的定义 定义:设随机序列{X(n)n≥0}的状态空间为S,如果对 n∈N,及a,i S,P{X(0) X(n)=in}>0, 有: P{X(n+1)=inX(0)=i,Xx(1)=,…Y(m)=in}= =P(X(n+1)=in X(n)=i,) 则称{X(mn),n≥0}为 Markov链 注1:随机序列{X(m)n≥0}也可记为{Xn;n≥0}。 注2:等式(A)刻画了 Markov链的特性,称此特性为 Markov 性或无后效性,简称为马氏性。 Markov链也称为马氏链 定义:设{Y(n),n≥0}为马氏链,状态空间为S,对于Vi,j∈S, 称
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 第二章 Markov 过程 本章我们先讨论一类特殊的参数离散状态空间离散的随机过 程，参数为 0 T ={0,1,2, } = N ，状态空间为可列 S ={1,2, } 或有限 S ={1,2, ,n} 的情况，即讨论的过程为 Markov 链。Markov 链最 初由 Markov 于 1906 年引入，至今它在自然科学、工程技术、 生命科学及管理科学等诸多领域中都有广泛的应用。之后我们将 讨论另一类参数连续状态空间离散的随机过程，即纯不连续 Markov 过程。 1． Markov 链的定义 定义：设随机序列 {X (n); n 0} 的状态空间为 S ，如果对 n N0 ，及 i 0 ,i 1 , ,i n ,i n+1 S, P{X (0) = i 0 , X (1) = i 1 , , X (n) = i n } 0 ， 有： { ( 1) ( ) } { ( 1) (0) , (1) , , ( ) } 1 1 0 1 n n n n P X n i X n i P X n i X i X i X n i = + = = + = = = = = + + (A) 则称 {X (n); n 0} 为 Markov 链。 注 1：随机序列 {X (n); n 0} 也可记为 {X ; n 0} n 。 注 2：等式（A）刻画了 Markov 链的特性，称此特性为 Markov 性或无后效性，简称为马氏性。Markov 链也称为马氏链。 定义：设 {X (n); n 0} 为马氏链，状态空间为 S ，对于 i, jS ， 称
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 P{X(n+1)=i2n|Y(mn)=1}p,(m) 为马氏链{Y(m)n≥0}在n时刻的一步转移概率。若对于ⅵ,j∈S, 有 P{X(n+1)=nX(m)=n}≡P,(n)≡P 即上面式子的右边与时刻n无关,则称此马氏链为齐次(或时齐 的)马氏链 对于齐次马氏链,我们记P=(p,),称矩阵P为齐次马氏链的 步转移概率矩阵,简称为转移矩阵。 注3:对于马氏链{X(m)n≥0},我们有: P{X(0)=i0,X(1) (n)=1 P{X(n)=n|X(0)=in,X(1)=i1…,X(m-1)=in1} P{X(0)=i0,X(1)=1,…,X(n-1)=in-} P{X(mn)=|X(n-1)=in}.P{X(0)=b,X() =P{X(n)=in|X(m-1)=n}P{X(n-1)=in|X(m-2)=ln2} P{X(1)=1X(0)=}P{X(0)=i} p_(n-1)P 2)…P(0)·P(X(0)=b} 因此,只要得到了马氏链的一步转移概率及初始分布,就可以求 得马氏链的任意前n+1维的联合分布。特别地,若马氏链是齐次 的,则由转移矩阵及初始分布,就可以得到齐次马氏链的任意前 n+1维的联合分布。 注4:一步转移概率满足:
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 { ( 1) ( ) } ˆ ( ) P X n + = i n+1 X n = i n = pi j n 为马氏链 {X (n); n 0} 在 n 时刻的一步转移概率。若对于 i, jS ， 有 n n pi j n pi j P{X (n +1) = i +1 X (n) = i } = ˆ ( ) 即上面式子的右边与时刻 n 无关，则称此马氏链为齐次（或时齐 的）马氏链。 对于齐次马氏链，我们记 ( ) P = pi j ，称矩阵 P 为齐次马氏链的 一步转移概率矩阵，简称为转移矩阵。 注 3：对于马氏链 {X (n); n 0} ，我们有： ( 1) ( 2) (0) { (0) } { (1) (0) } { (0) } { ( ) ( 1) } { ( 1) ( 2) } { ( ) ( 1) } { (0) , (1) , , ( 1) } { (0) , (1) , , ( 1) } { ( ) (0) , (1) , , ( 1) } { (0) , (1) , , ( ) } 0 1 0 0 1 1 2 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1 p n p n p P X i P X i X i P X i P X n i X n i P X n i X n i P X n i X n i P X i X i X n i P X i X i X n i P X n i X i X i X n i P X i X i X n i i i i i i i n n n n n n n n n n n n n n n = − − = = = = = = − = − = − = = = = − = = = − = = = − = = = = = − = = = = = − − − − − − − − − − 因此，只要得到了马氏链的一步转移概率及初始分布，就可以求 得马氏链的任意前 n +1 维的联合分布。特别地，若马氏链是齐次 的，则由转移矩阵及初始分布，就可以得到齐次马氏链的任意前 n +1 维的联合分布。 注 4：一步转移概率满足：
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 P,(n)≥0(,j∈S) ∑P,(m)=1i∈S 注5:若状态空间是有限的,设状态数为n则一步转移矩阵是 n阶方阵,若状态是无限可列的情形,则一步转移矩阵只是形式 上的矩阵。 2.普曼一柯尔莫哥洛夫(C一K)方程 (一)m步转移概率的定义 定义:称pm(n)=P{X(n+m)=jX(n)=为马氏链{X(m)n≥0} 的m步转移概率。在齐次马氏链的情况下,p(n)与n无关,我 们记为p),称 为齐次马氏链的m步转移(概率)矩阵。 显然有: pm(n)≥0(i,j∈S) m=1时,即为一步转移矩阵。 规定: (m)=6
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 = j S i j i j p n i S p n i j S ( ) 1 ( ) 0 ( , ) 注 5：若状态空间是有限的，设状态数为 n 则一步转移矩阵是 n 阶方阵，若状态是无限可列的情形，则一步转移矩阵只是形式 上的矩阵。 2． 普曼－柯尔莫哥洛夫（C－K）方程 （一） m 步转移概率的定义 定义：称 ( ) { ( ) ( ) } ( ) p n P X n m j X n i m i j = + = = 为马氏链 {X(n); n 0} 的 m 步转移概率。在齐次马氏链的情况下， ( ) ( ) p n m i j 与 n 无关，我 们记为 (m) i j p ，称 ( ) ( ) (m) i j m P = p 为齐次马氏链的 m 步转移（概率）矩阵。 显然有： ( ) 1 ( ) ( ) 0 ( , ) ( ) ( ) p n i S p n i j S j S m i j m i j = m =1 时，即为一步转移矩阵。 规定： = = = i j i j pi j n i j 0 1 ( ) (0)
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 (二)切普曼一柯尔莫哥洛夫(C一K)方程 定理:对于m步转移概率有如下的C一K方程 pm"(m)=∑p(m)P(n+m)( 对于齐次马氏链,此方程为: p pmp(,j∈S)(C-K方程 证明:由全概率公式,有: n+r P(X(n+m+r)=jX(n)=i EPX(n+m+r)=j, X(n+m)=kX(n)=i; 2PX(n+m+r)=jX(n+m)=k, X(n)=i; P(X(n+m)=k X(n)=i; XPX(n+m+r)=jX(n+m)=k]P(X(n+m)=k X(n)=i; =∑P(m)P(m+m) 对于齐次马氏链的情形:我们可以写成矩阵的形式即有: P(m+r)= P(m)P(r) 由此推出: P(m)= p(m-p 其中:P=P 由此可知:对于齐次马氏链,如果知道了它的初始分布(0)和 一步转移矩阵P,就可以求得X(m)的所有有限维概率分布。即有:
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 （二）切普曼－柯尔莫哥洛夫（C－K）方程 定理：对于 m 步转移概率有如下的 C－K 方程： ( ) ( ) ( ) ( , ) ( ) ( ) ( ) p n p n p n m i j S k S r k j m i k m r i j = + + 对于齐次马氏链，此方程为： ( , ) ( ) ( ) ( ) p p p i j S k S r k j m ik m r i j = + （C－K 方程） 证明：由全概率公式，有： + = + = + + = + = + = = + = = = + + = + = = = + + = + = = = + + = = = k S r k j m i k k S k S k S m r i j p n p n m P X n m r j X n m k P X n m k X n i P X n m k X n i P X n m r j X n m k X n i P X n m r j X n m k X n i P X n m r j X n i p n ( ) ( ) { ( ) ( ) } { ( ) ( ) } { ( ) ( ) } { ( ) ( ) , ( ) } { ( ) , ( ) ( ) } { ( ) ( ) } ( ) ( ) ( ) ( ) 对于齐次马氏链的情形：我们可以写成矩阵的形式即有： (m r) (m) (r) P = P P + 由此推出： m m m m P = P P = = P = P − ( ) ( ) ( 1) (1) 其中： P = P (1) 由此可知：对于齐次马氏链，如果知道了它的初始分布 (0) 和 一步转移矩阵 P ，就可以求得 X (n) 的所有有限维概率分布。即有：
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 P{X(n1)=i12X(m2)=12…,X(m)=ik}= ∑p).-n"p pm-ipm P(X(0)=j) 上式中各m步转移概率均可由C-K方程求出,利用一步转 移矩阵及初始分布就可以完全确定齐次马氏链的统计性质。 3.马氏链的例子 随机游动: (1)无限制的随机游动: 以x(n)表示时刻n时质点所处的位置,则{X(m),n=0,1,2…}是 一齐次马氏链,其状态空间为S=(…-2,-10,12…},一步转移概 率为 P1:+1=P (i∈S,0<p<1) P1=q=1-p,(i∈S,0<p<1) 0 (i≠i+1,i-1,j∈S) 现在求n步转移概率p": 设n次转移中向右m次,向左m2次,则有 n+J m1(+1)+m2(-1)=j 即有 n+I-l n-J+I =10Pq2,(+j-1是偶数) 0 (n+j-i是奇数) p"={C;pq,(m+j-i是偶数) (n+j-i是奇数)
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 − − − = = = = = = − − − − − − j S n j i n n i i n n i i n n i i k k p p p p P X j P X n i X n i X n i k k k k k k k k { (0) } { ( ) , ( ) , , ( ) } ( ) ( ) ( ) ( ) 1 1 2 2 1 1 2 1 1 2 1 2 2 1 1 1 上式中各 m 步转移概率均可由 C－K 方程求出，利用一步转 移矩阵及初始分布就可以完全确定齐次马氏链的统计性质。 3． 马氏链的例子 ⚫ 随机游动： （1） 无限制的随机游动： 以 X (n) 表示时刻 n 时质点所处的位置，则 {X(n), n = 0,1,2} 是 一齐次马氏链，其状态空间为 S ={ ,−2,−1,0,1,2, } ，一步转移概 率为： = + − = = − = − + 0 , ( 1, 1, ) 1 , ( , 0 1) , ( , 0 1) 1 1 p i i i j S p q p i S p p p i S p i j i i i i 现在求 n 步转移概率 (n) ij p ： 设 n 次转移中向右 m1 次，向左 m2 次，则有 2 , ( 1) ( 1) 2 1 2 1 2 1 2 n j i m n j i m m m j i m m n − + = + − = + + − = − + = 即有： + − + − = + − + − − + 0 , ( ) , ( ) 2 2 2 ( ) 是奇数 是偶数 n j i C p q n j i p n j i n j i n j i n n i j + − + − = 0 , ( ) , ( ) 2 2 2 ( ) 是奇数 是偶数 n j i C p q n j i p n n n n n ii