离散时间马尔可夫链

离散时间马尔可夫链在整数时间点于可数状态集之间移动，其下一个状态的选择概率仅取决于当前状态，这些概率紧凑地编码在转移矩阵中。

Definition

离散时间马尔可夫链是可数集合中随机状态的序列，其中下一个状态的概率仅取决于当前状态，这些一步概率汇集在转移矩阵中。

Scope

本主题涵盖转移矩阵和查普曼-科尔莫戈罗夫方程、强马尔可夫性质、状态分类（分为互通类、瞬态、零常返和正常返）、周期性、通过第一步分析计算的首达概率和期望首达时间，以及整数格上随机游走的常返二分法。

Core questions

• 转移矩阵如何编码链在多个步骤中的动态？
• 状态如何根据其通信结构和常返性进行分类？
• 首达概率和期望首达时间如何计算？
• 哪些随机游走确定会返回起点，哪些会逃逸到无穷远？

Key concepts

• 转移矩阵
• 查普曼-科尔莫戈罗夫方程
• 互通类
• 常返性和瞬态性
• 首达时间

Key theories

强马尔可夫性质

马尔可夫性质在称为停时的合适随机时间点上仍然成立，因此链在这样的时间点从其状态重新开始，这是分析返回、游程和首达时间的关键工具。

常返二分法

每个状态要么是常返的，以概率一无限次访问，要么是瞬态的，只被有限次访问；对于简单对称随机游走，这取决于维度，在一维和二维中是常返的，在三维及更高维度中是瞬态的。

Clinical relevance

离散时间马尔可夫链可用于建模棋盘游戏、库存和排队系统、通过PageRank链进行的网络导航以及遗传和生态演替；其首达时间和常返理论回答了关于系统何时达到目标状态或返回参考条件的实际问题。

History

马尔可夫于1906年引入这些链，将其应用于普希金诗歌中元音和辅音的序列，以证明大数定律适用于相关变量。波利亚在1921年对随机游走的分析确立了与其影响力相关的维度依赖性常返二分法。

Key figures

• Andrey Markov
• George Polya
• Joseph L. Doob

Seminal works

• norris1997

Frequently asked questions

常返状态和瞬态状态有什么区别？

常返状态是链确定会返回的状态，因此会无限次访问，而瞬态状态只被有限次访问，之后链会永远离开。

为什么简单随机游走在低维度是常返的，而在高维度不是？

在一维和二维中，游走以概率一返回原点，但从三维开始有足够的空间逃逸，因此游走只返回有限次并且是瞬态的；这是波利亚的经典结果。