马尔可夫链.doc

马尔可夫链郑小娇 张庆 娄双汇摘要马氏链作为描述一类实际问题的数学模型,在众多的领域内已经取得了极为丰硕的成果.本文由马尔可夫的基本原理，马尔夫链模型，及其应用三大部分构成，简单的介绍了一些马尔可链的基础知识关键词:马尔可夫链,隐马尔可夫链模型,性质，应用引言马尔可夫链，因安德烈•马尔可夫（A.A.Markov，1856－1922）得名，是数学中具有马尔可夫性质的离散时间随机过程该过程中，在给定当前知识或信息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的1 马尔可夫链的定义 一般情况下,当当前状态已知的条件下,将来的状态可能与过去所处的状态A有关,也可能无关.即 ,则称 }是马尔可夫链(Markov chain).马尔可夫链是满足下面两个假设的一种随机过程： 　　1、t+l时刻系统状态的概率分布只与t时刻的状态有关，与t时刻以前的状态无关； 　　2、从t时刻到t+l时刻的状态转移与t的值无关一个马尔可夫链模型可表示为=(S，P，Q)，其中各元的含义如下： 　　1）S是系统所有可能的状态所组成的非空的状态集，有时也称之为系统的状态空间，它可以是有限的、可列的集合或任意非空集。

本文中假定S是可数集(即有限或可列)用小写字母i,j(或Si,Sj)等来表示状态 　　2）是系统的状态转移概率矩阵，其中Pij表示系统在时刻t处于状态i，在下一时刻t+l处于状态i的概率，N是系统所有可能的状态的个数对于任意i∈s，有 3）是系统的初始概率分布，qi是系统在初始时刻处于状态i的概率，满足 2 马尔可夫链的基本性质2.1可还原性马尔可夫链是由一个条件分布来表示的这被称为是随机过程中的“转移概率”这有时也被称作是“一步转移概率”二、三，以及更多步的转移概率可以导自一步转移概率和马尔可夫性质：这些式子可以通过乘以转移概率并求k − 1次积分来一般化到任意的将来时间n + k2.2 周期性边际分布 P(Xn)是在时间为n时的状态的分布初始分布为P(X0)该过程的变化可以用以下的一个时间步幅描述这是Frobenius-Perron equation的一个版本这时可能存在一个或多个状态分布π满足,其中Y只是为了便于对变量积分的一个名义这样的分布π被称作是“平稳分布”（Stationary Distribution）或者“稳态分布”（Steady-state Distribution）。

一个平稳分布是一个对应于特征值为1的条件分布函数的特征方程平稳分布是否存在，以及如果存在是否唯一，这是由过程的特定性质决定的不可约”是指每一个状态都可来自任意的其它状态当存在至少一个状态经过一个固定的时间段后连续返回，则这个过程被称为是“周期的”2.3 重现性2.4 各态历遍性对于一般的两个状态的马氏链,  当 0 < a , b < 1时, Pij ( n )有极限对于固定的j,不管链在某一时刻的什么状态i出发,通过长时间的转移到达j的概率都趋近于π.2.5律动性2.6平稳状态分析和极限分布3可反转马尔可夫链可反转马尔可夫链类似于应用贝叶斯定理来反转一个条件概率:以上就是反转的马尔可夫链因而，如果存在一个π，使得: 那么这个马尔可夫链就是可反转的这个条件也被称为细致平衡 (detailed balance)条件对于所有的i求和: 所以，对于可反转马尔可夫链，π总是一个平稳分布4有限状态空间中的马尔可夫链如果状态空间是有限的，则转移概率分布可以表示为一个具有(i,j)元素的矩阵，称之为“转移矩阵”： 对于一个离散状态空间，k步转移概率的积分即为求和，可以对转移矩阵求k次幂来求得就是说，如果是一步转移矩阵，就是k步转移后的转移矩阵。

平稳分布是一个满足以下方程的向量在此情况下，稳态分布π * 是一个对应于特征根为1的、该转移矩阵的特征向量如果转移矩阵不可约，并且是非周期的，则收敛到一个每一列都是不同的平稳分布 π * ，并且，独立于初始分布π这是由Perron-Frobenius theorem所指出的正的转移矩阵（即矩阵的每一个元素都是正的）是不可约和非周期的矩阵被称为是一个随机矩阵，当且仅当这是某个马尔可夫链中转移概率的矩阵值得注意的是,在上面的定式化中，元素(i,j)是由j转移到i的概率有时候一个由元素(i,j)给出的等价的定式化等于由i转移到j的概率在此情况下，转移矩阵仅是这里所给出的转移矩阵的转置另外，一个系统的平稳分布是由该转移矩阵的左特征向量给出的，而不是右特征向量5隐马尔可夫链模型隐马尔可夫模型（HiddenMarkovModel，HMM），是马尔可夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由一个具有相应概率密度分布的状态序列产生所以，隐马尔可夫模型是一个双重随机过程----具有一定状态数的隐马尔可夫链和显示随机函数集。

自20世纪80年代以来，HMM被应用于语音识别，取得重大成功到了90年代，HMM还被引入计算机文字识别和移动通信核心技术“多用户的检测”近年来，HMM在生物信息科学、故障诊断等领域也开始得到应用 隐含马尔可夫模型是一个数学模型，到目前为之，它一直被认为是实现快速精确的语音识别系统的最成功的方法隐马尔可夫模型（HMM）可以用五个元素来描述，包括2个状态集合和3个概率矩阵： 　1. 隐含状态 S 　这些状态之间满足马尔可夫性质，是马尔可夫模型中实际所隐含的状态这些状态通常无法通过直接观测而得到例如S1、S2、S3等等) 　2. 可观测状态 O 　在模型中与隐含状态相关联，可通过直接观测而得到例如O1、O2、O3等等，可观测状态的数目不一定要和隐含状态的数目一致 　3. 初始状态概率矩阵 π　 　表示隐含状态在初始时刻t=1的概率矩阵，(例如t=1时，P(S1)=p1、P(S2)=P2、P(S3)=p3，则初始状态概率矩阵 π=[ p1 p2 p3 ]. 　4. 隐含状态转移概率矩阵 A 　描述了HMM模型中各个状态之间的转移概率 　其中Aij = P( Sj | Si ),1≤i,,j≤N. 　表示在 t 时刻、状态为 Si 的条件下，在 t+1 时刻状态是 Sj 的概率。

　5. 观测状态转移概率矩阵 B （英文名为Confusion Matrix，直译为混淆矩阵不太易于从字面理解） 　令N代表隐含状态数目，M代表可观测状态数目，则： 　Bij = P( Oi | Sj ), 1≤i≤M,1≤j≤N. 　表示在 t 时刻、隐含状态是 Sj 条件下，观察状态为 Oi 的概率 　总结：一般的，可以用λ=(A,B,π)三元组来简洁的表示一个隐马尔可夫模型隐马尔可夫模型实际上是标准马尔可夫模型的扩展，添加了可观测状态集合和这些状态与隐含状态之间的概率关系6马尔可夫链的科学应用 马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算法编码马尔可夫链也有众多的生物学应用，特别是人口过程，可以帮助模拟生物人口过程的建模隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测 6.1人力资源中的应用 马尔可夫链模型主要是分析一个人在某一阶段内由一个职位调到另一个职位的可能性，即调动的概率该模型的一个基本假设就是，过去的内部人事变动的模式和概率与未来的趋势大体相一致实际上，这种方法是要分析企业内部人力资源的流动趋势和概率，如升迁、转职、调配或离职等方面的情况，以便为内部的人力资源的调配提供依据。

它的基本思想是：通过发现过去组织人事变动的规律，以推测组织在未来人员的供给情况马尔可夫链模型通常是分几个时期收集数据，然后再得出平均值，用这些数据代表每一种职位中人员变动的频率，就可以推测出人员变动情况 具体做法是：将计划初期每一种工作的人数量与每一种工作的人员变动概率相乘，然后纵向相加，即得到组织内部未来劳动力的净供给量其基本表达式为： 　　 Ni(t)：t时间内I类人员数量； Pji：人员从j类向I类转移的转移率； Vi(t)：在时间（t-1,t）I类所补充的人员数 6.2统计中的应用马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码（著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码）6.3生物学中的应用马尔可夫链也有众多的生物学应用，特别是增殖过程，可以帮助模拟生物增殖过程的建模隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测6.4地理学中的应用马尔可夫链最近的应用是在地理统计学（geostatistics）中其中，马尔可夫链用在基于观察数据的二到三维离散变量的随机模拟这一应用类似于“克里金”地理统计学（Kriging geostatistics），被称为是“马尔可夫链地理统计学”。

这一马尔可夫链地理统计学方法仍在发展过程中6.5因特网应用谷歌所使用的网页排序算法（PageRank）就是由马尔可夫链定义的马尔可夫模型也被应用于分析用户浏览网页的行为一阶或者二阶的马尔可夫模型可以用于对一个用户从某一网络链接转移到另一链接的行为进行建模，然后这些模型可以用于对用户之后的浏览行为进行预测6.6马尔可夫模仿文本生成器马尔可夫过程，能为给定样品文本，生成粗略，但看似真实的文本：他们被用于众多供消遣的“模仿生成器”软件马尔可夫链还被用于谱曲6.7 PageRank中的应用 PageRank, 就是网页排名，又称网页级别，是一种由搜索引擎根据网页之间相互的超链接计算的网页排名技术，Google用它来体现网页的重要性是Google的创始人拉里·佩奇和谢尔盖·布林在斯坦福大学发明了这项技术, 并最终以拉里·佩奇（Larry Page）之姓来命名 PageRank 是基于从许多优质的网页链接过来的网页，必定还是优质网页的回归关系，来判定所有网页的重要性提高PageRank的要点，大致有3个：1.反向链接数（单纯的意义上的受欢迎度指标）； 2.反向链接是否来自推荐度高的页面（有根据的受欢迎指标）； 3.反向链接源页面的链接数（被选中的几率指标）。