线性代数 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$。

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

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注