一、马尔可夫链及其应用
一、马尔可夫链
随机过程描述的是一个量随时间可能的变化。在这个过程里，每一个时刻变化的方向都是不确定的，随机过程就是由这一系列不确定的随机变量组成的。每一个时刻系统的状态都
由一个随机变量表述，整个过程则构成一个随机过程的实现。
知道了什么是随机过程后，可以试想一个最简单的随机过程，这个过程由 N 步组成，每一步都有两个选择（0，1），那么可能的路径就有 2 的 N 次方个，这个随机过程就要由 这个指数级别个数的概率来描述，而这个指数级别太大，在现实中计算难度较大，所以需要使用马尔可夫过程（Markov Processes）：随机过程的每一步的结果与且仅与上一步有关，与其他无关。
马尔可夫性：在时刻 所处状态为已知的条件下，过程在时刻 所处状态的条件分布过程与时刻 之前所处的状态无关的特性称为马尔可夫性或无后效性。具有马尔可夫性的随机过程称为马尔可夫过程。
马尔可夫链：时间和状态都是离散的马尔可夫过程。
状态空间中经过一个状态到另一个状态的转换随机过程，该过程要求具备无记忆的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关，如图2-9-3 所示。
马尔可夫链是一个随机系统，它必须满足两个条件：
① 系统任意时刻可以用有限个可能状态之一来描述；
② 系统无后效性，即某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。
马尔可夫链的数学表达如下。
状态向量：
● 概率向量的每个元素都是概率，并且元素之和为 1；
● 系统的可能状态数有个；
● 向量中各个元素分别表示第 次观测第 个状态的概率；
● 被称为初始状态。
转移概率矩阵：
● 表示这次观测前状态为，现在观测是状态为 的概率；
●矩阵元素非负；
● 每一行的元素之和都为 1。
根据无后效性，可以得出： 。
从而， 。
由于某一时刻状态转移的情况只依赖前一个状态，那么只要求出系统中任意两个状态之间的转移概率，这个马尔可夫链的模型就确定了。
● 表示这次观测前状态为，现在观测是状态为 的概率；
●矩阵元素非负；
● 每一行的元素之和都为 1。
根据无后效性，可以得出： 。
从而， 。
由于某一时刻状态转移的情况只依赖前一个状态，那么只要求出系统中任意两个状态之间的转移概率，这个马尔可夫链的模型就确定了。 二、马尔可夫链的应用
（一）随机漫步
马尔可夫链的一个典型例子是随机漫步，其每一步的状态是在图形中的点，每一步可以移动到任何一个相邻的点，且移动到每一个点的概率都是相同的，如图 2-9-4所示。随机漫步程序的VBA 语言程序及动态演示可下载
查看。
查看。![[center][size=100] 图 2-9-4 随机漫步示意[/size][size=100][/size][/center]](https://www.geogebra.org/resource/raeshxdw/vH6hdN8qygdm6heH/material-raeshxdw.png)
图 2-9-4 随机漫步示意
（二）病情预测
艾滋病毒感染者病情发展有这样几个阶段（状态）：
① 无临床症状（HIV asymptomatic）；
② 有临床病状（HIV symptomatic）；
③ 获得性免疫缺陷综合征（AIDS）；
④ 死亡（death）。
其转移矩阵如表 2-9-1 所示。
表 2-9-1 艾滋病毒感染者病情转移矩阵
某地区艾滋病感染者一年后由一个状态转移到另一个状态的概率如表 2-9-1 所示。如果目前该地区感染者处于各状态的比例如表 2-9-2 所示。那么三年后，该地区感染者处于各状态的比例如何？
表 2-9-2 艾滋病毒感染者处于各状态的比例
表 2-9-1 就是确定的转移概率矩阵 p ，它是时间齐次性的，也就是转移概率矩阵 p 保持不变，第一年到第二年的转移概率矩阵与第二年到第三年的转移概率矩阵是一样的。
有了这个转移概率矩阵 p ，再加上已知的初期状态分布矩阵 S ，就可以计算该地区第 N年的艾滋病状态分布。
第一年该地区的艾滋病状态分布矩阵 （矩阵相乘），如表 2-9-3 所示。
表 2-9-3 第一年艾滋病状态分布比例
第二年该地区的艾滋病状态分布矩阵 （只和 s1 有关），如表 2-9-4 所示
表 2-9-4 第二年艾滋病状态分布比例
第三年该地区的艾滋病状态分布矩阵 （只和 s2 有关），如表 2-9-5 所示。
表 2-9-5 第三年艾滋病状态分布比例
如果仅仅计算某个感染者的概率，显然病情发展与该患者获得的治疗有着密切关系，但如果研究某个地区的艾滋病患者，那么在无外界因素干预，如国家加大艾滋病治疗投入或艾滋病特效药研发成功等，马尔可夫链模型是个不错的预测模型。
表 2-9-1 就是确定的转移概率矩阵 p ，它是时间齐次性的，也就是转移概率矩阵 p 保持不变，第一年到第二年的转移概率矩阵与第二年到第三年的转移概率矩阵是一样的。
有了这个转移概率矩阵 p ，再加上已知的初期状态分布矩阵 S ，就可以计算该地区第 N年的艾滋病状态分布。
第一年该地区的艾滋病状态分布矩阵 （矩阵相乘），如表 2-9-3 所示。
表 2-9-3 第一年艾滋病状态分布比例
第二年该地区的艾滋病状态分布矩阵 （只和 s1 有关），如表 2-9-4 所示
表 2-9-4 第二年艾滋病状态分布比例
第三年该地区的艾滋病状态分布矩阵 （只和 s2 有关），如表 2-9-5 所示。
表 2-9-5 第三年艾滋病状态分布比例
如果仅仅计算某个感染者的概率，显然病情发展与该患者获得的治疗有着密切关系，但如果研究某个地区的艾滋病患者，那么在无外界因素干预，如国家加大艾滋病治疗投入或艾滋病特效药研发成功等，马尔可夫链模型是个不错的预测模型。
（三）语音识别及自然语言处理
让机器“听懂”人类的语言，需要用到两个马尔可夫模型：
（1）声学模型：利用 HMM 建模（隐马尔可夫模型）。HMM 是指这一马尔可夫模型的内部状态外界不可见，外界只能看到各个时刻的输出值。对于语音识别系统，输出值通常就是从各个帧计算而得的声学特征。
（2）语言模型：N-Gram 算法，简单有效，所以应用也最广泛。它基于独立输入假设：第 个词的出现只与前面 个词相关，而与其他任何词都不相关。整句的概率就是各个词出现概率的乘积。这些概率可以通过直接从语料中统计 个词同时出现的次数得到。
简单来说，人们利用马尔可夫模型，来计算事件的状态转移概率矩阵，除了语音识别，只要随机过程具有马尔可夫性，都少不了应用马尔可夫链。