3.2　马尔可夫链

马尔可夫链是一种离散状态的马尔可夫序列，也是一般性马尔可夫序列的特殊形式。马尔可夫链的状态空间具有离散和有限性：qt∈{s(j), j=1, 2, …, N}。每一个离散值都与马尔可夫链中的一个状态相关。因为状态s(j)与它的索引j一一对应，我们通常可交替使用这两者。

一个马尔可夫链可被转移概率完全表示，定义为

以及初始状态分布概率。如果这些转移概率与时间t无关，则得到齐次马尔可夫链。

（齐次）马尔可夫链的转移概率通常能被方便地表示为矩阵形式

A被称为马尔可夫链的转移矩阵。给定马尔可夫链的转移概率，则状态输出概率

pj(t)≈P[qt=s(j)]

很容易计算得到。根据下式可知该计算是递归的：

如果马尔可夫链的状态占有分布渐进收敛：pi(t)→π(q(i)），则当t→∞时，我们称p(s(i)）为马尔可夫链的一个稳态分布。对有稳态分布的马尔可夫链来说，它的转移概率aij必须满足

马尔可夫链的稳态分布在一类被统称为马尔可夫链蒙特卡罗（MCMC）方法的强大的统计方法中起着重要作用。这些方法用来模拟（即采样）任意复杂的分布函数，使其能执行很多复杂的统计推断和学习任务，否则这些任务运算困难。MCMC方法的理论基础是马尔可夫链到它的稳态分布的渐进收敛。也就是说，无论初始分布如何，马尔可夫链之于都是渐进无偏的。因此，为了从任意的复合分布p(s）中采样，都可以通过设计合适的转移概率aij构造一个马尔可夫链，使它的稳态分布为。

3种其他有趣且有用的马尔可夫链的性质也容易被得到。首先，马尔可夫链的状态时长是一个指数或者几何级分布：pi(d)=C(aii)d−1，其中归一化常数为C=1−aii。其次，平均状态时长为

最后，对任意一个服从马尔可夫链的观察序列，若它对应有限长度状态序列，则其概率很容易计算，是所有马尔可夫链的转移概率的乘积：

其中，是当t=1时的初始状态输出概率。