马尔科夫链

Please refresh the page if equations are not rendered correctly.
---------------------------------------------------------------

一、基本概念

1、随机过程（stochastic process)

考虑一个随机变量的序列 $X=\begin{Bmatrix}X_0,X_1,\ldots,X_t,\ldots\end{Bmatrix},t=0,1,2,\ldots$
这里 $X_{t}$ 表示时刻 $t$ 的随机变量，每个随机变量 $X_{t}$ 的取值集合相同，称为状态空间，表示为 $S$ 。随机变量可以是离散的，也可以是连续的。以上随机变量的序列构成随机过程。

（1）状态空间：所有随机变量都定义在相同的概率空间上，设 $X=\begin{Bmatrix}X_0,X_1,\ldots,X_t,\ldots\end{Bmatrix},t=0,1,2,\ldots$ 如果每个 $X_{t}$ 都在 $S$ 中取值，则称 $S$ 为状态空间，称 $S$ 中的元素为状态；

（2）状态：当 $S$ 中只有有限个或可列个状态时，可以将 $S$ 中的状态进行编号，得到由整数构成的集合 $I$ ， $I$ 是 ${X_{t}}$ 的状态空间，用 $i,j,k,i_{0},i_{1},\ldots$ 来表示 $I$ 中的状态。

2、马尔科夫链（Markov chain)

马尔科夫链定义本身比较简单，它假设某一时刻状态转移的概率只依赖于它的前一个状态。

假设在时刻 $X_{0}$ 的随机变量遵循概率分布 $P(X_{0})=\pi_{0}$ ，称为初始状态分布。在某个时刻 $t\geq1$ 的随机变量 $X_{t}$ 与前一个时刻的随机变量 $X_{t-1}$ 之间有条件分布 $P(X_{t}|X_{t-1})$ ，如果 $X_{t}$ 只依赖于 $X_{t-1}$ ，而不依赖于过去的随机变量 $\begin{Bmatrix}X_0,X_1,\ldots,X_{t-1},\ldots\end{Bmatrix}$ ，这一性质称为马尔可夫性，即：

$P(X_t|X_{t-1},X_{t-2},\ldots,X_0)=P(X_t|X_{t-1}),t=1,2,\ldots$

具有马尔可夫性的随机序列 $X=\begin{Bmatrix}X_0,X_1,\ldots,X_t,\ldots\end{Bmatrix}$ 称为马尔可夫链，或马尔可夫过程（Markov process)。条件概率分布 $P(X_{t}|X_{t-1})$ 称为马尔科夫链的转移概率分布。转移概率分布决定了马尔科夫链的特性。

加入状态也就是下式：

$P(X_{t+1}=j|X_{t}=i,X_{t-1}=i_{t-1},\ldots,X_{0}=i_{0})=P(X_{t+1}=j|X_{t}=i)$

就是说 $X_{t}$ 时的状态，只与 $X_{t-1}$ 有关，而与之前的状态没有关系。

若转移概率分布 $P(X_{t}|X_{t-1})$ 与 $t$ 无关，即

$P(X_{t+1}=j|X_t=i)=P(X_1=j|X_0=i),i,j\in I$

也就是与具体在某个时刻是没有关系的，只和间隔的转移次数有关，那么就称该马尔科夫链为为时间齐次的马尔科夫链。

二、离散状态马尔科夫链（Discrete-time Markov chains)

1、转移概率矩阵（matrix of transition probability)

离散状态马尔科夫链 $X=\begin{Bmatrix}X_0,X_1,\ldots,X_t,\ldots\end{Bmatrix}$ ，随机变量 $X_{t}(t=0,1,2,\ldots)$ 定义在离散空间S，转移概率分布可以由矩阵表示。

转移概率可记作

$P_{ij}= P(X_{t+1}=j|X_{t}=i)$

满足

$P_{i,j}\geq0,\sum_{i}P_{i,j}=1$

马尔科夫链的转移概率可以由矩阵表示，即

$P=\left[\begin{matrix}P_{11}&P_{12}&P_{13}&\cdots\\\ P_{21}&P_{32}&P_{23}&\cdots\\\ P_{31}&P_{32}&P_{33}&\cdots\\\ \cdots&\cdots&\cdots&\cdots\end{matrix}\right]$

成为马尔科夫的概率转移矩阵，矩阵列元素之和为1。

2、柯尔莫哥洛夫—切普曼方程（K—C方程）

对于任意的m，n≥，有：

$P_{i j}^{(m+n)}=\sum_{k\in I}P_{i k}^{n}P_{k j}^{m}$

也就是

$P^{(n+m)}=P^{n+m}$

其内涵是n+m步转移矩阵就等于一步转移矩阵的n+m次方。

所以，

$P^{(m)}=P\times P\times\cdots\times P=P^{m}$

3、状态分布（state distribution)

转移概率（transition probability)

$P(X_{t+1}=j|X_{t}=i)=P_{i j}(t)$

表示 $t$ 时刻由状态 $i$ 到状态 $j$ 的过程。

静止概率（rest probability)

$\pi_{i}(t)=P(X_{t}=i)$

表示 $t$ 时刻是状态 $i$ 的概率。

马尔科夫过程（Markov process)

$\pi(t)=A\pi(t-1)，A=P^T$

$P(t)=A P(t-1)$

马尔科夫链在 $t$ 时刻的概率分布称为 $t$ 时刻的状态分布：

$\pi(t)=\begin{bmatrix} \pi_1(t)\\\ \pi_2(t)\\\ \pi_3(t)\\\ \cdots\end{bmatrix}$

特别地，马尔可夫链的初始状态分布可以表示为：

$\pi(0)=\begin{bmatrix} \pi_1(0)\\\ \pi_2(0)\\\ \pi_3(0)\\\ \cdots\end{bmatrix}$

通常初始分布 $\pi(0)$ 向量只有一个分量是1，其余分量都是0（因为一个时刻只能有一种状态)，表示马尔可夫链从一个具体状态开始。

马尔科夫链在时刻 $t$ 的状态分布，可以由在时刻 $t-1$ 的状态分布以及转移概率矩阵决定

$\pi(t)=P\pi(t-1)$

因为

$\begin{matrix}\pi_{i}(t)=P(X_{t}=i)\\ = \ \sum_{m}P(X_{t}=i|X_{t-1}=m)P(X_{t-1}=m) \\ =\sum_{m}P_{i m}\pi_{m}(t-1)\end{matrix}$

4、平稳分布(stationary distribution)

若

$\lim_{n\rightarrow\infty}\pi_{n}=\pi$

使得

$\pi=P\pi$

则称 $π$ 为马尔科夫链 $X={X_{0},X_{1},\ldots,X_{t},\ldots}，$ 的平稳分布。

$\pi=P\pi=\ldots=P^{(n)}\pi=P^{n}\pi$

马尔科夫链模型的状态转移矩阵收敛到的稳定概率分布（平稳分布 $π$ ）与我们的初始状态概率分布无关。也就是说，如果我们得到了这个稳定概率分布对应的马尔科夫链模型的状态转移矩阵，则我们可以用任意的概率分布样本开始，带入马尔科夫链模型的状态转移矩阵，这样经过一些序列的转换，最终就可以得到符合对应稳定概率分布的样本。

平稳分布时， $π$ 是 $A$ 特征值为1的特征向量。

当 $A$ 多次迭代作用即重复

$P(t)=A P(t-1)$

得到的分布向量逐渐地接近与A的最大特征值相关的A的特征向量。（任何初始向量分布都可以写成A的特征向量的线性组合。设A的特征向量和相应的特征值分别为 $\boldsymbol{x}_1,\ldots,\boldsymbol{x}_n$ 和 $\lambda_1,\ldots,\lambda_n$ ，显然有

$P(k)=A^{k}P(0)=\sum_{i=1}^{t}c_{i}\lambda_{i}^{k}x_{i}$

当 $A$ 乘以初始向量，线性组合中第K个特征向量的系数乘以相应的特征值，如果重复 $t$ 次，则每个系数相乘的因子为 $\lambda_{i}^{k}$ 。如果 $t$ 较大，则特征值最大的项占主导地位）。

由于 $A$ 的每一列和都为1，所以考虑用 $A-E$ ，显然有：

$|A-E|=0$

$A-E$ 相当于 $A$ 的每一列和都减去1，因此 $A-E$ 的每一列和都为0。

首先将 $A$ 做特征值分解。 $\Lambda$ 为对角矩阵，对角线上元素为 $A$ 的特征值，X为对应特征值的特征向量矩阵。

$A=X\Lambda X^{-1}$

$\begin{aligned} |A-E|& =|X\Lambda X^{-1}-E| \\ &=|X\Lambda X^{-1}-XEX^{-1}| \\ &=|X(\Lambda-E)X^{-1}| \\ &=\prod\limits_{i=1}^{n}(\lambda_i-1) \end{aligned}$

于是有

$\prod_{i=1}^n\left(\lambda_i-1\right)=0$

所以一定存在特征值为1的情况。且A的列和为1，所以

$|\lambda_{i}| \leq1$

即A的最大特征值为1。

5、马尔科夫链的收敛性质

如果一个非周期的马尔科夫有状态转移矩阵 $P$ ，并且他的任何两个状态是连通的（不可约），那么 $\lim\limits_{n\to\infty}P^n_{ij}$ 与 $i$ 无关，有：

$\text{1.}\lim\limits_{n\to\infty}P^n_{ij}=\pi(j)$

$2.\underset{n\to\infty}{\text{lim}}P^n=\begin{bmatrix}\pi(1)&\pi(2)&\cdots&\pi(j)&\cdots\\\ \pi(1)&\pi(2)&\cdots&\pi(j)&\cdots\\\ \ \vdots&\vdots&\vdots&\ddots&\vdots\\\ \ \pi(1)&\pi(2)&\cdots&\pi(j)&\cdots\\\ \ \vdots&\vdots&\vdots&\ddots&\vdots\ \end{bmatrix}.$

$3.\pi(j)=\sum_{i=0}^\infty\pi(i)P_{ij}$

4. $π$ 是方程 $\pi=P\pi$ 唯一非负解，其中，

$\pi=[\pi(1),\pi(2),\cdots,\pi(j),\cdots]，\sum_{i=1}^{\infty}\pi(i)=1$

$π$ 是马氏链的平稳分布。

三、基于马尔科夫链采样

如果我们得到了某个平稳分布所对应的马尔科夫链状态转移矩阵，我们就很容易采用出这个平稳分布的样本集。

假设我们任意初始的概率分布是 $\pi_{0}\left(x\right)$ ，经过第一轮马尔科夫链状态转移后的概率分布是 $\pi_{1}\left(x\right)$ ，...，第 i轮的概率分布是 $\pi_{i}\left(x\right)$ 。假设经过t轮后马尔科夫链收敛到我们的平稳分布 π(x) ，即

$\pi_t(x)=\pi_{t+1}(x)=\pi_{t+2}(x)=...=\pi(x)$

对于每个分布，都有

$\pi_{i}(x)=\pi_{i-1}(x)P=\pi_{i-2}(x)P^{2}=\ldots=\pi_{0}(x)P^{i}$

现在可以开始采样，首先，基于初始任意简单概率分布比如高斯分布 $\pi_{0}\left(x\right)$ 采样得到状态值 $x_{0}$ ，基于条件概率分布 $P(X|X_{0})$ 采样状态值 $x_{1}$ ，一直进行下去，当状态转移进行到一定的次数时，比如到 $t$ 次时，我们认为此时的采样集即是符合我们的平稳分布的对应样本集，可以用来做蒙特卡罗模拟求和。