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为暂态分∑Pm< 推论5.17状态j为暂态→,∑p<∞,从而mp=0 证明右=F()<∞ 推论5.18(有限状态 Markov链)有限状态 Markov链至少存在一个常返态 证明假设有限状态 Markov链的所有状态均为暂态,那么由 P(n=j|50=1=∑P→0 这就导致了矛盾 定义5.20如果存在n≥0,使P>0,则称状态订可达状态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 为暂态 Û å < ¥ ¥ =1 ( ) n n p jj . 推论５．１７ 状态 j 为暂态 Þ "i, å < ¥ ¥ =1 ( ) n n pij , 从而 lim 0 ( ) = ®¥ n ij n p . 证明 右= Fij(1) < ¥ . 推论５．１８ (有限状态 Markov 链) 有限状态 Markov 链至少存在一个常返态. 证明 假设有限状态 Markov 链的所有状态均为暂态, 那么由 å å £ £ £ £ ®¥ = = = = ® j N j N n n n ij P j i p 1 1 ( ) 0 1 (x | x ) 0． 这就导致了矛盾． 定义５.２０ 如果存在n ³ 0，使 0 ( ) > 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 ．