马尔可夫链(Markov Chain, MC)是概率论和数理统计中具有马尔可夫性质(Markov property)且存在于离散的指数集(index set)和状态空间(state space)内的随机过程(stochastic process) [1-2]。适用于连续指数集的马尔可夫链被称为马尔可夫过程(Markov process),但有时也被视为马尔可夫链的子集,即连续时间马尔可夫链(Continuous-Time MC, CTMC),与离散时间马尔可夫链(Discrete-Time MC, DTMC)相对应,因此马尔可夫链是一个较为宽泛的概念 [2]。
马尔可夫链可通过转移矩阵和转移图定义,除马尔可夫性外,马尔可夫链可能具有不可约性、常返性、周期性和遍历性。一个不可约和正常返的马尔可夫链是严格平稳的马尔可夫链,拥有唯一的平稳分布。遍历马尔可夫链(ergodic MC)的极限分布收敛于其平稳分布 [1]。
- 中文名
- 马尔可夫链
- 外文名
- Markov chain
- 类 型
- 随机过程
- 提出者
- Andrey A. Markov
- 提出时间
- 1906年 [6]
- 学 科
- 统计学
- 应 用
- 数值模拟,机器学习
在人类发展的历史上,马尔可夫链是第一个从理论上被提出并加以研究的随机过程模型。 [40]
马尔可夫链的提出来自俄国数学家安德雷·马尔可夫(Андрей Андреевич Марков)。为了扩大概率论极限定理的应用范围,1906年,马尔可夫在论文《大数定律关于相依变量的扩展》中第一次提到这种如同锁链般环环相扣的随机变量序列,其特点是:当一些随机变量依次被观测时,随机变量的分布仅仅依赖于前一个被观测的随机变量,而不依赖于更前面的随机变量,这就是被后人称作马尔可夫链的著名概率模型。 [41]
马尔可夫在1906-1907年间发表的研究中为了证明随机变量间的独立性不是弱大数定律(weak law of large numbers)和中心极限定理(central limit theorem)成立的必要条件,构造了一个按条件概率相互依赖的随机过程,并证明其在一定条件下收敛于一组向量,该随机过程被后世称为马尔可夫链 [1] [5-6]。
在马尔可夫链被提出之后,保罗·埃伦费斯特(Paul Ehrenfest)和Tatiana Afanasyeva在1907年使用马尔可夫链建立了Ehrenfest扩散模型(Ehrenfest model of diffusion) [7]。1912年亨利·庞加莱(Jules Henri Poincaré)研究了有限群上的马尔可夫链并得到了庞加莱不等式(Poincaré inequality) [8-9]。
1931年,安德雷·柯尔莫哥洛夫(Андрей Николаевич Колмогоров)在对扩散问题的研究中将马尔可夫链推广至连续指数集得到了连续时间马尔可夫链,并推出了其联合分布函数的计算公式 [10]。独立于柯尔莫哥洛夫,1926年,Sydney Chapman在研究布朗运动时也得到了该计算公式,即后来的Chapman-Kolmogorov等式 [10]。
1953年,Nicholas Metropolis等通过构建马尔可夫链完成了对流体目标分布函数的随机模拟 [11],该方法在1970年由Wilfred K. Hastings进一步完善,并发展为现今的梅特罗波利斯-黑斯廷斯算法(Metropolis-Hastings algorithm) [12]。
1959-1962,前苏联数学家Eugene Borisovich Dynkin完善了柯尔莫哥洛夫的理论并通过Dynkin公式(Dynkin formula)将平稳马尔可夫过程与鞅过程(martingale process)相联系 [14-15]。
此后以马尔可夫链为基础,更复杂的马尔可夫模型(例如隐马尔可夫模型 [16]和马尔可夫随机场 [17])被相继提出,并在模式识别等实际问题中得到应用了 [18]。
马尔可夫链是一组具有马尔可夫性质的离散随机变量的集合。具体地,对概率空间 内以一维可数集为指标集(index set) 的随机变量集合 ,若随机变量的取值都在可数集内: ,且随机变量的条件概率满足如下关系 [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-阶马尔可夫链满足如下条件:
马尔可夫链中随机变量的状态随时间步的变化被称为演变(evolution)或转移(transition)。这里介绍描述马尔可夫链结构的两种途径,即转移矩阵和转移图,并定义了马尔可夫链在转移过程中表现出的性质。
转移概率(transition probability)与转移矩阵(transition matrix)
主词条:转移矩阵
上式表明,马尔可夫链直接演变n步等价于其先演变n-k步,再演变k步(k处于该马尔可夫链的状态空间内)。n-步转移概率与初始概率的乘积被称为该状态的绝对概率。
转移图(transition graph)
1. 可达(accessible)与连通(communicate)
若对马尔可夫链中的状态 有: ,即采样路径上的所有转移概率不为0,则状态 是状态 的可达状态,在转移图中表示为有向连接: 。如果 互为可达状态,则二者是连通的,在转移图中形成闭合回路,记为 [1]。由定义,可达与连通可以是间接的,即不必在单个时间步完成。
2. 闭合集(closed set)与吸收态(absorbing state)
给定状态空间的一个子集,若马尔可夫链进入该子集后无法离开: ,则该子集是闭合的,称为闭合集,一个闭合集外部的所有状态都不是其可达状态。若闭合集中只有一个状态,则该状态是吸收态,在转移图中是一个概率为1的自环。一个闭合集可以包括一个或多个连通类。
3. 转移图的例子
这里通过一个转移图的例子对上述概念进行举例说明 [1]:
由定义可知,该转移图包含了三个连通类: 、三个闭合集: 和一个吸收态,即状态6。注意到,在上述转移图中,马尔可夫链从任意状态出发最终都会进入吸收态,这类马尔可夫链被称为吸收马尔可夫链(absorbing Markov chain) [22]。
这里对马尔可夫链的4个性质:不可约性、常返性、周期性和遍历性进行定义。与马尔可夫性质不同,这些性质不是马尔可夫链必然拥有的性质,而是其在转移过程中对其状态表现出的性质。上述性质都是排他的,即不具有可约性的马尔可夫链必然是不可约的,以此类推。
不可约性(irreducibility)
如果一个马尔可夫链的状态空间仅有一个连通类,即状态空间的全体成员,则该马尔可夫链是不可约的,否则马尔可夫链具有可约性(reducibility) [23]。马尔可夫链的不可约性意味着在其演变过程中,随机变量可以在任意状态间转移 [1]。
常返性(recurrence)
若马尔可夫链在到达一个状态后,在演变中能反复回到该状态,则该状态是常返状态,或该马尔可夫链具有(局部)常返性,反之则具有瞬变性(transience)的。正式地,对状态空间中的某个状态,马尔可夫链对一给定状态的返回时间(return time)是其所有可能返回时间的下确界(infimum) [1]:
由上述瞬变性和常返性的定义可有如下推论:
- 1.推论:对有限个状态的马尔可夫链,其至少有一个常返状态,且所有常返状态都是正常返的 [24]。
- 2.推论:若有限个状态的马尔可夫链是不可约的,则其所有状态是正常返的。
- 3.推论:若状态A是可常返的,且状态B是A的可达状态,则A与B是连通的,且B是常返的。
- 4.推论:若状态B是A的可达状态,且状态B是吸收态,则B是常返状态,A是瞬变状态。
- 5.推论:由正常返状态组成的集合是闭合集,但闭合集中的状态未必是常返状态。
周期性(periodicity)
一个正常返的马尔可夫链可能具有周期性,即在其演变中,马尔可夫链能够按大于1的周期常返其状态。正式地,给定具有正常返的状态 ,其返回周期按如下方式计算 [1]:
- 1.推论:吸收态是非周期性状态。
- 2.推论:若状态A与状态B连通,则A与B周期相同 [1]。
- 3.推论:若不可约的马尔可夫链有周期性状态A,则该马尔可夫链的所有状态为周期性状态 [1]。
遍历性(ergodicity)
若马尔可夫链的一个状态是正常返的和非周期的,则该状态具有遍历性 [1]。若一个马尔可夫链是不可还原的,且有某个状态是遍历的,则该马尔可夫链的所有状态都是遍历的,被称为遍历链。由上述定义,遍历性有如下推论:
- 1.推论:若状态A是吸收态,且A是状态B的可达状态,则A是遍历的,B不是遍历的。
- 2.推论:若多个状态的马尔可夫链包含吸收态,则该马尔可夫链不是遍历链。
- 3.推论:若多个状态的马尔可夫链形成有向无环图,或单个闭环,则该马尔可夫链不是遍历链。
遍历链是非周期的平稳马尔可夫链,有长时间尺度下的稳态行为,因此是被广泛研究和应用的马尔可夫链 [1-2]。
这里介绍马尔可夫链的长时间尺度行为的描述,即平稳分布和极限分布,并定义平稳马尔可夫链。
平稳分布(stationary distribution)
给定一个马尔可夫链,若在其状态空间存在概率分布 ,且该分布满足以下条件:
对不可约的马尔可夫链,当且仅当其存在唯一平稳分布,即平衡方程 在正单纯形上有唯一解时,该马尔可夫链是正常返的,且平稳分布有如下表示 [1] [23]:
极限分布(limiting distribution)
若一个马尔可夫链的状态空间存在概率分布 并满足如下关系:
1. 极限定理(limiting theorem)
两个独立的非周期平稳马尔可夫链,即遍历链如果有相同的转移矩阵,那么当时间步趋于无穷时,两者极限分布间的差异趋于0。按随机过程中的耦合(coupling)理论,该结论的表述为:对状态空间相同的遍历链 ,给定任意初始分布后有 [2]:
2. 遍历定理(ergodic theorem)
若一个马尔可夫链为遍历链,则由遍历定理,其对某一状态的访问次数与时间步的比值,在时间步趋于无穷时趋近于平均返回时间的倒数,即该状态的平稳分布或极限分布 [1]:
平稳马尔可夫链(stationary Markov chain)
伯努利过程(Bernoulli process)
主词条:伯努利过程
伯努利过程也被称为二项马可夫链(Binomial Markov chain),其建立过程如下:给定一系列相互独立的“标识”,每个标识都是二项的,按概率 取正和负。令正随机过程 表示n个标识中有k个正标识的概率,则其是一个伯努利过程,其中的随机变量服从二项分布(binomial distribution) [2]:
赌徒破产问题(gambler's ruin)
参见:赌徒输光定理
假设赌徒持有有限个筹码在赌场下注,每次下注以概率 赢或输一个筹码,若赌徒不断下注,则其持有的筹码总数是一个马尔可夫链,且有如下转移矩阵 [2]:
随机游走(random walk)
主词条:随机游走
定义一系列独立同分布(independent identically distributed, iid)的整数随机变量 ,并定义如下随机过程 [2]:
则随机过程 是整数集内的随机游走,而 是步长。由于步长是iid的,因此当前步与先前步相互独立,该随机过程是马尔可夫链 [2]。伯努利过程和赌徒破产问题都是随机游走的特例 [2]。
由上述随机游走的例子可知,马尔可夫链有一般性的构建方法,具体地,若状态空间 内的随机过程 有满足形式 [2]:
马尔可夫过程(Markov process)
主词条:马尔可夫过程
马尔可夫过程也被称为连续时间马尔可夫链,是马尔可夫链或离散时间马尔可夫链的推广,其状态空间是可数集,但一维指数集不再有可数集的限制,可以表示连续时间。马尔可夫过程与马尔可夫链的性质是可以类比的,其马尔可夫性质通常有如下表示 [2]:
马尔可夫模型(Markov model)
主词条:马尔可夫模型
马尔可夫链或马尔可夫过程不是唯一以马尔可夫性质为基础建立的随机过程,事实上,隐马尔可夫模型、马尔可夫决策过程、马尔可夫随机场等随机过程/随机模型都具有马尔可夫性质并被统称为马尔可夫模型。这里对马尔可夫模型的其它成员做简要介绍:
1. 隐马尔可夫模型(Hidden Markov Model, HMM)
HMM是一个状态空间不完全可见,即包含隐藏状态(hidden status)的马尔可夫链,HMM中可见的部分被称为输出状态(emission state),与隐藏状态有关,但不足以形成完全的对应关系。以语音识别(speech recognition)为例,需要识别的语句是不可见的隐藏状态,接收的语音或音频是和语句有关的输出状态,此时HMM常见的应用是基于马尔可夫性质从语音输入推出其对应的语句,即从输出状态反解隐藏状态 [16] [18]。
2. 马尔可夫决策过程(Markov decision process, MDP):
MDP是在状态空间的基础上引入了“动作”的马尔可夫链,即马尔可夫链的转移概率不仅与当前状态有关,也与当前动作有关。MDP包含一组交互对象,即智能体(agent)和环境,并定义了5个模型要素:状态(state)、动作(action)、策略(policy)、奖励(reward)和回报(return),其中策略是状态到动作的映射,回报是奖励随时间步的折现或积累。在MDP的演化中,智能体对环境的初始状态进行感知,按策略实施动作,环境受动作影响进入新的状态并反馈给智能体一个奖励。智能体接收“奖励”并采取新的策略,与环境持续交互。MDP是强化学习(reinforcement learning)的数学模型之一,被用于模拟智能体可实现的随机性策略与回报 [30]。MDP的推广之一是部分可观察马尔可夫决策过程(partially observable Markov decision process, POMDP),即考虑了HMM中隐藏状态和输出状态的MDP [30]。
3. 马尔可夫随机场(Markov Random Field, MRF)
MRF是马尔可夫链由一维指数集向高维空间的推广。MRF的马尔可夫性质表现为其任意一个随机变量的状态仅由其所有邻接随机变量的状态决定。 类比马尔可夫链中的有限维分布,MRF中随机变量的联合概率分布是所有包含该随机变量的团(cliques)的乘积。MRF最常见的例子是伊辛模型(Ising model) [17] [31]。
哈里斯链(Harris chain)
哈里斯链是马尔可夫链从可数状态空间向连续状态空间的推广,给定可测空间 上的平稳马尔可夫链 ,若对可测空间的任意子集 和子集的返回时间 ,该马尔可夫链满足 [32]:
构建以采样分布为极限分布的马尔可夫链是马尔可夫链蒙特卡罗(Markov Chain Monte Carlo, MCMC)的核心步骤,MCMC通过在马尔可夫链上不断迭代时间步以得到近似服从采样分布的随机数,并使用这些随机数逼近求解目标对采样分布的数学期望 [2-3]:
在物理学和化学中,马尔可夫链和马尔可夫过程被用于对动力系统进行建模,形成了马尔可夫动力学(Markov dynamics) [34-35]。 在排队论(queueing theory)中,马尔可夫链是排队过程的基本模型 [36]。在信号处理方面,马尔可夫链是一些序列数据压缩算法,例如Ziv-Lempel编码的数学模型 [37-38],在金融领域,马尔可夫链模型被用于预测企业产品的市场占有率 [39]。
随着马尔可夫链的逐步深人研究,它在经济学、生物学、物理学、化学、军事学 天文学等领域都引起了连锁反应,衍生出一系列新课题、新理论和新学科。马尔可夫链具有丰富的数学理论,与其他数学学科相互渗透;而它又与自然科学、技术科学、管理科学、经济科学以至人文科学有广泛的交叉应用。很多问题都可建立马尔可夫过程概率模型,运用概率论及随机过程的理论及方法进行研究,而它们又不断地衍生出新的研究课题。这种交互作用促进了当代概率论的飞速发展。而当前马尔可夫链的理论研究,正方兴未艾。 [40]