Markov Chain

马尔可夫链可以理解成 “下一步只看现在” 的规则系统。

比如天气：

• 如果今天是晴天，明天有 80% 还是晴天，15% 变多云，5% 下雨

• 如果今天是多云，明天有 45% 晴天，35% 多云，20% 下雨

• 如果今天是下雨，明天有 30% 晴天，40% 多云，30% 下雨

只要你知道今天的天气，就能算出明天的概率，不用去记昨天、前天……

你把这些概率整理成一个表格（转移矩阵），每次乘一下，就能得到“明天的概率分布”。

一直乘下去，最终会收敛到一个长期固定的比例（比如 67% 晴天，22% 多云，11% 下雨），这就是平稳分布，代表很长时间后天气的总体规律。

1. 核心定义

• 马尔可夫链是一系列随机变量：

$$X_0,X_1,X_2,\dots$$

• 满足马尔可夫性质：

$$P(X_{n+1}=s\mid X_n,X_{n-1},\dots ,X_0)=P(X_{n+1}=s\mid X_n)$$

即无记忆性：下一步状态只依赖当前状态，不依赖过去的历史。

---

2. 状态与转移矩阵

• 状态空间：所有可能的状态集合（有限或可数无限）
• 转移矩阵 $P$：
  • 元素 $p_{ij}=P(X_{t+1}=i\mid X_t=j)$
  • 列和为 1（列向量表示状态）或行和为 1（行向量表示状态）

天气示例：

$$P=\left[\begin{array}{ccc}0.8& 0.45& 0.3\\ 0.15& 0.35& 0.4\\ 0.05& 0.2& 0.3\end{array}\right]$$

---

3. 状态演化公式

• 当前状态的概率分布（列向量）为 $x_t$：

$$x_{t+1}=P\cdot x_t$$

• 多步：

$$x_n=P^n\cdot x_0$$

---

4. 平稳分布（Stationary Distribution）

• 当 $n\to \infty$，若收敛到 $x^{\ast }$：

$$x^{\ast }=P\cdot x^{\ast }$$

• 这是 $P$ 的特征向量，特征值 $\lambda =1$
• 含义：长期概率分布（不变分布）

---

5. 分类

1. 齐次马尔可夫链（Homogeneous）：转移概率不随时间变化
2. 非齐次马尔可夫链（Non-Homogeneous）：转移概率随时间变化
3. 有限状态 / 无限状态
4. 可约 / 不可约：是否可以从任一状态到达任一状态
5. 周期性 / 非周期性

---

6. 应用

• PageRank（网页排名）
• 天气预测
• 用户行为分析
• 自然语言模型（N-gram）
• 生物序列建模（DNA、蛋白质）
• 金融市场状态切换