NO.17.tip: 马尔可夫链

背景

  假设 $x_t$ 捕获了关于系统状态的所有相关信息。这意味着在给定过去的情况下，这是预测未来的充分统计量，即对于任何 $\tau \ge 0$，

$$p(x_{t+\tau }\mid x_t,x_{1:t-1})=p(x_{t+\tau }\mid x_t)\text{\hspace{1em}(1)}$$

这被称为马尔可夫假设。在这种情况下，我们可以将任何有限长度序列的联合分布记作：

$$p(x_{1:T})=p(x_1)p(x_2\mid x_1)p(x_3\mid x_2)p(x_4\mid x_3)\cdots =p(x_1)\prod _{t=2}^{T}p(x_t\mid x_{t-1})\text{\hspace{1em}(2)}$$

这被称为马尔可夫链或马尔可夫模型。

源与流

  条件分布 $p(x_t\mid x_{t-1})$ 被称为转移函数、转移核或马尔可夫核。马尔可夫转移核是在给定时间 $t-1$ 的状态情况下，在时间 $t$ 状态上的条件分布，因此该分布满足条件 $p(x_t\mid x_{t-1})\ge 0$ 以及 ${\int }_{x\in \mathcal{X}}\mathrm{d}xp(x_t=x\mid x_{t-1})=1$。

如果我们假设转移函数 $p(x_t\mid x_{1:t-1})$ 与时间无关，那么模型被认为是齐次的、平稳的或时不变的。这是一个参数绑定的例子，因为同一个参数由多个变量共享。这个假设允许我们使用固定数量的参数对任意数量的变量进行建模。在本节的其余部分中，我们假定满足时不变假设。

  我们假设变量是离散的，因此 $X_t\in \{1,\dots ,K\}$，这被称为有限状态马尔可夫链。在这种情况下，条件分布 $p(X_t\mid X_{t-1})$ 可以写成一个 $K\times K$ 的矩阵 $\mathbf{A}$，称为转移矩阵（又称为转换矩阵），其中 $A_{ij}=p(X_t=j\mid X_{t-1}=i)$ 是从状态 $i$ 到状态 $j$ 的概率。矩阵每一行的和为 1，即 ${\sum }_j{A}_{ij}=1$，所以这被称为随机矩阵。

  平稳的有限状态马尔可夫链等价于随机自动机。通常，可以通过绘制有向图来可视化这种自动机，其中节点表示状态，箭头表示合法转移，即 $\mathbf{A}$ 的非零元素。这被称为状态转换图（又称为状态转移图）。弧上的权重是概率。

  马尔可夫链的关键就是在于对于转移矩阵的设计与研究。假设我们从马尔可夫链中连续抽取样本。在有限状态空间的情况下，我们可以认为这是从一个状态到另一个状态的“跳跃”。根据转换图的不同，我们在某些状态下花费的时间往往会比在其他状态下花费的更多。状态上的长期分布被称为马尔可夫链的平稳分布。

  设 $A_{ij}=p(X_t=j\mid X_{t-1}=i)$ 为一步转移矩阵，并且设 ${\pi }_t(j)=p(X_t=j)$ 为在时间 $t$ 处于状态 $j$ 的概率。

  如果我们在 ${\mathbf{\pi }}_0$ 的状态上有一个初始分布，那么在时间 1 处，我们有：

$${\pi }_1(j)=\sum _i{\pi }_0(i)A_{ij}\text{\hspace{1em}(3)}$$

或者，使用矩阵表示法表示为：${\mathbf{\pi }}_1={\mathbf{\pi }}_0\mathbf{A}$，其中我们遵循了假设 $\mathbf{\pi }$ 是行向量的标准约定，所以我们右乘转移矩阵。

  现在想象对这些方程进行迭代。如果我们达到了 $\mathbf{\pi }=\mathbf{\pi }\mathbf{A}$ 的阶段，那么称已经达到了平稳分布（也称为不变分布或平衡分布）。一旦进入平稳分布，那么将保持状态不变。