图文详情

历史

在人类发展的历史上，马尔可夫链是第一个从理论上被提出并加以研究的随机过程模型。40

马尔可夫链的提出来自俄国数学家安德雷·马尔可夫（Андрей Андреевич Марков）。为了扩大概率论极限定理的应用范围，1906年，马尔可夫在论文《大数定律关于相依变量的扩展》中第一次提到这种如同锁链般环环相扣的随机变量序列，其特点是：当一些随机变量依次被观测时，随机变量的分布仅仅依赖于前一个被观测的随机变量，而不依赖于更前面的随机变量，这就是被后人称作马尔可夫链的著名概率模型。41

马尔可夫在1906-1907年间发表的研究中为了证明随机变量间的独立性不是弱大数定律（weak law of large numbers）和中心极限定理（central limit theorem）成立的必要条件，构造了一个按条件概率相互依赖的随机过程，并证明其在一定条件下收敛于一组向量，该随机过程被后世称为马尔可夫链156。

在马尔可夫链被提出之后，保罗·埃伦费斯特（Paul Ehrenfest）和Tatiana Afanasyeva在1907年使用马尔可夫链建立了Ehrenfest扩散模型（Ehrenfest model of diffusion）7。1912年亨利·庞加莱（Jules Henri Poincaré）研究了有限群上的马尔可夫链并得到了庞加莱不等式（Poincaré inequality）8。

1931年，安德雷·柯尔莫哥洛夫（Андрей Николаевич Колмогоров）在对扩散问题的研究中将马尔可夫链推广至连续指数集得到了连续时间马尔可夫链，并推出了其联合分布函数的计算公式10。独立于柯尔莫哥洛夫，1926年，Sydney Chapman在研究布朗运动时也得到了该计算公式，即后来的Chapman-Kolmogorov等式10。

1953年，Nicholas Metropolis等通过构建马尔可夫链完成了对流体目标分布函数的随机模拟11，该方法在1970年由Wilfred K. Hastings进一步完善，并发展为现今的梅特罗波利斯-黑斯廷斯算法（Metropolis-Hastings algorithm）12。

1957年，Richard Bellman通过离散随机最优控制模型首次提出了马尔可夫决策过程（Markov Decision Processes, MDP）13。

1959-1962，前苏联数学家Eugene Borisovich Dynkin完善了柯尔莫哥洛夫的理论并通过Dynkin公式（Dynkin formula）将平稳马尔可夫过程与鞅过程（martingale process）相联系1415。

此后以马尔可夫链为基础，更复杂的马尔可夫模型（例如隐马尔可夫模型16和马尔可夫随机场17）被相继提出，并在模式识别等实际问题中得到应用了18。

定义

马尔可夫链是一组具有马尔可夫性质的离散随机变量的集合。具体地，对概率空间内以一维可数集为指标集（index set）的随机变量集合，若随机变量的取值都在可数集内：，且随机变量的条件概率满足如下关系2：

则被称为马尔可夫链，可数集被称为状态空间（state space），马尔可夫链在状态空间内的取值称为状态2。这里定义的马尔可夫链是离散时间马尔可夫链（Discrete-Time MC, DTMC），其具有连续指数集的情形虽然被称为连续时间马尔可夫链（Continuous-Time MC, CTMC），但在本质上是马尔可夫过程（Markov process）。常见地，马尔可夫链的指数集被称为“步”或“时间步（time-step）”2。

上式在定义马尔可夫链的同时定义了马尔可夫性质，该性质也被称为“无记忆性（memorylessness）”，即t+1步的随机变量在给定第t步随机变量后与其余的随机变量条件独立（conditionally independent）：2。在此基础上，马尔可夫链具有强马尔可夫性（strong Markov property），即对任意的停时（ stopping time），马尔可夫链在停时前后的状态相互独立1。

解释性例子

马尔科夫链的一个常见例子是简化的股票涨跌模型：若一天中某股票上涨，则第二天该股票有概率p开始下跌，1-p继续上涨；若一天中该股票下跌，则明天该股票有概率q开始上涨，1-q继续下跌。该股票的涨跌情况是一个马尔可夫链，且定义中各个概念在例子中有如下对应：

随机变量：第t天该股票的状态；状态空间：“上涨”和“下跌”；指数集：天数。
条件概率关系：按定义，即便已知该股票的所有历史状态，其在某天的涨跌也仅与前一天的状态有关。
无记忆性：该股票当天的表现仅与前一天有关，与其他历史状态无关（定义条件概率关系的同时定义了无记忆性）。
停时前后状态相互独立：取出该股票的涨跌记录，然后从中截取一段，我们无法知道截取的是哪一段，因为截取点，即停时t前后的记录（t-1和t+1）没有依赖关系。

n-阶马尔可夫链（n-order Markov chain）

n-阶马尔可夫链拥有n阶的记忆性，可视为马尔可夫链的推广。类比马尔可夫链的定义，n-阶马尔可夫链满足如下条件：

按上式，传统的马尔可夫链可以认为是1-阶马尔可夫链。由马尔可夫性质可得，将多个马尔可夫链作为组元可以得到n-阶的马尔可夫链。

理论与性质

转移理论

马尔可夫链中随机变量的状态随时间步的变化被称为演变（evolution）或转移（transition）。这里介绍描述马尔可夫链结构的两种途径，即转移矩阵和转移图，并定义了马尔可夫链在转移过程中表现出的性质。

转移概率（transition probability）与转移矩阵（transition matrix）

主词条：转移矩阵

马尔可夫链中随机变量间的条件概率可定义为如下形式的（单步）转移概率和n-步转移概率2：

式中下标表示第n步的转移。由马尔可夫性质可知，在给定初始概率后，转移概率的连续乘法可以表示马尔可夫链的有限维分布（finite-dimensional distribution）2：

式中的为样本轨道（sample path），即马尔可夫链每步的取值2。对n-步转移概率，由Chapman–Kolmogorov等式可知，其值为所有样本轨道的总和2：

上式表明，马尔可夫链直接演变n步等价于其先演变n-k步，再演变k步（k处于该马尔可夫链的状态空间内）。n-步转移概率与初始概率的乘积被称为该状态的绝对概率。

若一个马尔可夫链的状态空间是有限的，则可在单步演变中将所有状态的转移概率按矩阵排列，得到转移矩阵2：

马尔可夫链的转移矩阵是右随机矩阵（right stochastic matrix），矩阵的第行表示时取所有可能状态的概率（离散分布），因此马尔可夫链完全决定转移矩阵，转移矩阵也完全决定马尔可夫链。由概率分布的性质可得，转移矩阵是一个正定矩阵，且每行元素之和等于1：按相同的方式也可定义n-步转移矩阵：，由n-步转移概率的性质（Chapman–Kolmogorov等式）可知，n-步转移矩阵是其之前所有转移矩阵的连续矩阵乘法：2。