线性代数 Cheat Sheet 4-9：马尔可夫链中的应用

Author: nex3z 2018-12-02

　　马尔可夫链习惯上用来描述用用一种方法进行多次实验或测量，实验中每次测试的结果属于几个指定的可能结果之一，每次测试结果仅依赖于最近的前一次测试。

　　一个具有非负元素且各元素的数值相加等于 $1$ 的向量称为概率向量。随机矩阵是各列向量均为概率向量的方阵。马尔可夫链是一个概率向量序列 $\boldsymbol x_0, \boldsymbol x_1, \boldsymbol x_2, \cdots$ 和一个随机矩阵 $P$，满足

$$\begin{equation} \boldsymbol x_1 = P \boldsymbol x_0, \; \boldsymbol x_2 = P \boldsymbol x_1, \; \boldsymbol x_3 = P \boldsymbol x_2, \cdots \end{equation}$$

于是马尔可夫链可用一阶差分方程来刻画：

$$\begin{equation} \boldsymbol x_{k+1} = P \boldsymbol x_k, \; k = 0, 1, 2, \cdots \end{equation}$$

　　当向量在 $\mathbb{R}^n$ 中的一个马尔可夫链描述一个系统或实验的序列时，$\boldsymbol x_k$ 中的元素分别列出系统在 $n$ 个可能状态中的概率，或实验结果是 $n$ 个可能结果之一的概率。因此，$\boldsymbol x_k$ 通常称为状态向量。

1. 稳态向量

　　若 $P$ 是一个随机矩阵，则相对于 $P$ 的稳态向量（或平衡向量）是一个满足

$$\begin{equation} P \boldsymbol q = \boldsymbol q \end{equation}$$

的概率向量 $\boldsymbol q$。可以证明每一个随机矩阵有一个稳态向量。

　　可以通过解方程 $P \boldsymbol x = P$ 来寻找随机矩阵 $P$ 的稳态向量。例如令 $P = \begin{bmatrix} 0.6 & 0.3 \\ 0.4 & 0.7\end{bmatrix}$，解方程 $P \boldsymbol x = P$：

$$\begin{equation} P \boldsymbol x – \boldsymbol x = \boldsymbol 0 \\ (P – I) \boldsymbol x = \boldsymbol 0 \end{equation}$$

由

$$\begin{equation} P – I = \begin{bmatrix} 0.6 & 0.3 \\ 0.4 & 0.7\end{bmatrix} – \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix} = \begin{bmatrix} -0.4 & 0.3 \\ 0.4 & -0.3\end{bmatrix} \end{equation}$$

化简增广矩阵

$$\begin{equation} \begin{bmatrix} -0.4 & 0.3 & 0 \\ 0.4 & -0.3 & 0\end{bmatrix} \sim \begin{bmatrix} 1 & -3/4 & 0 \\ 0 & 0 & 0\end{bmatrix} \end{equation}$$

得到通解为 $x_2 \begin{bmatrix}3/4 \\ 1\end{bmatrix}$。对此解空间选一个简单的基 $\boldsymbol w = \begin{bmatrix} 3 \\ 4\end{bmatrix}$，将 $\boldsymbol w$ 除以其元素之和，得到概率向量 $\boldsymbol q = \begin{bmatrix} 3/7 \\ 4/7\end{bmatrix}$。检验之，计算

$$\begin{equation} P \boldsymbol q = \begin{bmatrix} 0.6 & 0.3 \\ 0.4 & 0.7\end{bmatrix} \begin{bmatrix} 3/7 \\ 4/7\end{bmatrix} = \begin{bmatrix} 30/70 \\ 40/70\end{bmatrix} = \boldsymbol q \end{equation}$$

　　如果一个随机矩阵的某次幂 $P^k$ 仅包含严格正的元素，则称这个随机矩阵是正则的。

　　对于一个向量序列 $\{\boldsymbol x_k: k = 1, 2, \cdots\}$，如果当 $k$ 充分大时，$\boldsymbol x_k$ 中的元素无限接近 $\boldsymbol q$ 中对应的元素，则称该向量序列当 $k \rightarrow \infty$ 时收敛到一个向量 $\boldsymbol q$。

　　定理 18　若 $P$ 是一个 $n \times n$ 的正则随机矩阵，则 $P$ 具有唯一的稳态向量 $\boldsymbol q$。进一步地，若 $x_0$ 是任一个初始状态，且 $\boldsymbol x_{k+1} = P \boldsymbol x_k, \; k = 0,1,2,\cdots$，则当 $k \rightarrow \infty$ 时，马尔可夫链 $\{\boldsymbol x_k\}$ 收敛到 $\boldsymbol q$。

　　这个定理说明初始状态对马尔可夫链的长期行为没有影响。