马尔科夫链

基本概念

离散时间离散状态随机过程

称状态空间[math]\displaystyle{ S=\{1,2,\ldots\} }[/math]上的随机过程[math]\displaystyle{ \{X_n,\ n=0,1,2,\ldots\} }[/math]是马尔可夫链或具有马尔可夫性质，若满足

[math]\displaystyle{ \forall n,\ \ P(X_n=j|X_{n-1}=i,X_{n-2}=x_{n-2},\ldots,X_1=x_1)=P(X_n=j|X_{n-1}=i), }[/math]

其中，[math]\displaystyle{ X_n=j }[/math]表示过程在时刻[math]\displaystyle{ n }[/math]处于状态[math]\displaystyle{ i }[/math]，称[math]\displaystyle{ P(X_n=j|X_{n-1}=i) }[/math]为马尔可夫链的一步转移概率，并引入记号[math]\displaystyle{ P_{ij}(m,n)=P(X_n=j|X_m=i) }[/math]。

注：马尔可夫过程是不限于离散时间或离散状态的，此处重点研究离散时间且离散状态

特别的，当一步转移概率[math]\displaystyle{ P(X_n=j|X_{n-1}=i) }[/math]只与状态[math]\displaystyle{ i,j }[/math]有关，而与时刻[math]\displaystyle{ n }[/math]无关（平稳性假设），称此马尔可夫链为时齐马尔可夫链（homogeneous）；若[math]\displaystyle{ P(X_n=j|X_{n-1}=i) }[/math]不仅与状态[math]\displaystyle{ i,j }[/math]和时刻[math]\displaystyle{ n }[/math]均有关，则称此马尔可夫链为非时齐的。下面主要讨论时齐马尔可夫链。

转移概率矩阵

由时齐性假设，记一步转移概率 [math]\displaystyle{ P(X_n=j|X_{n-1}=i)=p_{ij}, }[/math] 一般的，记[math]\displaystyle{ n-m }[/math]步转移概率 [math]\displaystyle{ P_{ij}(m,n)=P_{ij}(n-m). }[/math]

将[math]\displaystyle{ p_{ij} }[/math]排列为一个矩阵

[math]\displaystyle{ P=(p_{ij})_{i,j\in S}=\begin{bmatrix} p_{11}& p_{12}&\ldots\\ p_{21}& p_{22}&\ldots\\ \vdots& \vdots&\ddots\\ \end{bmatrix} }[/math]

称[math]\displaystyle{ P }[/math]为一步转移概率矩阵（transition probability matrix, TPM）。

通过观察可知，矩阵[math]\displaystyle{ P }[/math]满足如下性质

[math]\displaystyle{ \begin{aligned} p_{ij}&\geq0,\ \forall\ i,j\in S,\\ \sum_{j\in S}p_{ij}&=1,\ \forall\ i\in S. \end{aligned} }[/math]

一般的，称满足上述性质的矩阵为随机矩阵（stochastic matrix）。

演化过程

若给定[math]\displaystyle{ X_n(n\geq0) }[/math]的分布列

[math]\displaystyle{ \pi_n=(\pi_n(1),\pi_n(2),\ldots), }[/math]

其中，[math]\displaystyle{ \pi_n(i)=P(X_n=i),\ i\in S }[/math]。

根据全概率公式，[math]\displaystyle{ X_{n+1} }[/math]的分布列为

[math]\displaystyle{ \pi_{n+1}=\pi_{n}P. }[/math]

进一步，递推可得，

[math]\displaystyle{ \forall\ n\geq0,\ \ \pi_n=\pi_0P^n. }[/math]

注：[math]\displaystyle{ \pi }[/math]是一个行向量，上述方程为左手方程（left hand equation）。

若将等式左右两边同时进行转置，得

[math]\displaystyle{ \pi_{n}^{\rm T}=(P^{\rm T})^n\pi_{0}^{\rm T}. }[/math]

这是一个一阶线性齐次常微分方程。由递推关系，自然地会联想到，这个系统的长期行为本质上是一个特征值问题。

细致平衡条件

[math]\displaystyle{ \pi_i P_{ij}=\pi_jP_{ji}, }[/math] 则

[math]\displaystyle{ \pi_i=\sum_k\pi_kP_{ki}\iff \pi=\pi P. }[/math]

证：[math]\displaystyle{ \pi_i=\pi_i\sum_kP_{ik}=\sum_k\pi_iP_{ik}=\sum_k\pi_kP_{ki}. }[/math]

注：[math]\displaystyle{ \pi_i P_{ij} }[/math]可以理解为状态[math]\displaystyle{ i }[/math]向状态[math]\displaystyle{ j }[/math]的输送，同理，[math]\displaystyle{ \pi_jP_{ji} }[/math]可以理解为状态[math]\displaystyle{ j }[/math]向状态[math]\displaystyle{ i }[/math]的输送，那么细致平衡表示状态[math]\displaystyle{ i }[/math]与状态[math]\displaystyle{ j }[/math]之间的相互输送是相同的，