马尔科夫链
马尔科夫过程是一类特殊的随机过程,在给定当前状态下,对于未来状态的预测便不再依赖于过去状态。马尔科夫链是一种应用十分广泛的马尔科夫过程,能够用于描述天气变化和基因调控等现象。本词条主要参考北京大学李东风老师的应用随机过程讲义[1]对相关基础概念进行梳理,为后续相关应用做铺垫。
基本概念
离散(或连续)时间马尔科夫链
下面介绍两种简单类型的马尔科夫过程,离散时间马尔科夫链(简称马尔科夫链,Markov chain)以及连续时间马尔科夫链。
称状态空间[math]\displaystyle{ S=\{1,2,\ldots\} }[/math]上的随机过程[math]\displaystyle{ \{X_n,\ n=0,1,2,\ldots\} }[/math]是马尔科夫链[2]或具有马尔科夫性质,若满足
[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]是连续时间马尔科夫链[3]
,若满足
[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]。
日常生活中的许多现象都可以利用马尔科夫链来描述,例如天气的变化。简单考虑两种天气状态,下雨和不下雨,分别记为状态2和状态1,即样本空间为[math]\displaystyle{ S=\{1,2\} }[/math]。那么,对应的马尔科夫假设就是明天是否下雨只取决于今天的天气,而与之前的天气无关。
令今天为时刻[math]\displaystyle{ n=0 }[/math],为了方面描述,记[math]\displaystyle{ X_n }[/math]为时刻[math]\displaystyle{ n }[/math]的天气状态,今天不下雨的条件下明天不下雨的概率为[math]\displaystyle{ P(X_1=1|X_0=1)=p }[/math],今天下雨的条件下明天下雨的概率为[math]\displaystyle{ P(X_1=2|X_0=2)=q }[/math]。而随着时间的推移,明天不下雨的条件下后天不下雨的概率[math]\displaystyle{ P(X_2=1|X_1=1) }[/math]可能不一定等于[math]\displaystyle{ p }[/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}\\ p_{21}& p_{22}\\ \end{bmatrix}=\begin{bmatrix} p& 1-p\\ 1-q& q\\ \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)。
下面用一个简单的例子来说明,下图中(a)和(b)分别为马尔科夫链的转移概率矩阵和图表示。
容易看出,状态1和状态2是互通的,可被归为一类,而状态3只可达自身,所以状态3为另一个类,即此马尔科夫链是可约的。
互通的状态之间是否有什么共同的性质?此处从状态自身的可达性出发,简单介绍一个类性质——周期。
考察状态自身的可达性,即使得转移概率[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{ P_{33}=1\gt P_{22}=0.2\gt 0 }[/math],那么[math]\displaystyle{ A_{2}=A_{3}=\{1,2,\ldots\} }[/math],所以它们都是非周期的。对于状态1,其与状态2互通且状态2一步可达自身,那么[math]\displaystyle{ A_{1}=\{2,3,\ldots\} }[/math],所以状态1也是非周期的。
进一步,可以通过严格证明得出,互通状态的周期是相同的。
证:不失一般性,假设[math]\displaystyle{ i\leftrightarrow j }[/math],则[math]\displaystyle{ \exists m,\ P_{ij}(m)\gt 0 }[/math]及[math]\displaystyle{ \exists n,\ P_{ji}(n)\gt 0 }[/math]。那么,
[math]\displaystyle{ P_{ii}(m+n)\geq P_{ij}(m)P_{ji}(n)\gt 0\Longrightarrow m+n\in A_i\Longrightarrow d_i|(m+n) }[/math]。
另一方面,任取[math]\displaystyle{ k\in A_j }[/math], [math]\displaystyle{ P_{ii}(m+n+k)\geq P_{ij}(m)P_{jj}(k)P_{ji}(n)\gt 0\Longrightarrow m+n+k\in A_i\Longrightarrow d_i|(m+n+k) }[/math]。
综上,[math]\displaystyle{ d_i\Big|[(m+n+k)-(m+n)]\Longrightarrow d_i|k }[/math], 即[math]\displaystyle{ d_i }[/math]是[math]\displaystyle{ A_j }[/math]的公因子。
由于一个集合的公因子一定整除其最大公因子,得[math]\displaystyle{ d_i|d_j }[/math]。同理,[math]\displaystyle{ d_j|d_i }[/math]。那么,[math]\displaystyle{ d_i=d_j }[/math],证毕。
上述分类方法是基于局部性质进行两两判断分类。此外,还可以从整体转移机制的角度对状态进行划分,详细介绍参见成块性(Lumpability)。
对于时齐马尔科夫链,其演化过程由初始分布以及一步转移概率矩阵刻画,下面具体考察其演化性质。
演化性质
演化过程
记[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)。
上节中的马尔科夫链如果在0时刻三个状态等概率地出现,那么在1时刻和2时刻的状态分布分别为
[math]\displaystyle{ \pi_1=(1/3,1/3,1/3)\left(\begin{matrix}0&0.9&0.1\\0.8&0.2&0\\ 0&0&1 \end{matrix}\right)=(0.2667,0.3667,0.3667),\ \ \ \ \ }[/math] [math]\displaystyle{ \pi_2=(1/3,1/3,1/3)\left(\begin{matrix}0&0.9&0.1\\0.8&0.2&0\\ 0&0&1 \end{matrix}\right)^2=(0.2933,0.3133,0.3933) }[/math]。
若将左手方程的左右两边同时进行转置,得
[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_0 }[/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_{ji}x_i }[/math]。
不失一般性,假设[math]\displaystyle{ |x_j|=\max_{k}|x_i| }[/math],有
[math]\displaystyle{ |\lambda|\cdot|x_j|=\Big|\sum_i p_{ji}x_i\Big|\leq\sum_{i}p_{ji}|x_i|\leq\sum_{i}p_{ji}|x_j|=|x_j| }[/math]。
那么,[math]\displaystyle{ |\lambda|\leq 1 }[/math]。
注:上述两条性质对于一般的随机矩阵均成立。
神奇的是,转移概率矩阵的谱性质可以一定程度上表征演化过程是否会发生涌现,详细内容参见词条基于可逆性的因果涌现理论。
细致平衡条件
前面的讨论都沿着时间正向在讨论,下面考虑时间反向的过程。
[math]\displaystyle{ P(X_n=j|X_{n+1}=i,X_{n+2},\ldots)= \frac{P(X_n=j|X_{n+1}=i)P(X_{n+2},\ldots|X_{n+1}=i,X_n=j)}{P(X_{n+2},\ldots|X_{n+1}=i)} =P(X_n=j|X_{n+1}=i) =\frac{P(X_n=j)P(X_{n+1}=i|X_n=j)}{P(X_{n+1}=i)} }[/math],
即反向过程仍满足马尔科夫性质。这其实是马尔科夫性质的等价定义——给定现在的条件下,过去与未来条件独立。并且,一般来讲,上述一步转移概率是与时间[math]\displaystyle{ n }[/math]有关的,即反向过程是非齐次的。
下面考察有限状态空间上不可约、非周期的马尔科夫链,其唯一的平稳分布为[math]\displaystyle{ \pi }[/math]。从平稳分布出发,有
[math]\displaystyle{ P(X_n=j|X_{n+1}=i,X_{n+2},\ldots) =\frac{P(X_n=j)P(X_{n+1}=i|X_n=j)}{P(X_{n+1}=i)}=\frac{\pi_jp_{ji}}{\pi_i}\triangleq q_{ij} }[/math]。
此时,反向过程是齐次的。
进一步,考虑一种特殊情形,若[math]\displaystyle{ q_{ij}=p_{ij} }[/math],即对于任意的状态[math]\displaystyle{ i,j }[/math],满足[math]\displaystyle{ \pi_i p_{ij}=\pi_jp_{ji} }[/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]之间的相互输送是相同的。
进一步,若满足细致平衡条件,则
[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]。
- ↑ 李东风. 应用随机过程, 2024, 163-215. https://www.math.pku.edu.cn/teachers/lidf/course/stochproc/stochprocnotes/html/_book/StocProc.pdf
- ↑ Brémaud P.Markov chains: Gibbs fields, Monte Carlo simulation, and queues.Springer Science & Business Media, 1999, 53-156.
- ↑ Kendall D G, Batchelor G K, Bingham N H, Hayman W K, Hyland J M E, Lorentz G G, Moffatt H K, Parry W, Razborov A A, Robinson C A and Whittle P. Andrei Nikolaevich Kolmogorov (1903–1987). Bulletin of the London Mathematical Society, 1990, 22(1): 31-100.