算法大全马氏链模型（Markov chain model of algorithm Daquan）.docVIP

算法大全马氏链模型（Markov chain model of algorithm Daquan） 第十七章马氏链模型 §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 ,n = 1,2,L} 。它是一个随机序列，其状态空间E ={0,1}。 例 2 在m个商店联营出租照相机的业务中（顾客从其中一个商店租出，可以到m 个商店中的任意一个归还），规定一天为一个时间单位， “ξt = j ”表示“第 t天开始营 业时照相机在第 j个商店”， j =1,2,L,m 。则{ξn ,n = 1,2,L} 是一个随机序列，其状 态空间E ={1,2,L,m}。 例 3 统计某种商品在 t时刻的库存量，对于不同的 t，得到一族随机变量， {ξt ,t ∈[0,+∞)}是一个随机过程，状态空间E =[0, R] ，其中R为最大库存量。 我们用一族分布函数来描述随机过程的统计规律。一般地，一个随机过程 {ξt ,t ∈T}，对于任意正整数 n及T中任意n个元素t1,L,tn 相应的随机变量ξt ,L,ξt 1 n 的联合分布函数记为 Ft1Ltn (x1,L, xn ) = P{ξt1 ≤ x1,L,ξtn ≤ xn } （1） 由于n及ti (i =1,L,n) 的任意性，（1）式给出了一族分布函数。记为 {F (x ,L, x ),t ∈T,i = 1,L,n;n = 1,2,L} t Lt 1 ni 1 n 称它为随机过程{ξt ,t ∈T}的有穷维分布函数族。它完整???描述了这一随机过程的统计 规律性。 §2马尔可夫链 2.1马尔可夫链的定义 现实世界中有很多这样的现象：某一系统在已知现在情况的条件下，系统未来时刻 的情况只与现在有关，而与过去的历史无直接关系。比如，研究一个商店的累计销售额， 如果现在时刻的累计销售额已知，则未来某一时刻的累计销售额与现在时刻以前的任一 时刻累计销售额无关。上节中的几个例子也均属此类。描述这类随机现象的数学模型称 为马氏模型。 定义 2 设{ξn ,n = 1,2,L} 是一个随机序列，状态空间 E为有限或可列集，对于任 意的正整数m,n，若i, j,ik ∈ E(k = 1,L,n .1) ，有 -207- P{ξξn+m = j |ξn = i,ξn.1 = in.1,L,ξ1 = i1} = P{ξn+m = j |ξn = i} （2） 则称{ξn ,n = 1,2,L} 为一个马尔可夫链（简称马氏链），（2）式称为马氏性。 事实上，可以证明若等式（ 2）对于 m =1成立，则它对于任意的正整数 m也成立。 因此，只要当 m =1时（2）式成立，就可以称随机序列 {ξn ,n = 1,2,L} 具有马氏性， 即{ξn ,n = 1,2,L} 是一个马尔可夫链。 定义 3 设{ξn ,n = 1,2,L} 是一个马氏链。如果等式（ 2）右边的条件概率与 n无 关，即 P{ξn+m = j |ξn = i} = pij (m) （3） 则称{ξn ,n = 1,2,L} 为时齐的马氏链。称 pij(m) 为系统由状态i经过m个时间间隔（或 m步）转移到状态 j的转移概率。（3）称为时齐性。它的含义是：系统由状态 i到状态 j的转移概率只依赖于时间间隔的长短，与起始的时刻无关。本章介绍的马氏链假定都 是时齐的，因此省略“时齐”二字。 2.2转移概率矩阵及柯尔莫哥洛夫定理 对于一个马尔可夫链{ξn ,n = 1,2,L} ，称以m步转移概率 pij(m) 为元素的矩