跳转到内容

马可夫过程

本页使用了标题或全文手工转换
维基百科,自由的百科全书
马可夫过程范例

概率论统计学中,马可夫过程(英语:Markov process)是一个具备了马可夫性质随机过程,因为俄国数学家安德雷·马可夫得名。马可夫过程是不具备记忆特质的(memorylessness)。换言之,马可夫过程的条件概率仅仅与系统的当前状态相关,而与它的过去历史或未来状态,都是独立、不相关的[1]

具备离散状态的马可夫过程,通常被称为马可夫链。马可夫链通常使用离散的时间集合定义,又称离散时间马可夫链[2]。有些学者虽然采用这个术语,但允许时间可以取连续的值[3]

概论

[编辑]
可数或有限的状态空间 连续或一般的状态空间
离散时间 在可数且有限状态空间下的马可夫链 Harris chain (在一般状态空间下的马可夫链)
连续时间 Continuous-time Markov process 任何具备马可夫性质的连续随机过程,例如维纳过程

历史

[编辑]

安德烈·马尔可夫于20世纪初开始研究马尔可夫过程,并于1906年发表了关于这一主题的第一篇论文[4][5]。不过,连续时间马尔可夫过程的一种形式,即泊松过程,早在马尔可夫的工作之前就已被发现[6]

马尔可夫对这一领域的兴趣源于他与帕维尔·涅克拉索夫之间的学术争论。涅克拉索夫主张,随机变量独立性大数弱定律成立的必要条件。马尔可夫试图构造反例来否定这一论断[7]。在1906年的论文中,马尔可夫证明了在特定条件下,马尔可夫链的平均结果会收敛到一组固定值,从而在不依赖独立性假设的前提下证明了大数弱定律[4][5]。此后,马尔可夫利用马尔可夫链分析了亚历山大·普希金的长篇诗体小说《叶甫盖尼·奥涅金》中元音辅音的分布规律,并为此类链证明了中心极限定理[4]

1912年,亨利·庞加莱有限群上研究马尔可夫链,目的是分析洗牌问题[4]。马尔可夫链的早期应用还包括保罗·埃伦费斯特塔季扬娜·埃伦费斯特英语Tatyana Afanasyeva于1907年提出的扩散模型,以及弗朗西斯·高尔顿亨利·威廉·沃森英语Henry William Watson于1873年提出的分支过程[4]。后者的工作实际上早在约三十年前就由伊雷内-儒勒·比安内梅英语Irénée-Jules Bienaymé独立发现[8]。从1928年起,莫里斯·弗雷歇开始关注马尔可夫链的研究,并于1938年出版了一部系统性的马尔可夫链专著[4]

1931年,安德雷·柯尔莫哥洛夫发表论文,建立了连续时间马尔可夫过程的大部分早期理论[9]。柯尔莫哥洛夫的研究在一定程度上受到路易·巴舍利耶1900年关于股市波动的工作以及诺伯特·维纳关于爱因斯坦布朗运动模型的工作的启发[9]。他引入并研究了一类被称为扩散过程的马尔可夫过程,并推导出了描述这些过程的一组微分方程[9]。与此独立地,悉尼·查普曼英语Sydney Chapman (mathematician)于1928年在研究布朗运动的过程中,以不如柯尔莫哥洛夫严格的数学方式推导出了一个方程,即现在所称的查普曼-柯尔莫哥洛夫方程[10]。上述微分方程现通称柯尔莫哥洛夫方程[11]

此后,对马尔可夫过程理论基础做出重要贡献的数学家还包括自20世纪30年代起开展工作的威廉·费勒,以及自20世纪50年代起开展工作的叶甫根尼·迪恩金[12]

示例

[编辑]

随机漫步

[编辑]

随机漫步是马尔可夫链最经典的例子之一。设想一个人站在数轴上的某个整数位置,每一步以相等的概率向左或向右移动一格。从任意位置出发,都只有两种可能的转移:移动到前一个整数或后一个整数。例如,从位置5出发,转移到4和6的概率各为0.5,转移到其他任何位置的概率为0。这些转移概率仅取决于当前位置,而与到达该位置的方式无关,无论此前经过了哪些位置,结果都是一样的。这一特征正是马尔可夫性质的体现。

随机漫步赌徒破产问题都是离散时间马尔可夫过程的实例[13]。另外两个重要的连续时间马尔可夫过程是维纳过程(即布朗运动)和泊松过程,它们被认为是随机过程理论中最基本的过程[14]

汉字序列中的马尔可夫性

[编辑]

马尔可夫当年利用马尔可夫链分析了普希金叶甫盖尼·奥涅金》中元音与辅音的交替规律。类似的思路也可以应用于汉字序列的分析。

在中文文本中,前后汉字之间存在很强的统计关联。例如,当前一个字为“中”时,后续出现“国”“文”“心”“间”等字的概率远高于“猫”“椅”等字。如果将每个汉字视为一个状态,将文本中相邻两字之间的接续频率作为转移概率的估计,就可以构建一个以汉字为状态空间的马尔可夫链模型。在这个模型中,下一个字的出现概率仅取决于当前字,而与更早的文本内容无关。

这种基于马尔可夫链的汉字序列建模方式在中文自然语言处理中有广泛应用。例如,简体中文拼音输入法的候选词排序就利用了类似的原理:系统根据当前已输入的字来预测最有可能的下一个字,从而提高输入效率[15]注音输入法也遵循同样的原理,只是将拼音字母替换为注音符号作为观测序列。不过,实际的输入法系统通常采用更复杂的模型(如隐马尔可夫模型n元语法模型),以捕捉更长距离的上下文依赖。

形式化定义

[编辑]

离散时间马尔可夫链

[编辑]

离散时间马尔可夫链是一列随机变量 ,满足马尔可夫性质,即转移到下一个状态的概率仅取决于当前状态,而与之前的状态无关:

其中要求上述条件概率有定义,即 所有可能取值构成的可数集合 称为该链的状态空间

时齐性与平稳性

[编辑]

若对所有 均有

则称该链为时齐的,即转移概率不随时间步变化。

若对所有 均有

则称该链为平稳的。由贝叶斯定理可知,每个平稳链都是时齐的。时齐马尔可夫链为平稳链的充要条件是 的分布为该链的平稳分布。

有限状态空间与转移矩阵

[编辑]

若状态空间为有限集合,则转移概率分布可用一个矩阵表示,称为转移矩阵 ,其第 个元素为

由于 的每一行元素之和为1,且所有元素非负,因此 是一个右随机矩阵

对于时齐链, 步转移概率可通过对转移矩阵求 次幂得到,即

平稳分布

[编辑]

平稳分布 是一个行向量,其元素非负且和为1,满足

将此定义与特征向量的定义对比可知,平稳分布 是转移矩阵 对应于特征值1的归一化左特征向量。

若马尔可夫链是不可约非周期的,则存在唯一的平稳分布 ,并且 收敛到一个每行均为 的矩阵[16]

其中 是所有元素均为1的列向量。这一结论由佩龙-弗罗贝尼乌斯定理保证。

高阶马尔可夫链

[编辑]

阶数为 的马尔可夫链(又称具有记忆的马尔可夫链)满足

即未来状态取决于过去 个状态。通过将相邻 个状态的有序组 定义为新的状态,可以将高阶链转化为一阶马尔可夫链。

连续时间马尔可夫链

[编辑]

连续时间马尔可夫链 由状态空间 转移速率矩阵 和初始分布共同定义。对于 ,元素 为非负实数,描述过程从状态 转移到状态 的速率。对角元素 的取值使得 的每行之和为零:

直观地说,当过程处于状态 时,它在该状态停留一段服从参数为 指数分布的随机时间,然后以概率 转移到状态 。连续时间链的转移概率满足柯尔莫哥洛夫前向方程

其中 单位矩阵

应用

[编辑]

马尔可夫链在自然科学、社会科学和工程技术中有广泛应用。以下列举几个主要领域。

统计学与蒙特卡洛方法

[编辑]

马尔可夫链蒙特卡洛(Markov chain Monte Carlo,简称MCMC)方法利用精心构造的马尔可夫链,从复杂的概率分布中生成样本。其核心思想是构造一条以目标分布为平稳分布的马尔可夫链,使链在经过足够多步转移后,所处状态的分布近似于目标分布。常见的MCMC算法包括Metropolis-Hastings算法吉布斯采样。MCMC方法极大地推动了贝叶斯推断的实际应用,使得对复杂后验分布的数值计算成为可能[17]

搜索引擎与网页排名

[编辑]

GooglePageRank算法将整个互联网建模为一条马尔可夫链:每个网页是一个状态,网页之间的超链接定义了转移概率。一个“随机浏览者”在当前页面上以概率 随机点击页面中的某个链接,以概率 跳转到互联网上任意一个页面(参数 通常取0.85)。每个网页的PageRank值即为该马尔可夫链平稳分布中对应状态的概率。PageRank值越高的网页被认为越重要,从而在搜索结果中排名越靠前[18]

强化学习

[编辑]

马尔可夫决策过程(Markov decision process,简称MDP)是马尔可夫链引入“动作”和“奖励”后的推广,构成了强化学习的数学基础[19]。在MDP框架中,智能体在每个时间步观察当前状态,选择一个动作,获得相应的奖励,并依据转移概率进入下一个状态。智能体的目标是学习一种“策略”,使累积奖励的期望值最大化。AlphaGo等围棋程序、自动驾驶决策系统以及大语言模型的人类反馈强化学习(RLHF)训练,都以MDP为理论框架。

信息论与自然语言处理

[编辑]

克劳德·香农在1948年奠定信息论的开创性论文中,将自然语言文本建模为遍历马尔可夫过程,以此引入了信息熵的概念[20]。这一思路后来衍生出多种应用,包括基于马尔可夫模型的数据压缩算法(如LZMA)和隐马尔可夫模型语音识别词性标注等任务中的广泛使用。

物理学与化学

[编辑]

马尔可夫过程在热力学统计力学中有广泛应用。当系统的动力学可认为与时间无关,且当前状态已包含所有相关信息时,就可以用马尔可夫过程来描述。在计算物理学中,格点量子色动力学的数值模拟依赖于马尔可夫链方法。在化学领域,化学反应网络可以建模为连续时间马尔可夫链,其中状态为各化学物种的分子数,反应为链的可能转移。经典的米氏方程模型也可以视为一条马尔可夫链。

经济学与金融

[编辑]

马尔可夫链在金融和经济学中被用于建模多种现象。路易·巴舍利耶最早观察到股票价格遵循随机漫步詹姆斯·汉密尔顿于1989年利用马尔可夫链对经济周期中高增长和低增长时期的切换进行建模,推动了“机制转换模型”的流行[21]信用评级机构也利用马尔可夫链的转移矩阵来描述不同信用等级之间的年度迁移概率。

排队论

[编辑]

马尔可夫链是排队论分析的基础。阿格纳·厄尔朗于1917年率先将马尔可夫链应用于电话网络的排队分析[22],此后该方法在通信网络优化中发挥了关键作用。例如,经典的M/M/1队列可以用一条定义在非负整数上的连续时间马尔可夫链来精确描述。

参考文献

[编辑]
  1. ^ Markov process (mathematics)页面存档备份,存于互联网档案馆) - Britannica Online Encyclopedia
  2. ^ Everitt,B.S. (2002) The Cambridge Dictionary of Statistics. CUP. ISBN 0-521-81099-x
  3. ^ Dodge, Y. The Oxford Dictionary of Statistical Terms, OUP. ISBN 0-19-920613-9
  4. ^ 4.0 4.1 4.2 4.3 4.4 4.5 Charles Miller Grinstead; James Laurie Snell. Introduction to Probability. American Mathematical Soc. 1997: 464–466. ISBN 978-0-8218-0749-1. 
  5. ^ 5.0 5.1 Hayes, Brian. First links in the Markov chain. American Scientist. 2013, 101 (2): 92–96. doi:10.1511/2013.101.92. 
  6. ^ Sheldon M. Ross. Stochastic processes. Wiley. 1996: 235, 358. ISBN 978-0-471-12062-9. 
  7. ^ Seneta, E. Markov and the Birth of Chain Dependence Theory. International Statistical Review. 1996, 64 (3): 255–257. JSTOR 1403785. doi:10.2307/1403785. 
  8. ^ Seneta, E. I.J. Bienaymé [1796–1878]: Criticality, Inequality, and Internationalization. International Statistical Review. 1998, 66 (3): 291–292. JSTOR 1403518. doi:10.2307/1403518. 
  9. ^ 9.0 9.1 9.2 Kendall, D. G.; et al. Andrei Nikolaevich Kolmogorov (1903–1987). Bulletin of the London Mathematical Society. 1990, 22 (1): 33. doi:10.1112/blms/22.1.31. 
  10. ^ Bernstein, Jeremy. Bachelier. American Journal of Physics. 2005, 73 (5): 395–398. Bibcode:2005AmJPh..73..395B. doi:10.1119/1.1848117. 
  11. ^ William J. Anderson. Continuous-Time Markov Chains: An Applications-Oriented Approach. Springer Science & Business Media. 2012: vii. ISBN 978-1-4612-3038-0. 
  12. ^ Cramér, Harald. Half a Century with Probability Theory: Some Personal Recollections. The Annals of Probability. 1976, 4 (4): 509–546. doi:10.1214/aop/1176996025可免费查阅. 
  13. ^ Ionut Florescu. Probability and Stochastic Processes. John Wiley & Sons. 2014: 373–374. ISBN 978-1-118-59320-2. 
  14. ^ Emanuel Parzen. Stochastic Processes. Courier Dover Publications. 2015: 7–8. ISBN 978-0-486-79688-8. 
  15. ^ 宗成庆. 统计自然语言处理 第2版. 清华大学出版社. 2013. ISBN 978-7-302-33069-2 请检查|isbn=值 (帮助). 
  16. ^ Serfozo, Richard. Basics of Applied Stochastic Processes. Springer. 2009. ISBN 978-3-540-89331-8. doi:10.1007/978-3-540-89332-5. 
  17. ^ Dani Gamerman; Hedibert F. Lopes. Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference 2nd. CRC Press. 2006. ISBN 978-1-58488-587-0. 
  18. ^ Page, Lawrence; Brin, Sergey; Motwani, Rajeev; Winograd, Terry. The PageRank Citation Ranking: Bringing Order to the Web (技术报告). 1999. CiteSeerX 10.1.1.31.1768可免费查阅. 
  19. ^ Richard S. Sutton; Andrew G. Barto. Reinforcement Learning: An Introduction 2nd. MIT Press. 2018. ISBN 978-0-262-03924-6. 
  20. ^ Thomsen, Samuel W. Some evidence concerning the genesis of Shannon's information theory. Studies in History and Philosophy of Science. 2009, 40 (1): 81–91. doi:10.1016/j.shpsa.2008.12.011. 
  21. ^ Hamilton, James. A new approach to the economic analysis of nonstationary time series and the business cycle. Econometrica. 1989, 57 (2): 357–384. JSTOR 1912559. doi:10.2307/1912559. 
  22. ^ 约翰·J·奥康纳; 埃德蒙·F·罗伯逊, Erlang, MacTutor数学史档案 (英语) 

参见

[编辑]