马尔可夫链（Markov-Chain）就是一种只需要当前状态就能决定下个状态分布的随机过程。 比如天气，明天的天气几乎只由今天决定。
马尔可夫性 (Markov Property) #
马尔可夫链的核心就是马尔可夫性，即未来的状态只与当前状态有关，与过去无关。
$$ P(X_{n+1} = x|X_{n}, X_{n-1}, \ldots, X_0) = P(X_{n+1} = x|X_n) $$即不管再前面有多少历史，都只在意最近的一次。
转移矩阵 #
一个有两种状态 \(A, B\) 的马尔可夫链，可以用一个转移矩阵表示：
$$ P = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} $$第一行表示从状态 \(A\) 转移到 \(A, B\) 的概率，第二行表示从状态 \(B\) 转移到 \(A, B\) 的概率。例如，如果当前在 \(A\) 状态，则保持在 \(A\) 的概率是 \(0.8\)，转移到 \(B\) 的概率是 \(0.2\)。
假设有一个初始状态分布向量 \(X_0 = [0.5, 0.5]\)，表示初始时有 \(50\%\) 的概率在 \(A\)，\(50\%\) 的概率在 \(B\)。转移一次后的状态分布为：
$$ X_1 = X_0 \cdot P = \\ [0.5, 0.5] \cdot \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = [0.6, 0.4] $$再转换一次的结果是：
$$ X_2 = X_1 \cdot P = \\ [0.6, 0.4] \cdot \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = [0.56, 0.44] $$这个结果等于先计算转移矩阵的平方，因为矩阵乘法是线性的且满足结合律：
$$ X_2 = (X_0 \cdot P) \cdot P = X_0 \cdot (P \cdot P) = X_0 \cdot P^2 $$所以，转移 \(n\) 次后的状态分布即为 \(X_0 \cdot P^n\)。
平稳分布 #
如果某个状态分布在转移后不变，则称该状态分布 \(\pi\) 为平稳分布。显然，平稳分布是转移矩阵的特征向量，对应的特征值为 \(1\)。转移矩阵不会改变这个向量。
$$ \pi = \pi \cdot P $$对于上面的例子，可以求出平稳分布：
$$ \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} \cdot \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} x \\ y \end{bmatrix} $$等于解方程：
$$ \begin{cases} 0.8x + 0.4y = x \\ 0.2x + 0.6y = y \end{cases} $$解方程得到平稳分布为：
$$ \pi = [0.625, 0.375] $$为什么会收敛？ #
初始分布就是一个向量，转移矩阵就是变换这个向量。如果转移矩阵中，存在唯一一个最大特征值为 \(1\) 的特征向量，那么多次施加转移矩阵后，所有与这个特征向量垂直的分量会逐渐缩小，只有在特征向量方向上的分量不变，最终占主导。
为什么要求唯一呢？否则会出现多个长期分布，而不会收敛到唯一一个平稳分布。
理论上达到这个分布，需要无限次次转移，因为其他方向上的分量会逐渐缩小，但永不消失。实际中，收敛的速度是比较快的，对于一些 \(3 \times 3\) 的转移矩阵，十几次转移就能相当接近平稳分布了。
收敛的条件？ #
需要满足以下条件，才会收敛：
- 转移矩阵是不可约的（任意两个状态之间都可以通过有限次转移到达）。
- 转移矩阵是非周期的（不会在某个状态上循环）。
- 有限状态空间。
收敛速度？ #
与转移矩阵的第二大特征值的绝对值有关，绝对值越接近 \(1\)，收敛速度越慢。
因为它决定了另一个方向上的分量缩小的速度。是另一股与平稳分布，这第一大势力对抗的力量；只要这个第二大特征向量的方向上还有分量，收敛就还未结束。