龚光鲁,钱敏平著应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,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 = 中恰好有
n 个发生的概率(5n要到达状态j,所需的步数n不可能小刊小,故n≥|,设N 和Nn分别表示在前n步中向右和向左的步数,则显然有n=N#+Nn, 于是N#=(n+5n),从而5n=j台N#=(n+j).又因为 2N+=(+5n)是偶数,因此n与En的奇偶性相同).对于初始状态为50=i的简单随机 徘徊,类似可得 P=P(5n=j|50=) n≥|-4,且n与-奇偶同) (其它情形) 0 例5.8(两端为反射壁的随机徘徊)在例5.7中,如果在位置a与b(a<b)分别 设置一个反射壁,即当粒子到达a与b时,下一步则以概率为1地分别”反射”到a+1 与b-1.此时粒子的运动仍然是一个 Markov链,与例5.7不同处仅在于 Pa+1=1,pay=0,(≠a+1),P 0,(≠b-1) 即其转移矩阵为 01 0p00 P=(P1) q00 q P o p 读者可自行写出一端反射壁的随机徘徊的转移矩阵P. 例5.9(两端为吸收壁的随机徘徊)若 Markov链取值于{a,a+1,…,b},且其 转移矩阵为 P=(p 0:g00 P g0 p 0 q P 则称此 Markov链为在a与b设有吸收壁的随机徘徊.即:Pa=Pb=1,并称a与b为
101 2 n + j 个发生的概率 ( n x 要到达状态 j ，所需的步数 n 不可能小于 j ，故n ³ j ， 设 + Nn 和 - Nn 分别表示在前 n 步中向右和向左的步 数 ， 则显然有 + - = Nn + Nn n ， + - n = Nn - Nn x ． 于是 ( ) n n N = n + x + 2 1 , 从而 j N (n j) n = Û n = + + 2 1 x ．又因为 ( ) n n N = n + x + 2 是偶数，因此 n 与 n x 的奇偶性相同). 对于初始状态为 = i 0 x 的简单随机 徘徊，类似可得 ï î ï í ì - ³ - - = = = = + - + - - + 其它情形） 若 ，且 与 奇偶同 ( 0 (1 ) ( ) ( | ) 2 2 2 0 ( ) C p p n j i n j i p P j i n j i n j i n j i n n n ij x x . 例５．８ (两端为反射壁的随机徘徊) 在例５．７中, 如果在位置 a 与 b ( a<b ) 分别 设置一个反射壁, 即当粒子到达 a 与 b 时, 下一步则以概率为 1 地分别 ”反射” 到 a +1 与b -1． 此时粒子的运动仍然是一个 Markov 链, 与例５．７不同处仅在于 1, 0 , ( 1); 1, 0, ( 1). pa,a +1 = pa , j = j ¹ a + pb,b-1 = pb, j = j ¹ b - 即其转移矩阵为 P=( ) ij p = ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç ç ç ç è æ 1 0 0 0 0 0 0 0 0 0 0 0 1 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 q p q p q p ． 读者可自行写出一端反射壁的随机徘徊的转移矩阵 P. 例５．９ (两端为吸收壁的随机徘徊) 若 Markov 链取值于{a, a +1,L,b}， 且其 转移矩阵为 P=( ) ij p = ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç ç ç ç è æ 0 1 0 0 0 0 0 0 0 0 0 1 0 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 q p q p q p ， 则称此 Markov 链为在 a 与b 设有吸收壁的随机徘徊．即： paa = pbb = 1，并称 a 与 b 为
Markov链的吸收态 例5.10(货仓存货问题) 设一个运货仓库每月进货的件数是一个独立同分布的随机变量序列仞n:n=12…}, 其中ηn表示第n个月进货的件数,n 仓库 的货物容量为N件,每当仓库的货物超过N件时,就将N件打包发运.记第n个月底的 存货量为5n,那么 5n-1+ nn <N nn≥N-5 于是{nn≥0是一个 Markov链,事实上 P(5m=10=1051=1…5n=l-15n=1) P(+nn=j50=l0,51 5n=1)(<j<N) P(i+1n-N=儿|0=l0…,5n1=ln-1,n=1) (≥j P(nm1=j-il5=io (<j<N) P(nn=N+j-|50=i0…,Em1=in15n=1)(j≤l) (i<j<N (<j<N) P(m1=N+j-i (i≥j (≥j 同样的推理也得到 P(51=/150=0)= i<j<N P 所以{n,n≥0}是时齐的 Markov链,且其转移矩阵的分量为 P-(<j P (≥j 例5.11(品牌选择)设市场上销售A,B,C,D四种品牌的牙膏,根据市场调 查,消费者购买哪一种品牌的牙膏,近似地仅与他前一次购买的品牌有关,而与这之前购买 的品牌无关.记50为某消费者最初所购买的牙膏的品牌,5152;…分别表示他在这之后各 次所购买的牙膏的品牌,则{n:n≥0}为一 Markov链,其状态空间为S={ABCD},它的 转移概率矩阵可以从市场调査中近似地获得.假定经过长期市场调查统计得到近似的转移矩 阵为
102 Markov 链的吸收态． 例５．１０ ( 货仓存货问题 ) 设一个运货仓库每月进货的件数是一个独立同分布的随机变量序列{ : n = 1,2,L} hn ， 其中hn 表示第 n 个月进货的件数, ÷ ÷ ø ö ç ç è æ N n p p N L L 1 1 h ~ . 又设 0 x ÷ ÷ ø ö ç ç è æ N N N 1 1 1 ~ L L , 仓库 的货物容量为 N 件, 每当仓库的货物超过N 件时, 就将N 件打包发运. 记第n个月底的 存货量为 n x , 那么 1 1 1 1 - - - - ³ - < - ç ç è æ + - + = n n n n n n n n n N N N h x h x x h x h x 。 于是{ :: n ³ 0} n x 是一个 Markov 链, 事实上 î í ì = + - = = = £ = - = = = < < = î í ì + - = = = = ³ + = = = = = < < = = = = = = + - - + - - + - - + - - + - - ( | , , , ) ( ) ( | , , , ) ( ) ( | , , , ) ( ) ( | , , , , ) ( ) ( , , , , ) 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 P N j i i i i j i P j i i i i i j N P i N j i i i i j P i j i i i i i j N P j i i i i n n n n n n n n n n n n n n n n n n n n h x x x h x x x h x x x h x x x x x x x x x L L L L L . î í ì = + - ³ = - < < = + + ( ) ( ) ( ) ( ) 1 1 P N j i i j P j i i j N n n h h î í ì ³ < < = + - - ( ) ( ) p i j p i j N N j i j i ． 同样的推理也得到 ( | ) 1 0 P x = j x = i î í ì ³ < < = + - - ( ) ( ) p i j p i j N N j i j i . 所以{ ,n ³ 0} n x 是时齐的 Markov 链, 且其转移矩阵的分量为 î í ì ³ < < = + - - ( ) ( ) p i j p i j N p N j i j i ij . 例 5．１１ ( 品牌选择 ) 设市场上销售 A， B，C，D 四种品牌的牙膏，根据市场调 查，消费者购买哪一种品牌的牙膏，近似地仅与他前一次购买的品牌有关，而与这之前购买 的品牌无关．记 0 x 为某消费者最初所购买的牙膏的品牌，x1 ,x 2 ,L分别表示他在这之后各 次所购买的牙膏的品牌，则{ : n ³ 0} n x 为一 Markov 链，其状态空间为 S={A,B,C,D}，它的 转移概率矩阵可以从市场调查中近似地获得．假定经过长期市场调查统计得到近似的转移矩 阵为
0.900050030.02 0.100.800.050.05 0.080.100.800.02 0.100.100.100.70 对于这个链,人们感兴趣的是这四种品牌的牙膏的市场占有率随时间进程的变化 例5.12( Wright-Fisher遗传模型)遗传的要素是染色体.遗传性质的携带者称 为基因,它们位于染色体上、基因控制着生物的特征,它们是成对出现的.控制同一特征的 不同基因称为等位基因,记这对等位基因为A和a,分别称为显性的与隐性的.在一个总 体中基因A和a出现的频率称为基因频率,分别记为p和1-P,设总体中的个体数为2N 每个个体的基因按A型基因的基因频率的大小,在下一代中转移成为A型基因.因此,繁 殖出的第二代的基因型是由试验次数为2N的 Bernoulli试验所确定的.即如果在第n代母体 中A型基因出现了i次,而a型基因出现了2N-i次,则下一代出现A型基因的概率为 P 2,而出现a型基因的概率为1-P·记5n为第n代中携带A型基因的个体数,则 易证{n,n≥0}是一状态空间为S={01,2,…,2N}的时齐 Markov链,其转移概率矩阵为 P=(Pn),其中 Pn=P(5m=n=0)=C3p,(1-P2)2N=C2(.)(1-2)2N 2. Markov链的状态分类 2.1首达分解,n步转移概率的递推式,矩母函数,常返性 定义5.13(首次进入状态j的时刻)把从i出发在n(≥1)步转移中首次到达j的概 率记为f"”·用数学式表达即 f=P(5n=,5≠jk=12,…n-1=1)(n≥ 而把 Markov链{n,n≥0}首次击中状态j的时刻记为T,那么T是一随机变量,但是与普 通的随机变量有一点不同,就是它可以取值∞(事实上,它还是一个(2n)停时,即它是否 不大于m,只由随机序列ξn在时刻m前的信息完全确定),即 mn{n≥1:5n=} (若存在n≥1使得n=j (其它情形) 从而有 P(T=帐0=1)=f”(n21 103
103 P= ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ 0.10 0.10 0.10 0.70 0.08 0.10 0.80 0.02 0.10 0.80 0.05 0.05 0.90 0.05 0.03 0.02 ． 对于这个链，人们感兴趣的是这四种品牌的牙膏的市场占有率随时间进程的变化. 例５．１２ ( Wright-Fisher 遗传模型 ) 遗传的要素是染色体．遗传性质的携带者称 为基因，它们位于染色体上. 基因控制着生物的特征，它们是成对出现的. 控制同一特征的 不同基因称为等位基因，记这对等位基因为 A 和 a.，分别称为显性的与隐性的．在一个总 体中基因 A 和 a 出现的频率称为基因频率，分别记为 p 和1- p ． 设总体中的个体数为 2N. 每个个体的基因按 A 型基因的基因频率的大小, 在下一代中转移成为 A 型基因. 因此，繁 殖出的第二代的基因型是由试验次数为 2N 的 Bernoulli试验所确定的. 即如果在第 n 代母体 中 A 型基因出现了i 次，而 a 型基因出现了 2N -i 次, 则下一代出现 A 型基因的概率为 N i pi 2 = ，而出现 a 型基因的概率为1- pi . 记 n x 为第 n 代中携带 A 型基因的个体数，则 易证{ ,n ³ 0} n x 是一状态空间为 S = {0,1,2,L,2N}的时齐 Markov 链，其转移概率矩阵为 P= ( ) ij p ，其中 j j N j N N j i j i j ij n n N N i N i p P j i C p p C - - = + = = = - = - 2 2 2 1 2 ) 2 ) (1 2 (x x ) (1 ) ( . 2. Markov 链的状态分类 2. 1 首达分解, n 步转移概率的递推式，矩母函数, 常返性 定义５.１３（首次进入状态 j 的时刻） 把从 i 出发在 n(³ 1) 步转移中首次到达 j 的概 率记为 (n ) ij f ．用数学式表达即 ( , , 1,2, 1 ),( 1) 0 ( ) f = P n = j k ¹ j k = n - = i n ³ n ij x x L x (5. 7) 而把 Markov 链{ ,n ³ 0} n x 首次击中状态 j 的时刻记为T j ，那么T j 是一随机变量, 但是与普 通的随机变量有一点不同, 就是它可以取值 ¥ （事实上，它还是一个 ( ) n x 停时，即它是否 不大于m ，只由随机序列 n x 在时刻m 前的信息完全确定），即 î í ì ¥ ³ = ³ = = 其它情形） 若存在 使得 ( min{ n 1: j} ( n 1 j) T n n j x x . 从而有 ( ) ( 1) ( ) P T = n 0 = i = f n ³ n j ij x ．
P(T=5=1)=1-∑f 再记 f=∑=P(T1<+150=1)=P(n21使得5n=k=i)s1 那么J表示{:n20从i出发,在有限时间内它能够到达j的概率(或者说,从i出发 最终转移到状态j的概率) 定义5.14(常返态与暂态) Markov链{2n:n≥0}的状态i称为常返态,如 果从i出发,能以概率为Ⅰ地,最终又能回到讠,即∫=1.如果状态i不是常返态,则称它 为暂态 定理5.15( Markov链的首达分解定理)对于任意状态i,j,任意时刻n,有 p(=∑f(p0= (5.10) 证明利用 Markov性质,我们有 P=P(5n=j15=1=∑P(5n=,T,=k150=1) ∑P(5n=川T=k.50=)PG=k|5=)=∑P(n=j15k=nf0.? fn=0, 并定义矩母函数 P2()=∑p/",F()=∑f= k= 易见定理5.15可以写成如下的矩母函数形式 定理5.15 P(=)=6n+F()P1(=) 从(5.10)′可以解出 P() (5.11) Fn(=) F(2) 1-Fn(2)
104 å ¥ = = ¥ = = - 1 ( ) ( 0 ) 1 n n j ij P T x i f ．. (5. 8) 再记 å ¥ = = 1 ( ) n n ij ij f f ( | ) 0 P T i = j < +¥ x = = P($n ³1使得xn = ix0 = i) £1, (5. 9) 那么 ij f 表示{ n 0} xn： ³ 从i 出发, 在有限时间内它能够到达 j 的概率 (或者说, 从i 出发 最终转移到状态 j 的概率). 定义５.１４ （ 常返态与暂态） Markov 链{ n ³ 0} xn： 的状态i 称为常返态， 如 果从 i 出发, 能以概率为 1 地, 最终又能回到 i，即 f ii = 1. 如果状态i 不是常返态, 则称它 为暂态. 定理 5．１５ （Markov 链的首达分解定理）对于任意状态 i, j , 任意时刻n ，有 å= - = n k n k jj k ij n pij f p 1 ( ) ( ) ( ) . (5. 10) 证明 利用 Markov 性质，我们有 å= = = = = = = = n k n n j n ij p P j i P j T k i 1 0 ( ) (x |x ) (x , |x０ )) å å = = = = = = = = = = = n k k n k ij n k n j j P j T k i P T k i P j j f 1 ( ) 1 0 0 (x | ,x ) ( | x ) (x |x ) .? 令 , 0 (0) (0 ) pij = d ij f ij = ， 并定义矩母函数 å ¥ = = 0 ( ) ( ) k n n Pij z pij z , å ¥ = = 0 ( ) ( ) k n n Fij z fij z . 易见定理５．１５可以写成如下的矩母函数形式 定理 5.１５’ P (z) F (z)P (z) ij = ij + ij jj d . (5. 10)’． ? 从（５．１０）＇可以解出 1 ( ) 1 ( ) F z P z jj jj - = , (5. 11) 1 ( ) ( ) ( ) F z F z F z jj ij ij - = . (5. 12)
在(5.11)式中令z→1-0,便得到(利用数学分析中的Abel定理) 于是,由常返性的定义立得如下的充要条件 定理5.16(常返性与暂态的条件) j为常返态∑p=m; j为暂态分∑Pm0,则称状态订可达状态j,记作i→j,表 示从状态i经过有限步的转移可以到达状态j.它等价于:存在l1,…,l-1使 P0,0≤k≤n-1,其中i0=i,in=j 注( Markov链转移的图示)把 Markov链的状态记为顶点。如果P>0,则从状态 i到状态j画一条有向边.这样就得到表示 Markov链的转移情况的一个有向图(有些边 可能是双向的).那么,i→>j等价于存在顶点i到顶点j的一条由定向边组成的通路 命题5.21设i→>j且j→>i(记为i台>j),则状态i与j常返与否是相同的 证明由于i台>j,故存在m,n≥0,使得pm>0, 0 由 Chapman- Kolmogorov方程可知,对任意非负整数r,有 Pi p pji=a·Pn 由对称性同样有 Pitrim)2 pin pm)=a pir
105 在(5. 11)式中令 z ®1-0 ，便得到(利用数学分析中的 Abel 定理) n jj n jj f p - å = ¥ = 1 1 1 ( ) . （５．１１）＇ 于是，由常返性的定义立得如下的充要条件 定理 5.１６ （常返性与暂态的条件） j 为常返态 Û å = ¥ ¥ =1 ( ) n n p jj ; j 为暂态 Û å n pij ，则称状态i 可达状态 j，记作i ® j ， 表 示从状态 i 经过有限步的转移可以到达状态 j. 它等价于: 存在 1 1 , , n- i L i 使 ,0 1, 1>0 £ £ - + p k n k k i i 其中i i i j 0 = , n = . 注 （Markov 链转移的图示） 把 Markov 链的状态记为顶点。如果 > 0 ij p ，则从状态 i 到状态 j 画一条有向边．这样就得到表示 Markov 链的转移情况的一个有向图（有些边 可能是双向的）．那么，i ® j 等价于存在顶点i 到顶点 j 的一条由定向边组成的通路． 命题 5.２１ 设 i ® j 且 j ® i （记为i « j ），则状态i 与 j 常返与否是相同的. 证明 由于i « j ，故存在m, n ³ 0，使得 0, 0 ( ) ( ) > > n ji m pij p ，记 0 ( ) ( ) = > D n ji m a pij p ． 由 Chapman-Kolmogorov 方程可知，对任意非负整数 r，有 ( ) ( ) ( ) ( ) (r) jj n ji r jj m ij m r n pii ³ p p p = × p + + a ． 由对称性同样有 ( ) ( ) ( ) ( ) (r) ii m ij r ii n ji n r m p jj ³ p p p = × p + + a ．