算法大全第17章 马氏链模型.pdf

《算法大全第17章 马氏链模型.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十七章马氏链模型§1随机过程的概念一个随机试验的结果有多种可能性，在数学上用一个随机变量（或随机向量）来描述。在许多情况下，人们不仅需要对随机现象进行一次观测，而且要进行多次，甚至接连不断地观测它的变化过程。这就要研究无限多个，即一族随机变量。随机过程理论就是研究随机现象变化过程的概率规律性的。定义1设{ξ,t∈T}是一族随机变量，T是一个实数集合，若对任意实数t∈T,ξtt是一个随机变量，则称{ξ,t∈T}为随机过程。tT称为参数集合，参数t可以看作时间。ξ的每一个可能取值称为随机过程的一个t状态。其全体可能取值所构成的集合称

2、为状态空间，记作E。当参数集合T为非负整数集时，随机过程又称随机序列。本章要介绍的马尔可夫链就是一类特殊的随机序列。例1在一条自动生产线上检验产品质量，每次取一个，“废品”记为1，“合格品”记为0。以ξ表示第n次检验结果，则ξ是一个随机变量。不断检验，得到一列随机nn变量ξ,ξ,L，记为{ξ,n=1,2,L}。它是一个随机序列，其状态空间E={0,1}。12n例2在m个商店联营出租照相机的业务中（顾客从其中一个商店租出，可以到m个商店中的任意一个归还），规定一天为一个时间单位，“ξ=j”表示“第t天开始营t业时照相机在第j个商店”

3、，j=1,2,L,m。则{ξ,n=1,2,L}是一个随机序列，其状n态空间E={1,2,L,m}。例3统计某种商品在t时刻的库存量，对于不同的t，得到一族随机变量，{ξ,t∈[0,+∞)}是一个随机过程，状态空间E=[0,R]，其中R为最大库存量。t我们用一族分布函数来描述随机过程的统计规律。一般地，一个随机过程{ξ,t∈T}，对于任意正整数n及T中任意n个元素t,L,t相应的随机变量ξ,L,ξt1nt1tn的联合分布函数记为F(x,L,x)=P{ξ≤x,L,ξ≤x}（1）t1Ltn1nt11tnn由于n及t(i=1,L,n)的任

4、意性，（1）式给出了一族分布函数。记为i{F(x,L,x),t∈T,i=1,L,n;n=1,2,L}t1Ltn1ni称它为随机过程{ξ,t∈T}的有穷维分布函数族。它完整地描述了这一随机过程的统计t规律性。§2马尔可夫链2.1马尔可夫链的定义现实世界中有很多这样的现象：某一系统在已知现在情况的条件下，系统未来时刻的情况只与现在有关，而与过去的历史无直接关系。比如，研究一个商店的累计销售额，如果现在时刻的累计销售额已知，则未来某一时刻的累计销售额与现在时刻以前的任一时刻累计销售额无关。上节中的几个例子也均属此类。描述这类随机现象的数

5、学模型称为马氏模型。定义2设{ξ,n=1,2,L}是一个随机序列，状态空间E为有限或可列集，对于任n意的正整数m,n，若i,j,i∈E(k=1,L,n−1)，有k-207-P{ξ=j

6、ξ=i,ξ=i,L,ξ=i}=P{ξ=j

7、ξ=i}（2）n+mnn−1n−111n+mn则称{ξ,n=1,2,L}为一个马尔可夫链（简称马氏链），（2）式称为马氏性。n事实上，可以证明若等式（2）对于m=1成立，则它对于任意的正整数m也成立。因此，只要当m=1时（2）式成立，就可以称随机序列{ξ,n=1,2,L}具有马氏性，n即{ξ,n=1,2,L}

8、是一个马尔可夫链。n定义3设{ξ,n=1,2,L}是一个马氏链。如果等式（2）右边的条件概率与n无n关，即P{ξ=j

9、ξ=i}=p(m)（3）n+mnij则称{ξ,n=1,2,L}为时齐的马氏链。称p(m)为系统由状态i经过m个时间间隔（或nijm步）转移到状态j的转移概率。（3）称为时齐性。它的含义是：系统由状态i到状态j的转移概率只依赖于时间间隔的长短，与起始的时刻无关。本章介绍的马氏链假定都是时齐的，因此省略“时齐”二字。2.2转移概率矩阵及柯尔莫哥洛夫定理对于一个马尔可夫链{ξ,n=1,2,L}，称以m步转移概率p(m)为

10、元素的矩阵nijP(m)=(p(m))为马尔可夫链的m步转移矩阵。当m=1时，记P(1)=P称为马尔可ij夫链的一步转移矩阵，或简称转移矩阵。它们具有下列三个基本性质：（i）对一切i,j∈E，0≤p(m)≤1；ij（ii）对一切i∈E，∑pij(m)=1；j∈E⎧1,当i=j时（iii）对一切i,j∈E，pij(0)=δij=⎨。⎩0，当i≠j时当实际问题可以用马尔可夫链来描述时，首先要确定它的状态空间及参数集合，然后确定它的一步转移概率。关于这一概率的确定，可以由问题的内在规律得到，也可以由过去经验给出，还可以根据观测数据来估计

11、。例4某计算机机房的一台计算机经常出故障，研究者每隔15分钟观察一次计算机的运行状态，收集了24小时的数据（共作97次观察）。用1表示正常状态，用0表示不正常状态，所得的数据序列如下：11100100111111100111101111110011