####本节书摘来自华章出版社《深度学习导论及案例分析》一书中的第2章，第2.9节，作者李玉鑑 张婷，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.9马尔可夫链
从理论上说，前面提到的概率图模型都可以看作是对马尔可夫链（Markov Chain，MC）的推广和发展。因此，马尔可夫链实际上是一种非常经典又相对简单的概率图模型，但它侧重于刻画一个在时间上离散的随机过程。其特点在于，随机变量在下一时刻的取值状态只依赖于当前状态，与之前的状态无关。
一个随机变量序列X1，…，XN称为马尔可夫链，如果它们满足马尔可夫性质：
P（XiX1，…，Xi-1）=P（XiXi-1），i（2.89）
在马尔可夫链中，在随机变量Xi之前的随机变量条件独立于Xi之后的所有随机变量，即
{X1，…，Xi-1}⊥{Xi+1，…，XN}Xi（2.90）
而且，其概率分布P（X1，…，XN）可分解为
P（X1，…，XN）=P（X1）∏Ni=2P（XiXi-1，…，X1）=P（X1）∏Ni=2P（XiXi-1）（2.91）
马尔可夫链可以用如图2.13所示的贝叶斯网络来建模，该网络表达的概率分布为
PB（X1，…，XN）=∏Ni=1P（XiPa=（Xi））=P（X1）∏Ni=2P（XiXi-1）（2.92）
其中Xi的唯一父节点是Xi-1。
马尔可夫链也可以用如图2.14所示的马尔可夫网络来建模，该网络表达的概率分布为：
PM（X1，…，XN）=∏N-1i=1ψCi（Ci）=∏N-1i=1ψCi=P（X1）∏Ni=2P（XiXi-1）（2.93）
其中极大团是Ci={Xi，Xi+1}（i=1，…，N-1），因子ψCi=P（Xi+1Xi）（i=2，…，N-1）且ψC1=P（X1）P（X2X1）。
马尔可夫链还可以用如图2.15所示的因子图（factor graph）来建模，该因子图表达的概率分布为
PM（X1，…，XN）=∏Ni=1fi（Nb（Fi））=P（X1）∏Ni=2P（XiXi-1）（2.94）
其中，因子f1（Nb（F1））=P（X1），且fi（Nb（Fi））=P（XiXi-1）（i=2，…，N）。因子图是由变量节点和因子节点这两类不交节点构成的无向二分概率图（undirected bipartite graph），更多的内容详见参考文献［109］。
马尔可夫链最重要的特点是具有“无记忆性（memorylessness）”，或者称为时间邻域马尔可夫性（temporal neighborhood Markov property），简称马尔可夫性。设Ω是状态空间。如果用pkij（i，j∈Ω）表示一个马尔可夫链在第k个时刻从第i个状态转变到第j个状态的转移概率，那么pkij可以定义如下：
pkij=Pr（Xk+1=jXk=i，Xk-1，…，X1）=Pr（Xk+1=jXk=i）（2.95）
其中，Pr表示概率函数。
如果对所有时刻k≥0，pkij具有相同的值pij（即转移概率并不随着时间而改变），那么马尔可夫链称为齐次的（homogeneous），且矩阵P=（pij）i，j∈Ω称为齐次马尔可夫链的转移矩阵（transition matrix）。
设初始分布μ0是X0的概率分布。如果令μ0=（μ0i）i∈Ω且μ0i=Pr（X0=i），那么Xk的分布μk是μk=μ0Pk。当一个分布π=（πi）i∈Ω满足π=πP时称为稳态分布（stationary distribution）。如果马尔可夫链在时刻k达到稳态分布，那么所有后续状态都将进入稳态分布，即n∈N，μk+n=π。一个分布π关于马尔可夫链稳态的充分条件是满足细致平衡（detailed balance）条件，即：
i，j∈Ω，πipij=πjpji（2.96）
可以证明，如果状态空间是有限的，那么一个不可约（irreducible）且非周期（aperiodic）的马尔可夫链具有唯一稳态分布。不可约是指从任意状态出发经过有限次转移都能够到达任意其他状态，其形式化定义如下：
i，j∈Ω，k>0，Pr（Xk=j|X0=i）>0（2.97）
非周期是指任意状态都不存在重复周期，也就是说不能周期性地转移到它自己，其形式化定义如下：
i∈Ω，gcd{n>0:Pr（Xk=iX0=i）>0}=1（2.98）
其中gcd表示最大公约数。
假设α=（αi）i∈Ω和β=（βi）i∈Ω是有限状态空间Ω上的两个分布。如果把它们的距离定义为：
dV（α，β）=12α-β=12∑i∈Ωαi-βi（2.99）
那么对一个有限状态空间上的不可约、非周期马尔可夫链来说，从任意初始分布μ0出发反复经过其转移矩阵P的作用都可以收敛到唯一的稳态分布π，即：
limk→∞dV（μPk，π）=0（2.100）
