龚光鲁,钱敏平著应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,2003 第5章时间离散的 Markov链 1 Markov链的概念 1.1定义与 Markov性质 定义5.1随机过程可能取到的值(状态)组成的集合记为S,称为随机过程的状态 空间.随机序列{n:n≥0}称为 Mar koy链,如果这些随机变量都是离散的(状态空间S 至多是一个可数集,即或者S是有限集,或者S可与自然数一一对应),而且对于Vn≥0 及任意状态,j,0,…,in1,都有 P(5n1=j|n=i,5n1=ln1;…,5o=l0)=P(n+1=j|n=1).(5.1 这个性质称为 Markov性质 Markov性的等价性质1 若A为任意形如{0(0)=10,51()=1,…,n(O)=n4}的事件的并,即 A=U{50=bk,51=1k…5m=bnk} 则有 P(5nm=1A5n=1=P(5m=n=) Markov性的等价性质2 进一步还可以证明 Markov性等价于:对于过程在时刻n+1及其以后的时刻所确定的 事件B及等价性质中之A有 P(BA.5n=1)=P(B5n=1) P(ABE,=i)=P(AI5m=D)P(Bsm=i) (5.3)式的含意为:如果过程在时刻n处于状态i,那么不管它以前处于什么状态,过 程以后处于什么状态的概率是一样的.这就说明了, Markov链在已知“现在”的条件下,“将 来”与“过去”是条件独立的.我们把它另列为一条性质 Markov性的等价性质3 在已知“现在”的条件下,“将来”与“过去”是条件独立的 Markov性的等价性质4 对Mkov链{n}及m≥Ln≥0及任意状态i,,i,…,ln1,有 P(mnm=儿5n=1,n1=in-1,…,50=6)=P(nm=jn=1)(5.4)
96 龚光鲁，钱敏平著 应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,2003 第 5 章 时间离散的 Markov 链 1 Markov 链的概念 1.1 定义与 Markov 性质 定义５.１ 随机过程可能取到的值(状态)组成的集合记为S , 称为随机过程的状态 空间. 随机序列{ : n ³ 0} n x 称为 Markov 链, 如果这些随机变量都是离散的 (状态空间S 至多是一个可数集, 即或者S 是有限集, 或者S 可与自然数一一对应), 而且对于 "n ³ 0 及任意状态 0 1 , , , , n- i j i L i , 都有 P(xn+1 = j |x n = i,xn-1 = i n-1 ,L,x0 = i 0 ) = ( | ) 1 P j i xn + = xn = . (5. 1) 这个性质称为 Markov 性质. Markov 性的等价性质 1 若 A 为任意形如{ ( ) , ( ) , ., ( ) } 0 = 0 1 = 1 n -1 = n -1 x w i x w i L x w i 的事件的并，即 U L k k k n n k A { i , i , , i } = 0 = 0, 1 = 1, -1 = -1, x x x 则有 ( , ) ( ) 1 1 P j A i P j i xn+ = x n = = x n+ = x n = . (5. 2) Markov 性的等价性质 2 进一步还可以证明 Markov 性等价于：对于过程在时刻 n+1 及其以后的时刻所确定的 事件 B 及等价性质中之 A 有 P(B A, i) P(B i) xn = = xn = . (5. 3) 或 P(AB i) P(A| i)P(B i) x n = = xn = x n = (5. 3)’ （5．3）式的含意为: 如果过程在时刻 n 处于状态 i，那么不管它以前处于什么状态，过 程以后处于什么状态的概率是一样的. 这就说明了，Markov 链在已知“现在”的条件下，“将 来”与“过去”是条件独立的. 我们把它另列为一条性质。 Markov 性的等价性质 3 在已知“现在”的条件下，“将来”与“过去” 是条件独立的. Markov 性的等价性质 4 对 Markov 链{ }n x 及"m ³ 1, n ³ 0 及任意状态 0 1 , , , , n- i j i L i , 有 P(xn+m = j |x n = i,xn-1 = i n -1 ,L,x0 = i 0 ) = P( j | i) xn+m = x n = . (5. 4)
证明对m作归纳法.m=1时即为(5.1)式设m时(5.4)式正确,今证m+1时也正确 P(5n+m+1=n=1,5n1=in1,…,50=10) j,5n1=k|n=1,5 P(S jm=k, n=i, sn-I=i P(5n1=k|5n=i,5 利用归纳法假设及(5.1)式,上式简化为 ∑P(5nm=j15m=k)P(5m=k|n=) f3n+1=k,5n=1)P(n+1=k|5n=1) P(nm+1=j,n+1=k|n=1)=P(nm=j5n=) Markov性的等价性质5 对状态空间S上的任意有界实值函数∫有 E((m米0=10…,n=n)=E(f(5m)kn=Ln)。 (5.1)式是(.5)式的特例,即f(x)=ln(x)的情形.从(5.1)式推广为5.5)式需要 用测度论的基本知识,我们把它略去) 注]第1,2,3,5种等价性质都有与第4种等价性质类似的表达形式,请读者自检. Markov性的等价性质6(最一般的形式) 对于常见的实数集合A,及由随机序列ξn在时刻n及其后的信息所决定的随机变量 nn,恒有 P(mn∈N0=o,…,5n=n)=P(mn∈Nn= E(nm 50=io, m=in))=E(n, 5m =in) 注]这个等价条件的内涵十分丰富,其等价性的证明在测度论中非常典型,本书从略 在以实际问题为背景的 Markov链的研究中,人们最关心的是,经过时间n,过程到达某 些状态的概率有多大,以及需要多长时间才能到达这些状态.这类问题的描述首先涉及 Markov链的转移特性—— Markov链的n步转移概率矩阵族 1.2概率转移矩阵 定义5.2记 Pu(n, 并定义无穷矩阵
97 证明 对m 作归纳法. m=1 时即为(5. 1)式. 设 m 时(5. 4)式正确, 今证 m+1 时也正确. ( | , , , ) 1 1 1 0 0 P j i i i n m n n n = = = = + + - - x x x L x ( , | , , , ) 1 1 1 1 0 0 P j k i i i n m n n n n k = å x + + = x + = x = x - = - L x = ( | , , , , ) 1 1 1 1 0 0 P j k i i i n m n n n n k = å x + + = x + = x = x - = - L x = ´ ( | , , , ) 1 1 1 0 0 P k i i i xn+ = x n = xn - = n- L x = . 利用归纳法假设及(5. 1)式, 上式简化为 ( | ) 1 1 P j k n m n k = å x + + = x + = ( | ) 1 P k i xn+ = x n = ( | , ) 1 1 P j k i n m n n k = å x + + = x + = x = ( | ) 1 P k i xn+ = x n = ( , | ) 1 1 P j k i n m n n k = å x + + = x + = x = ( ,| ) 1 P j i = xn +m+ = x n = . Markov 性的等价性质 5 对状态空间 S 上的任意有界实值函数 f 有 ( ( ) , , ) ( ( ) ) n 1 0 0 n n n 1 n n E f = i = i = E f = i + + x x L x x x 。 (5. 5) ( (5. 1) 式是 (5. 5)式的特例, 即 ( ) ( ) { } f x I x = j 的情形. 从 (5. 1)式推广为(5. 5)式需要 用测度论的基本知识, 我们把它略去). [注] 第 1，2，3，5 种等价性质都有与第 4 种等价性质类似的表达形式，请读者自检． Markov 性的等价性质 6 （最一般的形式 ） 对于常见的实数集合L ，及由随机序列 m x 在时刻n 及其后的信息所决定的随机变量 hn， 恒有 ( , , ) ( ) n 0 0 n n n n n P h Î Lx = i L x = i = P h Î Lx = i 或 ( , , )) ( ) n 0 0 n n n n n E h x = i L x = i = E h x = i ． [注] 这个等价条件的内涵十分丰富， 其等价性的证明在测度论中非常典型，本书从略. 在以实际问题为背景的 Markov 链的研究中，人们最关心的是, 经过时间 n, 过程到达某 些状态的概率有多大，以及需要多长时间才能到达这些状态. 这类问题的描述首先涉及 Markov 链的转移特性——Markov 链的 n 步转移概率矩阵族． １．２ 概率转移矩阵 定义５．２ 记 pij(n,m) =， 并定义无穷矩阵
P(n, m)=(Pi(n, m)) 由于此无穷矩阵的分量都是非负的且不超过1,易见这种无穷矩阵的乘法满足结合律.又因 为 A1(i= P 0(i≠j) ( Kronecker记号) 所以P(n,n)=I(无穷单位矩阵)特别地,P(n,n+1)称为时刻n(到时刻n+1)的概率转移 矩阵而P(n,n+k)就称为从n出发的k步概率转移矩阵. 命题5.3概率转移矩阵族满足以下的性质 记1为分量全是1的无穷行向量(矩阵),其维数与此 Markov链的状态数一致.我们有 (P.1)0≤p(n,m)≤1,P(n,m)1=1.(上标T表示转置运算) (P.2)( Chapman-Ko I mogorov方程)对于Vl≥m≥n有 P(n, 1)=P(n, m) P(m, 7) 写成分量形式就是 Pn(n1)=∑P4(n,m 证明验证P ∑P2(n,m)=∑P(5m=5n= PU{m=5n=1)=P(全集92|5n= 验证(P.2) ∑P1A(n,mp4(m1)=∑P(5m=k|5,=)P(51=5m=k) ∑P(m=k|5n=)P1=j1m=k,n=1)=∑P(51=j5m=k|5n=0 =PU5=jm=k}|5n=)=P(51=|5n=0 1.3时齐的 Markov链 定义5.4 Markov链称为时齐的,如果其概率转移阵P(n,n+1)与n无关(即1步 转移概率与出发时刻n无关 我们把此矩阵简记为P=(Pn).由(5.6)式得到 P(m,n+m)=P(n,n+1)P(n+1,n+2)…P(n+m-1,n+m)=P 它也不依赖出发时刻n,我们把它改记成Pm),(Pm)=(Pm),其分量 pm=P(5m=|n=1)为Mkov链5n,n≥0的m步转移概率,它也与出发时刻n无
98 P (n,m) ( p (n,m)) = ij . 由于此无穷矩阵的分量都是非负的且不超过 1, 易见这种无穷矩阵的乘法满足结合律. 又因 为 î í ì ¹ = = = 0 ( ) 1 ( ) ( , ) i j i j pij n n ij D d , (Kroneker 记号) 所以 P(n, n) = I (无穷单位矩阵). 特别地, P(n, n + 1) 称为时刻n (到时刻n +1)的概率转移 矩阵 而 P(n, n + k )就称为从n 出发的k 步概率转移矩阵． 命题５.３ 概率转移矩阵族满足以下的性质 记 1 为分量全是 1 的无穷行向量(矩阵), 其维数与此 Markov 链的状态数一致. 我们有 (P.1) 0 £ p (n,m) £ 1 ij , P (n,m) 1 T =1T . (上标T 表示转置运算) (P.2) (Chapman-Kolmogorov 方程) 对于"l ³ m ³ n 有 P (n,l) = P(n,m) P(m,l) , (5. 6) 写成分量形式就是 = å k ij ik kj p (n,l) p (n,m) p (m,l) . (5. 6)’ 证明 验证(P. 1) å = å = = j j ij m n p (n,m) P(x j | x i) . U j m n n = P( {x = j} | x = i) = P(全集W |x = i) =1. 验证(P. 2) å = å = = = = k m n l m k ik kj p (n,m) p (m,l) P(x k | x i)P(x j |x k) = å = = = = = k m n l m n P(x k |x i)P(x j | x k ,x i) = å = = = k l m n P(x j,x k | x i) U k l m n = P( {x = j,x = k} | x = i) P( j | i) = xl = xn = . １．３ 时齐的 Markov 链 定义５．４ Markov 链称为时齐的, 如果其概率转移阵 P(n, n + 1) 与n 无关(即 1 步 转移概率与出发时刻n 无关. 我们把此矩阵简记为 P= ( ) ij p ． 由 (5. 6)式得到 P (n, n + m) = P(n, n + 1) P(n + 1, n + 2)L P(n + m -1, n + m) = Pm 它也不依赖出发时刻n , 我们把它改记成 (m) P , ( ( ) ( ) (m) ij m P = p ), 其分量 ( ) ( ) p P j i n m n m ij = x + = x = 为 Markov 链{ ,n ³ 0} n x 的m 步转移概率, 它也与出发时刻n 无
关.于是 Chapman- Kolmogorov方程的矩阵形式变为 P(m)p 而其分量形式为 (其实(5.6)”式是显然的,因为它就是Pm"=PP) 以后在本书中除非特别声明,我们所考虑的 Markov链,均为时齐的 Markov链 对于时齐的 Markov链{n,n≥0},描述它的演化的最基本的量,就是它的转移概率矩 阵P=(P)(P,bj∈S),其中第i行就是给定5n=时,5m1的条件概率分布 转移概率矩阵P是一个随机矩阵,即它满足: (1)P中的元素均为非负,即Pn≥0 (2)P中的每一行的元素之和均为1,即∑P=1 Markov链的转移概率{Pj∈S}(或者说转移概率矩阵P)是刻画 Markov链的统 计特征的基本量.事实上,一个 Markov链可由其初始状态5o的统计性质(即其初始分布 0=P(50=)以及其转移概率矩阵P所完全确定这就是下面的定理。 定理5.5( Markov链的有限维分布)若 Markov链{n,n≥0}的初始分布为 H=P(50=1),其转移概率矩阵为P(Pn),则{n,n≥0}的有限维分布为 P(50=l0,51=l1,…5n=ln)=HnP4P2…P4-,b,4,…n∈S 证明由乘法公式与 Markov性得 P(0=l,51=i1,…,n=in) =P(50=)P(51=1k=)P(2=120=,51=1)…P(n=lnk0=l0…5n=ln) -Am Pigi pib"Pin-i 记p=P(En=1),它称为 Markov链在时刻n的绝对概率.再记由构成的行向 量为p(=(pm):t∈S),那么,我们有 定理5.6(m=p(mP),从而有p)=pPn 证明pm=P(5mn=)=∑P(5m=m=)P(5m=)=∑mp P
99 关. 于是 Chapman-Kolmogorov 方程的矩阵形式变为 (m n) (m) (n ) P = P P + (5. 6)’’ 而其分量形式为 =å + k n kj m ik m n pij p p ( ) ( ) ( ) (5. 6)’’’ (其实 (5. 6)’’式是显然的, 因为它就是 P m+n = P m Pn ). 以后在本书中除非特别声明，我们所考虑的 Markov 链，均为时齐的 Markov 链. 对于时齐的 Markov 链{ ,n ³ 0} n x ，描述它的演化的最基本的量，就是它的转移概率矩 阵 P= ( ) ij p ,( p , i, j S ) ij Î ，其中第i 行就是给定 i x n = 时， n+1 x 的条件概率分布. 转移概率矩阵 P 是一个随机矩阵，即它满足： (1) P 中的元素均为非负，即 ³ 0 ij p ， (2) P 中的每一行的元素之和均为 1，即å = 1 j ij p . Markov 链的转移概率{p , i, j S} ij Î （或者说转移概率矩阵 P）是刻画 Markov 链的统 计特征的基本量. 事实上，一个 Markov 链可由其初始状态 0 x 的统计性质（即其初始分布 ( ) 0 (0) P i mi = x = ）以及其转移概率矩阵 P 所完全确定. 这就是下面的定理。 定理 5．５ （Markov 链的有限维分布）若 Markov 链{ ,n ³ 0} n x 的初始分布为 ( ) 0 (0) P i mi = x = ，其转移概率矩阵为 P= ( ) ij p ，则{ ,n ³ 0} n x 的有限维分布为 P i i n i n i pi i pi i pi i i i i n S n n = = = = " Î - ( , , , ) , , , 0 1 (0 ) x0 0 x1 1 L x m 0 0 1 1 2 L 1 L ． 证明 由乘法公式与 Markov 性得 ( ) ( ) ( , ) ( , ) ( , , , ) 0 0 1 1 0 0 2 2 0 0 1 1 0 0 0 0 1 1 n n n n n n P i P i i P i i i P i i i P i i i = = = = = = = = = = = = = x x x x x x x x x x x x L L L n n i pi i pi i pi i 0 0 1 1 2 1 (0) - = m L ? 记 ( ) ( ) P i n n mi = x = ，它称为 Markov 链在时刻n 的绝对概率． 再记由 (n) mi 构成的行向 量为 (n ) m = ( : ) ( ) i S n mi Î ，那么，我们有 定理 5．６ (m+n) m = (m) m (n ) P ，从而有 (n ) m = (0) m n P 证明 = + = =å + = = = = å + i n ij m i i m n m n m m m n j P j P j i P i p ( ) ( ) ( ) m (x ) (x x ) (x ) m = j m n ( ) ( ) ( ) m P ． ?
定理5.5与定理5.6说明了 Markov链的统计性质(包括其长时间极限行为),完全 可由其转移概率矩阵P,以及它的初始分布所决定.因此, Markov链的很多性质的研 究就归结为随机矩阵的性质 1.4 Markov链的例 例5.7(随机徘徊) 独立同分布的随机变量的部分和序列,称为随机徘徊,它是时间参数离散情形时的时齐 的独立增量过程.又若其中的随机变量只取1与—1两个值,则称为简单随机徘徊 今考虑一个简单随机徘徊{n,n≥0},其状态空间为S=Z={全体整数},由n的定义 ZK 其中{k,k≥0}为独立同分布随机变量序列,满足 这里n表示一个粒子每次分别以概率p与q向右与向左走一格.P=的情况称为对称简 单随机徘徊由于随机徘徊是时齐的独立增量过程由第3章可知它也是时齐的 Markov链 又因为0,51,…n都是Z0,Z1,…,Zn的部分和,所以它们和Z独立,故 P(Em,=jmi)=P(Zn+5n=js, P( 0其它 即其转移矩阵为 q0p00 Pi) P 00 0 P 而绝对概率为 P(=D=c2p20-p)2,(若n2体且与奇偶同 其它情形) 实上P(5n=就是:n个相互独立的随机事件{Z1=1},亿Z2=1},…,1{Zn=1}中恰好有 100
100 定理５.５与定理５.６说明了 Markov 链的统计性质（包括其长时间极限行为），完全 可由其转移概率矩阵 P，以及它的初始分布 (0) m 所决定. 因此，Markov 链的很多性质的研 究就归结为随机矩阵的性质. １．４ Markov 链的例 例５．７ （随机徘徊） 独立同分布的随机变量的部分和序列，称为随机徘徊，它是时间参数离散情形时的时齐 的独立增量过程．又若其中的随机变量只取１与－１两个值, 则称为简单随机徘徊. 今考虑一个简单随机徘徊{ ,n ³ 0} n x ，其状态空间为 S = Z ={全体整数}，由 n x 的定义 å= = + n k n Zk 1 x x 0 ， 其中{Z , k ³ 0} k 为独立同分布随机变量序列，满足 ÷ ÷ ø ö ç ç è æ- q p Zk 1 1 ~ (q = 1- p) . 这里 n x 表示一个粒子每次分别以概率 p 与 q 向右与向左走一格. 2 1 p = 的情况称为对称简 单随机徘徊. 由于随机徘徊是时齐的独立增量过程, 由第 3 章可知它也是时齐的 Markov 链. 又因为 n x ,x ,Lx 0 1 都是 Z Z Zn , , , 0 1 L 的部分和, 所以, 它们和Zn +1 独立，故 ï î ï í ì = - = + = = - = = = - = = = = = + = = + + + + 0 其它 1 1 ( ) ( ) ( ) ( ) 1 1 1 1 q j i p j i P Z j i i P Z j i p P j i P Z j i n n n ij n n n n n x x x x x ． 即其转移矩阵为 P=( ) ij p = ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç ç ç ç è æ L L L L L L L M M M M M M M M M M M M M M M M M M M M L L L L L L L q p q p q p 0 0 0 0 0 0 0 0 0 ． 而绝对概率为 ïî ï í ì - ³ = = + + - ， 其它情形） ， 若 ，且 与 奇偶同 0 ( (1 ) ( ) ( ) 2 2 2 C p p n j n j P j n j n j n j n n x ． 事实上 P( j) xn = 就是: n 个相互独立的随机事件{ 1},{ 1},...,{ 1} Z1 = Z2 = Zn = 中恰好有