马尔可夫链

马尔可夫链的相关总结。马尔可夫链通常用于刻画满足马尔可夫性的随机过程，马尔可夫性指的是一个过程未来的状态仅仅与当前的状态有关，而不依赖于历史的状态。马尔可夫链通常可以根据转移概率矩阵$P_{ij}$ 描述。

State Definiction in Markov Chain

介绍马尔可夫链中状态的分类。

• 吸收态， $P_{ii} = 1$
• 可达，$\exists n, P_{ij}^{(n)} > 0 $ ，记为$i \rightarrow j$
• 不可达，$\forall n, P_{ij}^{(n)} =0$
• 互通, 两个状态相互可达，$i \leftrightarrow j$
• 闭集，$C: \forall i \in C, \forall j \notin C$, $i,j$不可达。
• 不可约，$\forall i,j , i \leftrightarrow j$, 不可约的马尔可夫链不可能有闭集
• 周期，$d(i)= \text{gcd}( P_{ii}^{(n)}>0 , n \ge 1)$
• 非周期，$d(i) =1$

其中，互通关系是一个等价类，因此在马尔可夫链中，在一个互通的类中只需要确定一个状态的性质，通常可以确定其他状态的性质。

例如，互通的状态具有相同的周期，下面证明： \(i \leftrightarrow j \Rightarrow d(i) = d(j)\) 只需要证明，$d(i) \vert d(j) = 0$，根据对称性则有，$d(j) \vert d(i)$ 。 因此，$d(i) = d(j)$.

根据互通性，$\exists n,m, P_{ij}^{(n)}>0,P_{ji}^{(m)}>0$。

因此，$P_{ii}^{(n+m)} \ge P_{ij}^{(n)} P_{ji}^{(m)}>0$.

根据周期性，$P_{jj}^{(s)} > 0 $, 则$P_{ii}^{(n+m+s)} \ge P_{ij}^{(n)} P_{jj}^{(s)} P_{ji}^{(m)} > 0$

因此，$(n+m),(n+m+s)$均为状态$i$的周期, 则$s$也为状态$i$的周期。

这样就证明了，$d(j) \vert d(i)$。

综上，$d(i) = d(j)$.

Transient and Recurrent

瞬时态和常返态是马克可夫链中状态的重要性质。定义$f_{ij}^{(n)}$表示$n$步首达概率。

若一个状态以概率1回到该状态，称为常返态，反之则为瞬时态，定义如下：

• 常返态，$\sum_{n=1}^{\infty} f_{ii}^{(n)} =1$
• 瞬时态，$\sum_{n=1}^{\infty} f_{ii}^{(n)} < 1$

但$f_{ij}^{(n)}$作为首达概率，很多情况其刻画不如转移$P_{ij}^{(n)}$直观，下面试图建立其联系。

对于状态$i$,定义示性函数$I_n$表示第$n$步之后是否回到了状态$i$。

定义 $K$表示回到状态$i$的次数，$K = \sum_{n=1}^{\infty} I_n$。

根据示性函数和概率的关系，$E[K] = E[\sum_{n=1}^{\infty} I_n] = \sum_{n=1}^{\infty} P_{ii}^{(n)}$。

另一方面，$K$ 服从参数为 $\sum_{n=1}^{\infty} f_{ii}^{(n)}$ 的几何分布。

根据几何分布的期望公式并做简单分析后，可以给出对于常返态和瞬时态的等价定义：

• 常返态，$\sum_{n=1}^{\infty} P_{ii}^{(n)} = \infty$
• 瞬时态，$\sum_{n=1}^{\infty} P_{ii}^{(n)} < \infty$

同时可以证明，对于互通关系，也具有相同的常返性。

根据互通关系，$ i \leftrightarrow j: \exists n,m, P_{ij}^{(n)}>0, P_{ji}^{(m)}>0$

若已知$i$为常返态，$\sum_{s=1}^{\infty} P_{ii}^{(s)} = \infty$.

则，$\sum_{s=1}^{\infty} P_{jj}^{(s)} \ge P_{ij}^{(n)} P_{ji}^{(m)}\sum_{s=1}^{\infty} P_{ii}^{(s)} = \infty$.

故，$j$也为常返态。

在常返态的基础上，可以定义零常返和正常返态。

对于$f_{ii}^{(n)}$所表示的$n$步首达的随机事件，定义其期望为平均首达步数 $\mu_i = E[f_{ii}^{(n)}]$

• 正常返，$\mu_i < \infty$
• 零常返，$\mu_i = \infty$

零常返状态只在可列无穷个状态的情况下出现。

Limitation

本节研究马尔可夫链的极限分布和平稳分布。

首先看极限定理，给出了转移矩阵的极限：

• $\lim P_{ii}^{(n)} = 0$ , 若$i$为瞬时态或者零常返态
• $\lim P_{ii}^{(n)} = \frac{1}{\mu_i}$ , 若$i$为非周期的正常返态
• $\lim P_{ii}^{(nd)} = \frac{d}{\mu_i}$ , 若$i$为周期为$d$的正常返态

对$i$为非周期的正常返态的情况进行证明：

定义$P_i(t),F_i(t)$为$P_{ii}^{(n)},f_{ii}^{(n)}$对应的特征函数。

根据定义，$P_{ii}^{(n)} = \sum_{k=1}^n f_{ii}^{(k)} P_{ii}^{(n-k)}$, 同时根据傅里叶变换的卷积定理，$P_i(t) = 1 + P_i(t) F_i(t)$

因此，$(1-e^t) P_i(t) = \frac{1-e^t}{F_i(t)}$, 令左右两端令$t \rightarrow 0$

$\lim (1-e^t) P_i(t) = \lim \frac{\sum_{n=0}^{\infty} P_{ii}^{(n)} e^{tn}}{\sum_{n=0}^{\infty} e^{tn}} = \lim \frac{\sum_{n=0}^{k} P_{ii}^{(n)}}{k} = P_{ii}^{(n)}$

根据洛必达法则，$\frac{1-e^t}{F_i(t)} = \frac{1}{E[f_{ii}^{(n)}]} = \frac{1}{\mu_i}$

因此，我们对$i$为非周期的正常返态的情况进行了证明。

对于其他两种情况的证明也是类似的，但需要用到一些矩阵极限的知识稍加变动，此处暂略。

Stationary

本节探究马尔可夫链的平稳性。

马尔可夫链的平稳性，本质上是随机过程的强平稳（严平稳），也即分布的时间平移不变性。 \(\forall t_1,t_2,...,t_n, \forall t_0, (t_1,t_2,..t_n) \sim (t_1+t_0, t_2+t_0,...,t_n+t+0)\) 可以简单证明，在马尔可夫链中，当且仅当初始概率$p_0$ 和转移矩阵$P$，满足$p_0 = p_0 P$

据此，定义概率分布$\pi$为马尔可夫链的平稳分布，$\pi = \pi P$.

平稳分布，在很多时候给出了另一种求极限分布的方法。

对于一个不可约的非周期正常返的马尔可夫链，其平稳分布等价于极限分布。

证明细节暂略，直观上来说，根据随机矩阵理论，此时转移矩阵的极限矩阵趋近于秩一矩阵，$\lim_{n \rightarrow \infty} P_{ij}^{(n)} = \mu_j = \pi_j$

这其实是个Perron投影，随机矩阵必有右特征向量$P e = e$, 且有左特征向量$\pi^T P = \pi^T$, 则 $\lim_{n \rightarrow \infty} P = \pi e^T$

Reversible Markov Chain

本节探究可逆的马尔可夫链。

可逆的马尔可夫链，首先前提是平稳不可约的马尔可夫链，其从逆向时间转移和正向时间转移具有相同的分布，也即: \(\forall t_1,t_2,...,t_n, \forall m \ge n, (t_1,t_2,..t_n) \sim (t_{m-1}, t_{m-2},...,t_{m-n})\) 同时，可以证明，一个马尔可夫链为可逆马尔可夫链的充要条件为其满足细致平稳条件， \(\mu_i P_{ij} = \mu_j P_{ji}\) 在蒙特卡罗采样方法中，由于细致平稳条件是平稳条件的充分条件，因此马尔可夫链-蒙特卡罗方法通常基于细致平稳条件构造转移矩阵，从而达到采样的目的，感兴趣的读者可以详见 马尔可夫链-蒙特卡罗方法