线性代数 Cheat Sheet 4-9：马尔可夫链中的应用
马尔可夫链习惯上用来描述用用一种方法进行多次实验或测量，实验中每次测试的结果属于几个指定的可能结果之一，每次测试结果仅依赖于最近的前一次测试。
一个具有非负元素且各元素的数值相加等于 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。
这个定理说明初始状态对马尔可夫链的长期行为没有影响。