马尔可夫链

Markov chain MC
具有无记忆性的离散参数随机过程

过去所有的信息都已经被保存到了现在的状态，基于现在就可以预测未来。

The future is independent of the past， given the present.
未来独立于过去，只基于当下。

一、马尔可夫性

Markov Property

马尔可夫性：马尔可夫链为状态空间中经过从一个状态到另一个状态的转换的随机过程，该过程要求具备“无记忆性 ”，即下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。

\begin{array}{r} P {X_{t + 1} = j ∣ X_{0} = i_{0}, \dots, X_{t - 1} = i_{t - 1}, X_{t} = i} = P {X_{t + 1} = j ∣ X_{t} = i} \end{array}

二、转移概率

1. 一步转移概率

此条件概率称为马尔可夫链在时刻 $t$ 处于状态 $i$ 条件下，在时刻 $t + 1$ 转移到状态 $j$ 的转移概率：

\begin{array}{r} p_{i j} = P {X_{t + 1} = j ∣ X_{t} = i} \end{array}

通常将一步转移概率排成无穷维度的矩阵，作为时齐马尔可夫链的状态转移矩阵：（当状态空间为有限集时， $P$ 就为有限矩阵，阶数等于状态空间的状态数）

\begin{array}{r} P = (\begin{array}{c} p_{00} & p_{01} & \dots & p_{0 j} & \dots \\ p_{10} & p_{11} & \dots & p_{1 j} & \dots \\ ⋮ & ⋮ & ⋮ \\ p_{i 0} & p_{i 1} & \dots & p_{i j} & \dots \\ ⋮ & ⋮ & ⋮ \end{array}) \end{array}

马尔可夫链在时刻 $t$ 从任何一个状态 $i$ 出发，到另一个时刻 $t + 1$ 必然转移到某状态 $j$ 中（必然事件），对于任意状态 $i, j, p_{i j} \geq 0$ , 有：

\begin{array}{r} \sum_{j = 0}^{+ \infty} p_{i j} = 1 \end{array}

这意味着状态转移矩阵的每一行的元素之和都为 1

2. 多步转移概率

$n$ 步转移概率定义为：马尔可夫链 $X_{t}$ 在时刻 $t$ 处于状态 $i$ 的条件下，经过 $n$ 步转移到达状态 $j$ 的转移概率。如果 $X_{t}$ 为时齐的，则可以简单记为 $p_{i j} (n)$

\begin{array}{r} p_{i j} (t, t + n) = p_{i j} (n) = P {X_{t + n} = j ∣ X_{t} = i} \end{array}

Champman-Kolmogorov Equation C-K 方程：

\begin{array}{r} p_{i j} (n + m) = \sum_{k = 0}^{\infty} p_{i k} (n) p_{k j} (m) \end{array}

写为矩阵的形式，进一步由递推关系知：时齐马尔可夫链的 $n$ 步转移概率是一步转移概率矩阵的 $n$ 次方：（矩阵的幂可以利用矩阵对角化方便地计算）

\begin{array}{r} P (n + m) = P (n) P (m) \Rightarrow P (n) = P P (n - 1) = P^{n} \end{array}

对马尔可夫链 $X_{t}$ ，定义 $p_{j} (0)$ 为初始一维分布， $p_{j} (n)$ 为任一时刻 $n$ 的一维分布：

p_{j} (0) = P {X_{0} = j} p_{j} (n) = P {X_{n} = j}, j \in I

时齐马尔可夫链在任一时刻 $n$ 的一维分布由它的初始分布和 $n$ 步状态转移概率矩阵确定：

\begin{aligned} P {X_{n} = j} = \sum_{i = 0}^{\infty} P {X_{n} = j ∣ X_{0} = i} P {X_{0} = i} \\ \Rightarrow p_{j} (n) = \sum_{i = 0}^{\infty} p_{i} (0) p_{i j} (n) \Rightarrow p (n) = p (0) P (n) \end{aligned}

\begin{array}{r} p (n) = {(\begin{array}{c} p_{0} (n) \\ p_{1} (n) \\ ⋮ \\ p_{j} (n) \\ ⋮ \end{array})}^{T} = {(\begin{array}{c} p_{0} (0) \\ p_{1} (0)) \\ ⋮ \\ p_{j} (0) \\ ⋮ \end{array})}^{T} {(\begin{array}{c} p_{00} & p_{01} & \dots & p_{0 j} & \dots \\ p_{10} & p_{11} & \dots & p_{1 j} & \dots \\ ⋮ & ⋮ & ⋮ \\ p_{i 0} & p_{i 1} & \dots & p_{i j} & \dots \\ ⋮ & ⋮ & ⋮ \end{array})}^{n} \end{array}

三、遍历性

主要研究当步数趋于无穷时的转移概率

遍历性：对于固定的状态 $j$ ，不管链在某一时刻从什么状态出发，通过长时间转移，到达状态 $j$ 的概率都接近 $π_{j}$

如果对于所有 $i, j \in I$ ，转移概率 $p_{i j}$ 存在极限，则称该马尔科夫链具有遍历性，进一步得到马尔可夫链的极限分布 $π$ ：

π_{j} = lim_{n \to \infty} p_{i j} (n) \Rightarrow π = (\begin{matrix} π_{0} & π_{1} & \dots & π_{j} & \dots \end{matrix}) \sum_{j}^{} π_{j} = 1

\begin{array}{r} π = π P π_{j} = \sum_{i = 0}^{N} π_{i} p_{i j} \sum_{j = 0}^{N} π_{j} = 1 \end{array}

基本应用

用于动力系统、化学反应、排队论、市场行为和信息检索的数学建模

Google PageRank 可以看作网页图上的马尔可夫链：随机访问者在每一步沿当前网页的链接跳转，必要时再以小概率随机跳到任意网页。长期访问比例形成一个稳态分布，比例越高的网页排名越靠前，因此网页排名可转化为随机游走的主特征向量计算。

马尔可夫链可被应用于蒙特卡洛方法中，形成马尔可夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC）

此外作为结构最简单的马尔可夫模型（Markov model）
一些机器学习算法，以马尔可夫链为理论基础，例如
隐马尔可夫模型（Hidden Markov Model, HMM）
马尔可夫随机场（Markov Random Field, MRF）
马尔可夫决策过程（Markov decision process, MDP）

矩阵谱图像

采用列随机矩阵约定时，正 Markov 矩阵满足两个条件：所有元素为正，并且每一列求和为 $1$ 。若 $u_{0}$ 是概率向量，则 $A u_{0}$ 仍非负且分量和仍为 $1$ ，因为

[1 \dots 1] A = [1 \dots 1] .

若采用行随机矩阵约定，同一性质写作 $u_{k + 1} = u_{k} P$ 且 $P$ 的每一行求和为 $1$ 。

正则 Markov 链的核心谱图像是： $λ_{1} = 1$ ，其他特征值模长小于 $1$ ，因此 $A^{k} u_{0}$ 会收敛到稳态特征向量。

列随机约定下的概率演化

若把分布写成列概率向量，则转移矩阵记为Markov矩阵 $A$ ，演化公式为

u_{k + 1} = A u_{k}, u_{k} = A^{k} u_{0} .

此时矩阵要求每列求和为 $1$ ，而不是每行求和为 $1$ ：

a_{i j} \geq 0, \sum_{i} a_{i j} = 1, [1 \dots 1] A = [1 \dots 1] .

这与前文行随机约定 $p (n) = p (0) P^{n}$ 等价，只是 $A = P^{T}$ ，所以稳态方程从 $π P = π$ 变为

A u_{\infty} = u_{\infty}, 1^{T} u_{\infty} = 1.

例如租车在 Denver 内外之间转移：

A = [\begin{matrix} .80 & .05 \\ .20 & .95 \end{matrix}], u_{0} = [\begin{matrix} .02 \\ .98 \end{matrix}] .

第一步和第二步为

u_{1} = A u_{0} = [\begin{matrix} .065 \\ .935 \end{matrix}], u_{2} = A u_{1} = [\begin{matrix} .09875 \\ .90125 \end{matrix}] .

该矩阵的特征值是 $1$ 和 $.75$ ，归一化的稳态特征向量为

u_{\infty} = [\begin{matrix} .2 \\ .8 \end{matrix}] .

也可写成 $u_{\infty} = (.2, .8)^{T}$ 。
因此长期有约 $20 %$ 的车在 Denver 内， $80 %$ 在 Denver 外。若除 $λ = 1$ 外所有特征值都满足 $| λ | < 1$ ，则任意初始概率分布都会收敛到稳态；若存在 $λ_{2} = - 1$ ，如交换矩阵

[\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}],

分布会在两个状态之间振荡。正则或本原条件排除这种周期性，从而保证极限分布存在。