马尔可夫链

持续更新中。。。

1. 简介

1.1 定义

我们一般这样描述马尔可夫过程（也叫马尔可夫链）：假设有一系列状态集合 $S=\{s_1,s_2,\ldots,s_r\}$ ，马尔可夫过程（Markov process）是从这些状态中的某一个开始，从一种状态连续移动到另一种状态。每一次移动被称为一步（step）。如果当前位于状态 $s_i$ ，下一步移动到其他任一状态 $s_j$ 的概率为 $p_{i,j}$ ，并且这个概率只取决于当前位于哪一个状态，与曾经的状态无关。

从状态 $s_i$ 移动到 $s_j$ 的概率 $p_{i,j}$ 被称为转移概率（transition probabilities），其中 $p_{i,i}$ 是一种特殊的转移，表现形式为留在原状态不动。

1.2 转移矩阵

由于从状态 $s_i$ 移动到 $s_j$ 的转移概率为 $p_{i,j}$ ，假设我们的状态集合大小为 $r$ ，那么所有转移概率 $p_{i,j}$ 可以视作一个大小恰好为 $r\times r$ 的矩阵，这个矩阵被称为马尔可夫链的转移矩阵（Transition Matrix），同时也被称为马尔可夫链的随机矩阵（Stochastic matrix），可以参考 wiki。

不难发现这是一个相当特殊的矩阵，它的每一行元素之和均为 $1$。

定理 1：令 $\textbf {P}$ 为一马尔可夫链的转移矩阵， $\textbf {P}^n$ 的第 $i,j$ 项 $p_{i,j}^{(n)}$ 表示 $n$ 步状态转移后，从 $s_i$ 移动到 $s_j$ 的概率。

定理 2：令 $\textbf {u}$ 表示初始状态概率分布的行向量（$u_i$ 表示初始状态为 $s_i$ 的概率，显然有 $\sum_{i=1}^ru_i=1$ ），则 $\textbf {u}^{(n)}=\textbf {u}\textbf {P}^n$（$\textbf {u}^{(n)}$ 表示 $n$ 步转移之后的概率分布行向量）。

2. 吸收型马尔可夫链

2.1 定义

首先给出吸收态（absorbing）的定义：当进入状态 $i$ 后再也无法离开这个状态时，状态 $s_i$ 被称为是一个吸收态（即 $p_{i,i}=1$ ）。至少带有一个吸收态，且每个状态都有可能进入吸收态的马尔可夫过程被称为吸收型马尔可夫链（Absorbing Markov Chains）。

同时，我们定义吸收型马尔可夫链的非吸收态为瞬态（transient）。

2.2 规范型转移矩阵

对于一个吸收型马尔可夫链的转移矩阵而言，由于状态集合可以划分为瞬态集合和吸收态集合，因此我们不妨重新规划一下转移矩阵，让所有瞬态位于左侧，吸收态位于右侧，即 $S=\{s_1,s_2,\ldots,s_k,s^{\prime}_{k+1},\ldots, a^{\prime}_r\}$ ，其中 $s_i$ 表示瞬态，$s^{\prime}_j$ 表示吸收态，假设瞬态集合大小为 $k$ 。此时，转移矩阵就可以写成：

这里，$\textbf {I}$ 是一个单位矩阵，$\textbf {0}$ 是一个零矩阵，$\textbf {Q}$ 是一个 $k\times k$ 的非零矩阵，$\textbf {R}$ 是一个 $k\times (r-k)$ 的非零矩阵。这个转移矩阵被称为规范型转移矩阵，简称规范矩阵（Canonical Matrix）。

定理 3：吸收型马尔可夫链中，最终到达吸收态的概率为 $1$ ，即 $\lim_{n \rightarrow \infty} \textbf {Q}^n = \textbf {0}$ 。

证明：

2.3 基本矩阵

定理 4：对于一个吸收型马尔可夫链，如果矩阵 $\textbf {I}-\textbf {Q}$ 存在一个逆矩阵 $\textbf {N}$ ，那么矩阵 $\textbf {N}$ 的第 $i,j$ 项 $n_{i,j}$ 就是从 $s_i$ 出发移动到 $s_j$ 的期望次数（被吸收前）。

证明：令 $(\textbf {I}-\textbf {Q})\textbf {x}=\textbf {0}$ ，则有 $\textbf {x}=\textbf {Q}\textbf {x}$ 。然后我们迭代 $\textbf {Q}$ 得到 $\textbf {x}=\textbf {Q}^n\textbf {x}$ ，由于 $\textbf {Q}^n\rightarrow \textbf {0}$ ，因此 $\textbf {x}=\textbf {0}$ 。这意味着 $(\textbf {I}-\textbf {Q})^{-1}=\textbf {N}$ 存在。然后注意到：

$$(\textbf{I}-\textbf{Q})(\textbf{I}+\textbf{Q}+\textbf{Q}^2+\cdots+\textbf{Q}^n)=\textbf{I}-\textbf{Q}^{n+1}$$

两边同乘 $\textbf {N}$ 得到：

$$\textbf{I}+\textbf{Q}+\textbf{Q}^2+\cdots+\textbf{Q}^n=\textbf{N}(\textbf{I}-\textbf{Q}^{n+1})$$

由于 $\textbf {Q}^{n+1}\rightarrow 0$ ，因此 $\textbf {N}=\textbf {I}+\textbf {Q}+\textbf {Q}^2+\cdots+\textbf {Q}^n$ 。根据期望的线性性质以及定理 1，本命题得证。

注意到这个逆矩阵 $\textbf {N}$ 的性质很强，于是我们称之为基本矩阵（Fundamental Matrix）。

2.4 吸收时间

定理 5：令 $\textbf {t}$ 为一个 $1\times r$ 的行向量，其中 $t_i$ 表示从状态 $s_i$ 出发被吸收的期望步数，那么有：

$$\textbf {t}=\textbf {Nc}$$

其中 $\textbf {c}$ 是一个 $r\times 1$ 的全 $1$ 列向量。

证明：其实这个定理的正确性是比较明显的，上式相当于将矩阵 $\textbf {N}$ 中的每一行累加了起来，由于基本矩阵 $\textbf {N}$ 中第 $i$ 行的和表示从 $s_i$ 出发到达任意瞬态的期望步数，换而言之也就是从 $s_i$ 出发被吸收前的期望步数。

2.5 吸收概率

定理 6：令 $b_{i,j}$ 表示从瞬态 $s_i$ 出发在 $s_j$ 被吸收的概率，那么 $\textbf {B}$ 是一个 $k\times r$ 的矩阵，且有：

$$\textbf{B}=\textbf{NR}$$

其中，$\textbf {R}$ 就是标准型转移矩阵中的 $\textbf {R}$ 。

证明：