第十七章马氏链模型 §1随机过程的概念 个随机试验的结果有多种可能性,在数学上用一个随机变量(或随机向量)来描 述。在许多情况下,人们不仅需要对随机现象进行一次观测,而且要进行多次,甚至接 连不断地观测它的变化过程。这就要研究无限多个,即一族随机变量。随机过程理论就 是硏究随机现象变化过程的概率规律性的 定义1设{1,t∈T}是一族随机变量,T是一个实数集合,若对任意实数t∈T5 是一个随机变量,则称{1I∈T}为随机过程 T称为参数集合,参数t可以看作时间。5的每一个可能取值称为随机过程的一个 状态。其全体可能取值所构成的集合称为状态空间,记作E。当参数集合T为非负整 数集时,随机过程又称随机序列。本章要介绍的马尔可夫链就是一类特殊的随机序列。 例1在一条自动生产线上检验产品质量,每次取一个,“废品”记为1,“合格品” 记为0。以5n表示第n次检验结果,则n是一个随机变量。不断检验,得到一列随机 变量51252…,记为{n,n=1,2,…}。它是一个随机序列,其状态空间E={0,1} 例2在m个商店联营出租照相机的业务中(顾客从其中一个商店租出,可以到m 个商店中的任意一个归还),规定一天为一个时间单位,“51=j”表示“第1天开始营 业时照相机在第j个商店”j=1,2,…,m。则{n,n=12,…}是一个随机序列,其状 态空间E={1,2…,m}。 例3统计某种商品在t时刻的库存量,对于不同的t,得到一族随机变量, {5,t∈[0,+∞)}是一个随机过程,状态空间E=[0,R],其中R为最大库存量 我们用一族分布函数来描述随机过程的统计规律。一般地,一个随机过程 51,t∈T},对于任意正整数n及T中任意n个元素,…,n相应的随机变量54,…,5 的联合分布函数记为 F.(x1,…,xn)=P{5,≤x1…,.≤xn} (1) 由于n及t(i=1,…,n)的任意性,(1)式给出了一族分布函数。记为 {F….(x1,…,xn),1∈T,i=1,…,n,n=12… 称它为随机过程{,t∈T}的有穷维分布函数族。它完整地描述了这一随机过程的统计 规律性。 §2马尔可夫链 2.1马尔可夫链的定义 现实世界中有很多这样的现象:某一系统在已知现在情况的条件下,系统未来时刻 的情况只与现在有关,而与过去的历史无直接关系。比如,研究一个商店的累计销售额 如果现在时刻的累计销售额已知,则未来某一时刻的累计销售额与现在时刻以前的任一 时刻累计销售额无关。上节中的几个例子也均属此类。描述这类随机现象的数学模型称 为马氏模型。 定义2设{n,n=1,2,…}是一个随机序列,状态空间E为有限或可列集,对于任 意的正整数m,n,若,j∈E(k=1,…,n-1),有
-207- 第十七章 马氏链模型 §1 随机过程的概念 一个随机试验的结果有多种可能性，在数学上用一个随机变量（或随机向量）来描 述。在许多情况下，人们不仅需要对随机现象进行一次观测，而且要进行多次，甚至接 连不断地观测它的变化过程。这就要研究无限多个，即一族随机变量。随机过程理论就 是研究随机现象变化过程的概率规律性的。 定义 1 设{ ,t T} ξ t ∈ 是一族随机变量，T 是一个实数集合，若对任意实数 T t t ∈ ,ξ 是一个随机变量，则称{ ,t T} ξ t ∈ 为随机过程。 T 称为参数集合，参数t 可以看作时间。ξ t 的每一个可能取值称为随机过程的一个 状态。其全体可能取值所构成的集合称为状态空间，记作 E 。当参数集合T 为非负整 数集时，随机过程又称随机序列。本章要介绍的马尔可夫链就是一类特殊的随机序列。 例 1 在一条自动生产线上检验产品质量，每次取一个，“废品”记为 1，“合格品” 记为 0。以ξ n 表示第n 次检验结果，则ξ n 是一个随机变量。不断检验，得到一列随机 变量ξ 1 ,ξ 2 ,L，记为{ ,n = 1,2,L} ξ n 。它是一个随机序列，其状态空间 E = {0,1}。 例 2 在m 个商店联营出租照相机的业务中（顾客从其中一个商店租出，可以到m 个商店中的任意一个归还），规定一天为一个时间单位，“ j ξ t = ”表示“第t 天开始营 业时照相机在第 j 个商店”， j = 1,2,L,m 。则{ ,n = 1,2,L} ξ n 是一个随机序列，其状 态空间 E = {1,2,L,m}。 例 3 统计某种商品在 t 时刻的库存量，对于不同的 t ，得到一族随机变量， { ,t ∈[0,+∞)} ξ t 是一个随机过程，状态空间 E = [0,R]，其中 R 为最大库存量。 我们用一族分布函数来描述随机过程的统计规律。一般地，一个随机过程 { ,t T} ξ t ∈ ，对于任意正整数n 及T 中任意n 个元素 n t , ,t 1 L 相应的随机变量 n ξ t ξ t , , 1 L 的联合分布函数记为 ( , , ) { , , } t1 t 1 n t1 1 t n F x x P x x n n L L = ξ ≤ L ξ ≤ （1） 由于n 及t (i 1, ,n) i = L 的任意性，（1）式给出了一族分布函数。记为 { ( , , ), , 1, , ; 1,2, } Ft1Ltn x1 L xn ti ∈T i = L n n = L 称它为随机过程{ ,t T} ξ t ∈ 的有穷维分布函数族。它完整地描述了这一随机过程的统计 规律性。 §2 马尔可夫链 2.1 马尔可夫链的定义 现实世界中有很多这样的现象：某一系统在已知现在情况的条件下，系统未来时刻 的情况只与现在有关，而与过去的历史无直接关系。比如，研究一个商店的累计销售额， 如果现在时刻的累计销售额已知，则未来某一时刻的累计销售额与现在时刻以前的任一 时刻累计销售额无关。上节中的几个例子也均属此类。描述这类随机现象的数学模型称 为马氏模型。 定义 2 设{ ,n = 1,2,L} ξ n 是一个随机序列，状态空间 E 为有限或可列集，对于任 意的正整数m,n ，若i, j,i ∈ E(k = 1, ,n −1) k L ，有
P{nm=儿n=1,n1=n1…,51=1}=P{5n+m=n=l} (2) 则称{n,n=1,2,…}为一个马尔可夫链(简称马氏链),(2)式称为马氏性。 事实上,可以证明若等式(2)对于m=1成立,则它对于任意的正整数m也成立。 因此,只要当m=1时(2)式成立,就可以称随机序列{n,n=1,2,…具有马氏性 即{n,n=1,2,…}是一个马尔可夫链 定义3设{n,n=12,…}是一个马氏链。如果等式(2)右边的条件概率与n无 关,即 PIMm=jIm=1)=Pu,(m) (3) 则称{5n,n=1,2…为时齐的马氏链。称P(m)为系统由状态i经过m个时间间隔(或 m步)转移到状态j的转移概率。(3)称为时齐性。它的含义是:系统由状态i到状态 j的转移概率只依赖于时间间隔的长短,与起始的时刻无关。本章介绍的马氏链假定都 是时齐的,因此省略“时齐”二字 22转移概率矩阵及柯尔莫哥洛夫定理 对于一个马尔可夫链{n,n=12…},称以m步转移概率P2(m)为元素的矩阵 P(m)=(P2(m))为马尔可夫链的m步转移矩阵。当m=1时,记P()=P称为马尔可 夫链的一步转移矩阵,或简称转移矩阵。它们具有下列三个基本性质: (i)对一切,j∈E,0≤P2(m)≤1 (i)对一切i∈E,∑P2(m)=1 (i)对一切1∈E,P=9={当=时 0,当≠j时 当实际问题可以用马尔可夫链来描述时,首先要确定它的状态空间及参数集合,然 后确定它的一步转移概率。关于这一概率的确定,可以由问题的内在规律得到,也可以 由过去经验给出,还可以根据观测数据来估计。 例4某计算机机房的一台计算机经常出故障,研究者每隔15分钟观察一次计算 机的运行状态,收集了24小时的数据(共作97次观察)。用1表示正常状态,用0表 示不正常状态,所得的数据序列如下 111001001111111001111011111100111111111000110110 111011011010111101110111101111110011011111100111 解设X(n=1…97)为第n个时段的计算机状态,可以认为它是一个时齐马氏 链,状态空间E={0,1},编写如下 Matlab程序 a1=11110010011111110011110111111001111111110001101101; a2=11110110110101111011101111011111100110111111001111 a=[a1a2] f00=length(findstr(00,a) f0l=length(findstr('01,a) f10=length(findstr(10,a) fll=length(findstr('ll,a) 或者把上述数据序列保存到纯文本文件data1.txt中,存放在Mat1ab下的work 子目录中,编写程序如下: C⊥c,c1e
-208- { | , , , } { | } 1 1 1 1 P j i i i P j i ξ n+m = ξ n = ξ n− = n− L ξ = = ξ n+m = ξ n = （2） 则称{ ,n = 1,2,L} ξ n 为一个马尔可夫链（简称马氏链），（2）式称为马氏性。 事实上，可以证明若等式（2）对于m = 1成立，则它对于任意的正整数m 也成立。 因此，只要当 m = 1时（2）式成立，就可以称随机序列{ ,n = 1,2,L} ξ n 具有马氏性， 即{ ,n = 1,2,L} ξ n 是一个马尔可夫链。 定义 3 设{ ,n = 1,2,L} ξ n 是一个马氏链。如果等式（2）右边的条件概率与n 无 关，即 P{ j | i} p (m) ξ n+m = ξ n = = ij （3） 则称{ ,n = 1,2,L} ξ n 为时齐的马氏链。称 p (m) ij 为系统由状态i 经过m 个时间间隔（或 m 步）转移到状态 j 的转移概率。（3）称为时齐性。它的含义是：系统由状态i 到状态 j 的转移概率只依赖于时间间隔的长短，与起始的时刻无关。本章介绍的马氏链假定都 是时齐的，因此省略“时齐”二字。 2.2 转移概率矩阵及柯尔莫哥洛夫定理 对于一个马尔可夫链{ ,n = 1,2,L} ξ n ，称以 m 步转移概率 p (m) ij 为元素的矩阵 P(m) ( p (m)) = ij 为马尔可夫链的m 步转移矩阵。当m = 1时，记 P(1) = P 称为马尔可 夫链的一步转移矩阵，或简称转移矩阵。它们具有下列三个基本性质： （i）对一切i, j ∈ E ，0 ≤ pij(m) ≤ 1； （ii）对一切i ∈ E ， ∑∈ = j E pij(m) 1； （iii）对一切i, j ∈ E ， ⎩ ⎨ ⎧ ≠ = = = 当 时 当 时 ， i j i j pij ij 0 1, (0) δ 。 当实际问题可以用马尔可夫链来描述时，首先要确定它的状态空间及参数集合，然 后确定它的一步转移概率。关于这一概率的确定，可以由问题的内在规律得到，也可以 由过去经验给出，还可以根据观测数据来估计。 例 4 某计算机机房的一台计算机经常出故障，研究者每隔 15 分钟观察一次计算 机的运行状态，收集了 24 小时的数据（共作 97 次观察）。用 1 表示正常状态，用 0 表 示不正常状态，所得的数据序列如下： 1110010011111110011110111111001111111110001101101 111011011010111101110111101111110011011111100111 解 设 X (n = 1,L,97) n 为第n 个时段的计算机状态，可以认为它是一个时齐马氏 链，状态空间 E = {0,1}，编写如下 Matlab 程序： a1='1110010011111110011110111111001111111110001101101'; a2='111011011010111101110111101111110011011111100111'; a=[a1 a2]; f00=length(findstr('00',a)) f01=length(findstr('01',a)) f10=length(findstr('10',a)) f11=length(findstr('11',a)) 或者把上述数据序列保存到纯文本文件data1.txt中，存放在Matlab下的work 子目录中，编写程序如下： clc,clear
format rat fid=fopen('datal. txt,'r)i while (feof(fid) a=[a fgetl(fid)] end for 1=0: 1 for j=0: 1 s=[int2str(),int2str (j)] f(i+1,j+1)=length(findstr(s, a))i end fs=sum(f)i f(i,:)=f(i,:)/fs(i) 求得96次状态转移的情况是 0→0,8次;0→1,18次 1→0,18次;1→1,52次 因此,一步转移概率可用频率近似地表示为 Poo= P(Xn=0 Xn=0 a 8+1813 o=P{Xn+1=1|Xn=0}≈ P1o=P(m=01,=l-18 73 8+ 9 18+5235 P1=PXn+=1|Xn=1≈-5226 18+5235 例5设一随机系统状态空间E={12,3,4},记录观测系统所处状态如下: 2232 14311 2143 若该系统可用马氏模型描述,估计转移概率P 解首先将不同类型的转移数nn统计出来分类记入下表 i→j转移数n 4121 行和n 2324 11 各类转移总和∑∑n等于观测数据中马氏链处于各种状态次数总和减1,而行和几是
-209- format rat fid=fopen('data1.txt','r'); a=[]; while (~feof(fid)) a=[a fgetl(fid)]; end for i=0:1 for j=0:1 s=[int2str(i),int2str(j)]; f(i+1,j+1)=length(findstr(s,a)); end end fs=sum(f'); for i=1:2 f(i,:)=f(i,:)/fs(i); end f 求得 96 次状态转移的情况是： 0 → 0，8 次； 0 →1，18 次； 1→ 0 ，18 次； 1→1，52 次， 因此，一步转移概率可用频率近似地表示为 13 4 8 18 8 { 0 | 0} 00 1 = + p = P Xn+ = Xn = ≈ 13 9 8 18 18 { 1| 0} 01 1 = + p = P Xn+ = Xn = ≈ 35 9 18 52 18 { 0 | 1} 10 1 = + p = P Xn+ = Xn = ≈ 35 26 18 52 52 { 1| 1} 11 1 = + p = P Xn+ = Xn = ≈ 例 5 设一随机系统状态空间 E = {1,2,3,4}，记录观测系统所处状态如下： 4 3 2 1 4 3 1 1 2 3 2 1 2 3 4 4 3 3 1 1 1 3 3 2 1 2 2 2 4 4 2 3 2 3 1 1 2 4 3 1 若该系统可用马氏模型描述，估计转移概率 pij 。 解 首先将不同类型的转移数nij 统计出来分类记入下表 i → j 转移数nij 1 2 3 4 行和ni 1 2 3 4 4 4 1 1 3 2 4 2 4 4 2 1 0 1 4 2 10 11 11 7 各类转移总和 ∑∑ i j nij 等于观测数据中马氏链处于各种状态次数总和减 1，而行和ni 是
系统从状态i转移到其它状态的次数,n是由状态i到状态j的转移次数,则pn的估 值P 算得 2/52/51/101/10 3/112/114/112/11 4/114/112/111/11 01/74/72/7 Matlab计算程序如下: format rat =[432143 2123443311 1332122244 for 1=1: 4 for j=l: 4 f(i,3)=length(findstr([i 3l, a)) ni=(sum(f)) for i=1: 4 p(i,:)=f(i,:)/ni(i) end 例6(带有反射壁的随机徘徊)如果在原点右边距离原点一个单位及距原点S(s>1) 个单位处各立一个弹性壁。一个质点在数轴右半部从距原点两个单位处开始随机徘徊。 每次分别以概率p(0<p<1)和q(q=1-p)向右和向左移动一个单位;若在+1处,则 以概率P反射到2,以概率q停在原处;在s处,则以概率q反射到s-1,以概率P停 在原处。设n表示徘徊n步后的质点位置。{n,n=1,2,…}是一个马尔可夫链,其状 态空间E={1,2,…,S},写出转移矩阵P。 当i=2时 0,当≠2时 q,当=1时 P={P,当=2时 0.其它 p,当=s时 Py={q,当 0,其它
-210- 系统从状态i 转移到其它状态的次数， nij 是由状态i 到状态 j 的转移次数，则 pij 的估 计值 i ij ij n n p = 。计算得 ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 0 1/ 7 4 / 7 2 / 7 4 /11 4 /11 2 /11 1/11 3/11 2 /11 4 /11 2 /11 2 / 5 2 / 5 1/10 1/10 Pˆ Matlab 计算程序如下： format rat clc a=[4 3 2 1 4 3 1 1 2 3 ... 2 1 2 3 4 4 3 3 1 1 ... 1 3 3 2 1 2 2 2 4 4 ... 2 3 2 3 1 1 2 4 3 1]; for i=1:4 for j=1:4 f(i,j)=length(findstr([i j],a)); end end f ni=(sum(f'))' for i=1:4 p(i,:)=f(i,:)/ni(i); end p 例 6（带有反射壁的随机徘徊）如果在原点右边距离原点一个单位及距原点 s(s > 1) 个单位处各立一个弹性壁。一个质点在数轴右半部从距原点两个单位处开始随机徘徊。 每次分别以概率 p(0 < p < 1) 和 q(q = 1− p) 向右和向左移动一个单位；若在+1 处，则 以概率 p 反射到 2，以概率q 停在原处；在 s 处，则以概率 q 反射到 s −1，以概率 p 停 在原处。设ξ n 表示徘徊 n 步后的质点位置。{ ,n = 1,2,L} ξ n 是一个马尔可夫链，其状 态空间 E = {1,2,L,s}，写出转移矩阵 P 。 解 ⎩ ⎨ ⎧ ≠ = = = 当 时 当 时 0， 2 1, 2 { } 0 i i P ξ i ⎪ ⎩ ⎪ ⎨ ⎧ = = = 其它 当 时 当 时 0, , 2 , 1 1 p j q j p j ⎪ ⎩ ⎪ ⎨ ⎧ = − = = 其它 当 时 当 时 0, , 1 , q j s p j s psj
p,当-1=1时 P={q,当-i=-1时(=23…,s-1) 0,其它 因此,P为一个s阶方阵,即 P0g 000 0 0 000 0 p 0000qp 定理1(柯尔莫哥洛夫一开普曼定理)设{n,n=1,2,…}是一个马尔可夫链,其 状态空间E={1,2,…},则对任意正整数m,n有 Pu, (n+m)=2P&(n)Pi, (m) 其中的i,∈E。 定理2设P是一个马氏链转移矩阵(P的行向量是概率向量),PO是初始分布 向量,则第n步的概率分布为 p(n)= p(o)pi 例7若顾客的购买是无记忆的,即已知现在顾客购买情况,未来顾客的购买情况 不受过去购买历史的影响,而只与现在购买情况有关。现在市场上供应A、B、C三个 不同厂家生产的50克袋状味精,用“5n=1”、“5n=2”、“5n=3”分别表示“顾客 第n次购买A、B、C厂的味精”。显然,{5n,n=12,…}是一个马氏链。若已知第 次顾客购买三个厂味精的概率依次为0.2,04,0.4。又知道一般顾客购买的倾向由表2 给出。求顾客第四次购买各家味精的概率。 表2 A B 上次 ABC 0.8 0 0.1 0.1 购买 0.5 0.3 0.2 解第一次购买的概率分布为 02040 0.80.10.1 转移矩阵P=0.50.104 0.50.30.2 则顾客第四次购买各家味精的概率为 P+=PP=[070040.3601636] 23转移概率的渐近性质一极限概率分布
-211- ⎪ ⎩ ⎪ ⎨ ⎧ − = − = − − = = 其它 当 时 当 时 0, , 1 ( 2,3, , 1) , 1 q j i i s p j i pij L 因此， P 为一个 s 阶方阵，即 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = q p q p q q p q p P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 L L L L L L L L L 。 定理 1 （柯尔莫哥洛夫—开普曼定理）设{ ,n = 1,2,L} ξ n 是一个马尔可夫链，其 状态空间 E = {1,2,L}，则对任意正整数 m,n 有 ∑∈ + = k E pij(n m) pik (n) pkj(m) 其中的i, j ∈ E 。 定理 2 设 P 是一个马氏链转移矩阵（ P 的行向量是概率向量）， (0) P 是初始分布 行向量，则第n 步的概率分布为 n n P P P ( ) (0) = 。 例 7 若顾客的购买是无记忆的，即已知现在顾客购买情况，未来顾客的购买情况 不受过去购买历史的影响，而只与现在购买情况有关。现在市场上供应 A、B、C 三个 不同厂家生产的 50 克袋状味精，用“ξ n = 1”、“ξ n = 2 ”、“ξ n = 3”分别表示“顾客 第n 次购买 A、B、C 厂的味精”。显然，{ ,n = 1,2,L} ξ n 是一个马氏链。若已知第一 次顾客购买三个厂味精的概率依次为 0.2，0.4，0.4。又知道一般顾客购买的倾向由表 2 给出。求顾客第四次购买各家味精的概率。 表 2 下 次 购 买 A B C 上次 购买 A B C 0.8 0.5 0.5 0.1 0.1 0.3 0.1 0.4 0.2 解 第一次购买的概率分布为 [ ] 0.2 0.4 0.4 (1) P = 转移矩阵 ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = 0.5 0.3 0.2 0.5 0.1 0.4 0.8 0.1 0.1 P 则顾客第四次购买各家味精的概率为 [0.7004 0.136 0.1636] (4) (1) 3 P = P P = 。 2.3 转移概率的渐近性质—极限概率分布
现在我们考虑,随n的增大,P"是否会趋于某一固定向量?先考虑一个简单例子: 转移矩阵Ps0.50.5 ,当n→+∞时, 0.70.3 1212 又若取l 1212/,则lP=n,u2为矩阵P的对应于特征值=1的特征(概 率)向量,也称为P的不动点向量。哪些转移矩阵具有不动点向量?为此我们给出 正则矩阵的概念。 定义4一个马氏链的转移矩阵P是正则的,当且仅当存在正整数k,使P的每 元素都是正数 定理3若P是一个马氏链的正则阵,那么 (i)P有唯一的不动点向量W,W的每个分量为正。 (i)P的n次幂Pn(n为正整数)随n的增加趋于矩阵W,W的每一行向量均 等于不动点向量W 例8信息的传播一条新闻在a1a2,…,an,…等人中间传播,传播的方式是a1传 给a2,a2传给a3,…如此继续下去,每次传播都是由a1传给a141。每次传播消息的失 真概率是P,0<P<1,即a将消息传给an1时,传错的概率是P,这样经过长时间 传播,第n个人得知消息时,消息的真实程度如何 设整个传播过程为随机转移过程,消息经过一次传播失真的概率为P,转移矩阵 真 假 pp P是正则矩阵。又设V是初始分布,则消息经过n次传播后,其可靠程度的概率分布 为V·Pn 般地,设时齐马氏链的状态空间为E,如果对于所有,j∈E,转移概率P(n) 存在极限 limp(m)=z,(不依赖于i)
-212- 现在我们考虑，随n 的增大， n P 是否会趋于某一固定向量？先考虑一个简单例子： 转移矩阵 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = 0.7 0.3 0.5 0.5 P ，当n → +∞ 时， ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ → 12 5 12 7 12 5 12 7 n P 又若取 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = 12 5 12 7 u ，则uP = u ， T u 为矩阵 T P 的对应于特征值λ = 1的特征（概 率）向量，u 也称为 P 的不动点向量。哪些转移矩阵具有不动点向量？为此我们给出 正则矩阵的概念。 定义４ 一个马氏链的转移矩阵 P 是正则的，当且仅当存在正整数k ，使 k P 的每 一元素都是正数。 定理３ 若 P 是一个马氏链的正则阵，那么： （i） P 有唯一的不动点向量W ，W 的每个分量为正。 （ii）P 的n 次幂 n P （n 为正整数）随n 的增加趋于矩阵W ，W 的每一行向量均 等于不动点向量W 。 例8 信息的传播 一条新闻在a1,a2 ,L,an ,L等人中间传播，传播的方式是 1 a 传 给 2 a ， 2 a 传给a3，…如此继续下去，每次传播都是由ai 传给ai+1 。每次传播消息的失 真概率是 p ，0 < p < 1，即ai 将消息传给ai+1 时，传错的概率是 p ，这样经过长时间 传播，第n 个人得知消息时，消息的真实程度如何？ 设整个传播过程为随机转移过程，消息经过一次传播失真的概率为 p ，转移矩阵 ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ = − − p p p p P 1 1 真 假 假 真 P 是正则矩阵。又设V 是初始分布，则消息经过 n 次传播后，其可靠程度的概率分布 为 n V ⋅ P 。 一般地，设时齐马氏链的状态空间为 E ，如果对于所有i, j ∈ E ，转移概率 p (n) ij 存在极限 ij j n p n = π →∞ lim ( ) ，（不依赖于i ） 或 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = ⎯⎯ → →⎯∞ L L L L L L L L L L L L L L L L j j j n n P n P π π π π π π π π π 1 2 1 2 1 2 ( ) ( )
则称此链具有遍历性。又若∑丌=1,则同时称丌=(x1,m2…)为链的极限分布。 下面就有限链的遍历性给出一个充分条件。 定理4设时齐(齐次)马氏链{n,n=1,2,…}的状态空间为E={a1…,ax}, P=(Pn)是它的一步转移概率矩阵,如果存在正整数m,使对任意的a,a∈E,都 P(m)>0,,j=12,…,N 则此链具有遍历性;且有极限分布丌=(丌1,…,丌x),它是方程组 丌=mP或即x,=∑兀P,j=1…,N 的满足条件 的唯一解 例9根据例7中给出的一般顾客购买三种味精倾向的转移矩阵,预测经过长期的 多次购买之后,顾客的购买倾向如何? 解这个马氏链的转移矩阵满足定理4的条件,可以求出其极限概率分布。为此, 解下列方程组: P1=0.8P1+0.5P2+0.5 P2=0.1p1+0.1p2+0.33 P3=0.1p1+04p2+0.2p3 p1+p2+p3=1 编写如下的 Matlab程序 format rat p=[0.80.10.1;0.50.10.4;0.50.30.2] a=[p'-eye(3);ones(1,3)]; b=[ zeros(3,1);1] P 1m1 或者利用求转移矩阵P的转置矩阵P的特征值1对应的特征(概率)向量,求得极 限概率。编写程序如下: p=[0.80.10.1;0.50.10.4;0.50.30.2] p=sym(p) Ix, y]=eig(p) for i=1: 3 x(:,i)=x(:,i)/sum(x(:,i)) end 求符7,p:28" 这说明,无论第一次顾客购买的情况如何,经过长期多次购买以后,A厂产的味 213
-213- 则称此链具有遍历性。又若∑ = j π j 1，则同时称 ( , , ) π = π 1 π 2 L 为链的极限分布。 下面就有限链的遍历性给出一个充分条件。 定理 4 设时齐（齐次）马氏链{ ,n = 1,2,L} ξ n 的状态空间为 { , , } E = a1 L aN ， ( ) P = pij 是它的一步转移概率矩阵，如果存在正整数 m ，使对任意的ai ,a j ∈ E ，都 有 pij(m) > 0，i, j = 1,2,L,N 则此链具有遍历性；且有极限分布 ( , , ) π = π 1 L π N ，它是方程组 π = πP 或即 ∑= = N i j i pij 1 π π ， j = 1,L, N 的满足条件 π j > 0， 1 1 ∑ = = N j π j 的唯一解。 例 9 根据例 7 中给出的一般顾客购买三种味精倾向的转移矩阵，预测经过长期的 多次购买之后，顾客的购买倾向如何？ 解 这个马氏链的转移矩阵满足定理 4 的条件，可以求出其极限概率分布。为此， 解下列方程组： ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + + = = + + = + + = + + 1 0.1 0.4 0.2 0.1 0.1 0.3 0.8 0.5 0.5 1 2 3 3 1 2 3 2 1 2 3 1 1 2 3 p p p p p p p p p p p p p p p 编写如下的 Matlab 程序： format rat p=[0.8 0.1 0.1;0.5 0.1 0.4;0.5 0.3 0.2]; a=[p'-eye(3);ones(1,3)]; b=[zeros(3,1);1]; p_limit=a\b 或者利用求转移矩阵 P 的转置矩阵 T P 的特征值 1 对应的特征(概率)向量，求得极 限概率。编写程序如下： p=[0.8 0.1 0.1;0.5 0.1 0.4;0.5 0.3 0.2]; p=sym(p'); [x,y]=eig(p) for i=1:3 x(:,i)=x(:,i)/sum(x(:,i)); end x 求得 7 5 p1 = ， 84 11 p2 = ， 84 13 p3 = 。 这说明，无论第一次顾客购买的情况如何，经过长期多次购买以后， A 厂产的味
精占有市场的二,B,C两厂产品分别占有市场的 24吸收链 马氏链还有一种重要类型一吸收链。 若马氏链的转移矩阵为 1234 10.303004 2|0.030203 30030304 000 P的最后一行表示的是,当转移到状态4时,将停留在状态4,状态4称为吸收状态。 如果马氏链至少含有一个吸收状态,并且从每一个非吸收状态出发,都可以到达某 个吸收状态,那么这个马氏链被称为吸收链。 具有r个吸收状态,S(S=n-r)个非吸收状态的吸收链,它的n×n转移矩阵的标 准形式为 P (4) R S 其中L为r阶单位阵,O为r×s零阵,R为sxr矩阵,S为s×s矩阵。从(4)得 (5) (5)式中的子阵S"表示以任何非吸收状态作为初始状态,经过n步转移后,处于S个 非吸收状态的概率。 在吸收链中,令F=(1-S)-,则F称为基矩阵。 对于具有标准形式(即(4)式)转移矩阵的吸收链,可以证明以下定理 定理5吸收链的基矩阵F中的每个元素,表示从一个非吸收状态出发,过程到达 每个非吸收状态的平均转移次数。 定理6设N=FC,F为吸收链的基矩阵,C= ,则N的每个 元素表示从非吸收状态出发,到达某个吸收状态被吸收之前的平均转移次数。 定理7设B=FR=(b),其中F为吸收链的基矩阵,R为(4)式中的子阵, 则b表示从非吸收状态i出发,被吸收状态j吸收的概率。 例10智力竞赛问题甲、乙两队进行智力竞赛。竞赛规则规定:竞赛开始时, 甲、乙两队各记2分,在抢答问题时,如果甲队赢得1分,那么甲队的总分将增加 分,同时乙队总分将减少1分。当甲(或乙)队总分达到4分时,竞赛结束,甲(或乙) 获胜。根据队员的智力水平,知道甲队得1分的概率为P,失去1分的概率为1-p, 求:(i)甲队获胜的概率是多少?(ⅱi)竞赛从开始到结束,分数转移的平均次数是多 少?(ⅲ)甲队获得1、2、3分的平均次数是多少? 分析甲队得分有5种可能,即0、1、2、3、4,分别记为状态a0,a1a2,a3,a4, 其中a0和a4是吸收状态,a1,a2和a3是非吸收状态。过程是以a2作为初始状态。根据
-214- 精占有市场的 7 5 ， B,C 两厂产品分别占有市场的 84 11 ， 84 13 。 2.4 吸收链 马氏链还有一种重要类型—吸收链。 若马氏链的转移矩阵为 ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 0 0 0 1 0 0.3 0.3 0.4 0.2 0.3 0.2 0.3 0.3 0.3 0 0.4 4 3 2 1 1 2 3 4 P ， P 的最后一行表示的是，当转移到状态 4 时，将停留在状态 4，状态 4 称为吸收状态。 如果马氏链至少含有一个吸收状态，并且从每一个非吸收状态出发，都可以到达某 个吸收状态，那么这个马氏链被称为吸收链。 具有 r 个吸收状态，s(s = n − r)个非吸收状态的吸收链，它的n ×n 转移矩阵的标 准形式为 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = R S I O P r （4） 其中 r I 为 r 阶单位阵，O 为 r × s 零阵， R 为 s × r 矩阵， S 为 s × s 矩阵。从（4）得 ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = n n r Q S I O P （5） （5）式中的子阵 n S 表示以任何非吸收状态作为初始状态，经过n 步转移后，处于 s 个 非吸收状态的概率。 在吸收链中，令 1 ( ) − F = I − S ，则 F 称为基矩阵。 对于具有标准形式（即(4)式）转移矩阵的吸收链，可以证明以下定理： 定理 5 吸收链的基矩阵 F 中的每个元素，表示从一个非吸收状态出发，过程到达 每个非吸收状态的平均转移次数。 定理 6 设 N = FC ， F 为吸收链的基矩阵， [ ] T C = 1 1 L 1 ，则 N 的每个 元素表示从非吸收状态出发，到达某个吸收状态被吸收之前的平均转移次数。 定理 7 设 ( ) B = FR = bij ，其中 F 为吸收链的基矩阵， R 为（4）式中的子阵， 则bij 表示从非吸收状态i 出发，被吸收状态 j 吸收的概率。 例 10 智力竞赛问题 甲、乙两队进行智力竞赛。竞赛规则规定：竞赛开始时， 甲、乙两队各记 2 分，在抢答问题时，如果甲队赢得 1 分，那么甲队的总分将增加 1 分，同时乙队总分将减少 1 分。当甲（或乙）队总分达到 4 分时，竞赛结束，甲（或乙） 获胜。根据队员的智力水平，知道甲队赢得 1 分的概率为 p ，失去 1 分的概率为1− p ， 求：（i）甲队获胜的概率是多少？（ii）竞赛从开始到结束，分数转移的平均次数是多 少？（iii）甲队获得 1、2、3 分的平均次数是多少？ 分析 甲队得分有 5 种可能，即 0、1、2、3、4，分别记为状态 0 1 2 3 4 a ,a ,a ,a ,a ， 其中a0和 4 a 是吸收状态， 1 2 a ,a 和a3是非吸收状态。过程是以 2 a 作为初始状态。根据
甲队贏得1分的概率为P,建立转移矩阵 p0p00 (6) P P P a3001-p0p 0000 将(6)式改记为标准形式: 其中 0 S=1-p0 0p 01 0 计算 1-2 P p 因为a2是初始状态,根据定理5,甲队获得1,2,3分的平均次数为,q 1-pg pp N= FC q pq 根据定理6,以a2为初始状态,甲队最终获胜的分数转移的平均次数为2 1-2 又因为 pgp B= FR=- I 2 (-pq)p 215-
-215- 甲队赢得 1 分的概率为 p ，建立转移矩阵： ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − − − = 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 4 3 2 1 0 0 1 2 3 4 p p p p p p a a a a a P a a a a a （6） 将（6）式改记为标准形式： ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = R S I O P 2 其中 ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − = p p R 0 0 0 1 0 ， ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − = − 0 1 0 1 0 0 0 p p p p S ， 计算 ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − − = − = − q q pq q p pq p p pq F I S 1 1 1 1 2 1 ( ) 2 2 1 3 其中 q = 1− p 。 因为 2 a 是初始状态，根据定理 5，甲队获得 1，2，3 分的平均次数为 pq q 1− 2 ， 1 2 pq 1 − ， pq p 1− 2 。又 ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − − = = q q pq q p pq p p pq N FC 1 1 1 1 2 1 2 2 [ ] 2 2 1 2 2 1 2 1 2 1 p p pq + + − = 根据定理 6，以 2 a 为初始状态，甲队最终获胜的分数转移的平均次数为 1 2 pq 2 − 。 又因为 ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − − = = q pq p q p pq p p pq B FR (1 ) (1 ) 1 2 1 3 2 2 3
根据定理7,甲队最后获胜的概率b pq Matlab程序如下 r=[q,0;0,0;0,p]; [0,p,0;q,0,p;0,q,0] f=(eye(3)-s)(-1)if=simple(f) n=f*ones (3, 1)in=simple(n) b=f*ri b=simple(b) §3马尔可夫链的应用 应用马尔可夫链的计算方法进行马尔可夫分析,主要目的是根据某些变量现在的情 况及其变动趋向,来预测它在未来某特定区间可能产生的变动,作为提供某种决策的依 据 例11(服务网点的设置问题)为适应日益扩大的旅游事业的需要,某城市的甲、 乙、丙三个照相馆组成一个联营部,联合经营出租相机的业务。游客可由甲、乙、丙三 处任何一处租出相机,用完后,还在三处中任意一处即可。估计其转移概率如下表所示: 还相机处 甲 甲 租相机处 乙 0.8 0.2 0.3 今欲选择其中之一附设相机维修点,问该点设在哪一个照相馆为最好? 解由于旅客还相机的情况只与该次租机地点有关,而与相机以前所在的店址无 关,所以可用Xn表示相机第n次被租时所在的店址;“Xn=1”、“Xn=2”“Xn=3” 分别表示相机第n次被租用时在甲、乙、丙馆。则{Xn,n=1,2,…}是一个马尔可夫链 其转移矩阵P由上表给出。考虑维修点的设置地点问题,实际上要计算这一马尔可夫 链的极限概率分布。 转移矩阵满足定理4的条件,极限概率存在,解方程组 P1=02P1+0.82+0.1P P2=0.8P1+0.3 P3=0.2P2+06P P2+p2+P3=1 17 得极限概率P-41’P241’P341° 由计算看出,经过长期经营后,该联营部的每架照相机还到甲、乙、丙照相馆的概 率分别为 由于还到甲馆的照相机较多,因此维修点设在甲馆较好。但 由于还到乙馆的相机与还到甲馆的相差不多,若是乙的其它因素更为有利的话,比如, 交通较甲方便,便于零配件的运输,电力供应稳定等等,亦可考虑设在乙馆 习题十七
-216- 根据定理 7，甲队最后获胜的概率 pq p b 1 2 2 22 − = 。 Matlab 程序如下： syms p q r=[q,0;0,0;0,p]; s=[0,p,0;q,0,p;0,q,0]; f=(eye(3)-s)^(-1);f=simple(f) n=f*ones(3,1);n=simple(n) b=f*r;b=simple(b) §3 马尔可夫链的应用 应用马尔可夫链的计算方法进行马尔可夫分析，主要目的是根据某些变量现在的情 况及其变动趋向，来预测它在未来某特定区间可能产生的变动，作为提供某种决策的依 据。 例 11（服务网点的设置问题）为适应日益扩大的旅游事业的需要，某城市的甲、 乙、丙三个照相馆组成一个联营部，联合经营出租相机的业务。游客可由甲、乙、丙三 处任何一处租出相机，用完后，还在三处中任意一处即可。估计其转移概率如下表所示： 还 相 机 处 甲 乙 丙 租相机处 甲 乙 丙 0.2 0.8 0.1 0.8 0 0.3 0 0.2 0.6 今欲选择其中之一附设相机维修点，问该点设在哪一个照相馆为最好？ 解 由于旅客还相机的情况只与该次租机地点有关，而与相机以前所在的店址无 关，所以可用 Xn 表示相机第n 次被租时所在的店址；“ Xn = 1”、“ Xn = 2”、“ Xn = 3 ” 分别表示相机第n 次被租用时在甲、乙、丙馆。则{X ,n = 1,2,L} n 是一个马尔可夫链， 其转移矩阵 P 由上表给出。考虑维修点的设置地点问题，实际上要计算这一马尔可夫 链的极限概率分布。 转移矩阵满足定理 4 的条件，极限概率存在，解方程组 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + + = = + = + = + + 1 0.2 0.6 0.8 0.3 0.2 0.8 0.1 1 2 3 3 2 3 2 1 3 1 1 2 3 p p p p p p p p p p p p p 得极限概率 41 17 p1 = ， 41 16 p2 = ， 41 8 p3 = 。 由计算看出，经过长期经营后，该联营部的每架照相机还到甲、乙、丙照相馆的概 率分别为 41 17 、 41 16 、 41 8 。由于还到甲馆的照相机较多，因此维修点设在甲馆较好。但 由于还到乙馆的相机与还到甲馆的相差不多，若是乙的其它因素更为有利的话，比如， 交通较甲方便，便于零配件的运输，电力供应稳定等等，亦可考虑设在乙馆。 习 题 十 七
