马尔科夫链

基本概念

离散（或连续）时间马尔科夫链

马尔科夫过程是一类特殊的随机过程，在给定当前状态下，对于未来状态的预测便不再依赖于过去状态。下面介绍两种简单类型的马尔科夫过程，离散时间马尔科夫链（简称马尔科夫链，Markov chain）以及连续时间马尔科夫链。

称状态空间[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{ S=\{1,2,\ldots\} }[/math]上的随机过程[math]\displaystyle{ \{X_t,\ t\geq 0\} }[/math]是连续时间马尔科夫链，若满足 [math]\displaystyle{ \forall n,\ 0\leq t_0\lt t_1\lt \ldots\lt t_{n-1}\lt t_{n},\ \ P(X_{t_n}=j|X_{t_{n-1}}=i,X_{t_{n-2}}=x_{t_{n-2}},\ldots,X_{t_{0}}=x_{t_{0}})=P(X_{t_n}=j|X_{t_{n-1}}=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}(i,j\in S) }[/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{ \exists n\geq 0,\ \ P_{ij}(n)\gt 0 }[/math]，则称状态[math]\displaystyle{ i }[/math]可达状态[math]\displaystyle{ j }[/math]，记为[math]\displaystyle{ i\to j }[/math]。易知，可达是传递关系，即 [math]\displaystyle{ i\to j,\ j\to k\Longrightarrow i\to k }[/math]。

进一步，若[math]\displaystyle{ i\to j }[/math]且[math]\displaystyle{ j\to i }[/math]，则称状态[math]\displaystyle{ i }[/math]和[math]\displaystyle{ j }[/math]互通，记为[math]\displaystyle{ i\leftrightarrow j }[/math]。易知，互通是一种等价关系。那么，可以将互通的状态归为一类，且任一状态仅属于一个类。

特别的，若马尔科夫链中只存在一个类，则称它是不可约的（irreducible）；否则，称为是可约的（reducible）。

此外，考察状态自身的可达性，即使得转移概率[math]\displaystyle{ P_{ii}(n)\gt 0 }[/math]的转移步数[math]\displaystyle{ n }[/math]所组成的集合，记为[math]\displaystyle{ A_i=\{n:n\geq1,P_{ii}(n)\gt 0\} }[/math]。若[math]\displaystyle{ A_i }[/math]非空，则称其最大公约数为状态[math]\displaystyle{ i }[/math]的周期，记为[math]\displaystyle{ d_i }[/math]。若[math]\displaystyle{ d_i\gt 1 }[/math]，称[math]\displaystyle{ i }[/math]是周期的；若[math]\displaystyle{ d_i=1 }[/math]，称[math]\displaystyle{ i }[/math]是非周期的。通过证明可得，互通状态的周期是相同的。

对于时齐马尔科夫链，其演化过程由初始分布以及一步转移概率矩阵刻画，下面具体考察其演化性质。

演化性质

演化过程

若给定[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{ P }[/math]的特征值，由于[math]\displaystyle{ P }[/math]的行和为[math]\displaystyle{ 1 }[/math]，那么

[math]\displaystyle{ P\mathbf{1}=\begin{bmatrix} p_{11}& p_{12}&\ldots\\ p_{21}& p_{22}&\ldots\\ \vdots& \vdots&\ddots\\ \end{bmatrix}\begin{bmatrix} 1 \\ 1\\ \vdots\\ \end{bmatrix}=\begin{bmatrix} \sum_{j\in S}{p_{1j}}\\ \sum_{j\in S}{p_{2j}}\\ \vdots\\ \end{bmatrix}=\begin{bmatrix} 1 \\ 1\\ \vdots\\ \end{bmatrix}=\mathbf{1}. }[/math]

即[math]\displaystyle{ 1 }[/math]是[math]\displaystyle{ P }[/math]的特征值，且对应的特征向量为[math]\displaystyle{ \mathbf{1} }[/math]。另一方面，

[math]\displaystyle{ det(P-\lambda I)=det((P-\lambda I)^{\rm T})=det(P^{\rm T}-\lambda I). }[/math]

所以，[math]\displaystyle{ 1 }[/math]也是[math]\displaystyle{ P^{\rm T} }[/math]的特征值。

注：即方程[math]\displaystyle{ \pi=\pi P }[/math]总有非零解，这与马尔科夫链是否有极限没有关系。

若[math]\displaystyle{ \pi_0 }[/math]是方程[math]\displaystyle{ \pi=\pi P }[/math]的解，那么由递推关系得

[math]\displaystyle{ \pi_n=\pi_0P^n=\pi P^n=\pi. }[/math]

即若[math]\displaystyle{ P(X_0=i)=\pi_0(i) }[/math]，有

[math]\displaystyle{ \forall\ n,\ P(X_n=i)=\pi_0(i) }[/math]，

即[math]\displaystyle{ \pi_0 }[/math]为平稳分布。

进一步，设[math]\displaystyle{ \lambda }[/math]为[math]\displaystyle{ P }[/math]的任一特征值，对应的特征向量为[math]\displaystyle{ x=(x_1,x_2,\ldots)^{\rm T} }[/math]。那么，[math]\displaystyle{ \lambda }[/math]也是[math]\displaystyle{ P^{\rm T} }[/math]的特征值，且[math]\displaystyle{ \lambda x^{\rm T}=x^{\rm T}P^{\rm T} }[/math]，展开得

[math]\displaystyle{ \lambda x_j=\sum_{i}p_{ij}x_i. }[/math]

不失一般性，假设[math]\displaystyle{ |x_j|=\max_{k}|x_i| }[/math]，有

[math]\displaystyle{ |\lambda|\cdot|x_j|=\Big|\sum_i p_{ij}x_i\Big|\leq\sum_{i}p_{ij}|x_i|\leq\sum_{i}p_{ij}|x_j|=|x_j|. }[/math]

那么，[math]\displaystyle{ |\lambda|\leq 1 }[/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]之间的相互输送是相同的，