• https://www.eecs70.org/assets/pdf/notes/n21.pdf

有限马尔可夫链 (Finite Markov Chains) 学习笔记

本笔记基于你的手写笔记逻辑顺序进行整理，并结合 CS 70 Course Notes (Note 21) 补充了推导细节与缺失知识点，解答了你在手写笔记中标记的疑问。

一、 引言与基本概念

1.1 什么是马尔可夫链？

马尔可夫链（Markov Chain）是描述有限或可数状态空间中随机运动的数学模型。它的核心特征是无记忆性（Amnesic / Markov Property）：

在已知“现在”状态的条件下，“未来”的状态只与“现在”有关，而与“过去”的历史无关。

在你的手写笔记第一页（IMG_20260531_181317.jpg）中，你提到了一个直观的例子：

• 20级楼梯的攀爬问题：一个人从地面（0级）出发，每一步以概率 $p = 0.9$ 向上爬一级，以概率 $1-p = 0.1$ 摔回地面。求登顶所需的平均步数。这个过程的每一步去向只取决于当前在第几级，与之前是怎么爬上来的无关，因此是一个典型的马尔可夫链模型。

1.2 状态、初始状态与转移概率

设马尔可夫链在时刻 $n = 0, 1, 2, \dots$ 的状态为 $X_n$。

1. 初始分布（Initial Distribution）

我们在时刻 $0$ 所处的各个状态的概率称为初始分布，记为 $\pi_0$。 对于一个双状态（状态空间为 $\{0, 1\}$）的系统，初始分布为：

$\mathbb{P}[X_0 = 0] = \pi_0(0), \quad \mathbb{P}[X_0 = 1] = \pi_0(1) \quad (\text{其中 } \pi_0(0) + \pi_0(1) = 1)$

解答你在 IMG_20260531_181317.jpg 中的疑问：

• 问题：“这是初始状态吗？我有些忘了信息论中马尔可夫链是其因怎么做的了。”
• 解答：是的，这正是初始概率分布。在信息论中，马尔可夫链常用于模拟信源（如马尔可夫信源）。在计算信源的**熵率（Entropy Rate）**时，我们同样需要先通过状态转移矩阵求解出平稳分布（即不变分布 $\pi$），然后用公式 $H(\mathcal{X}) = -\sum_{i} \pi(i) \sum_{j} P(i,j) \log P(i,j)$ 来计算。因此，这里的 $\pi_0$ 作为初始分布，是马尔可夫链随时间演变起点，它与信息论中的稳态分析有着紧密的继承关系。

2. 双状态转移图与转移矩阵

参考 IMG_20260531_181317.jpg 的手写示意图，设状态为 $0$ 和 $1$，转移规则如下：

• 若当前在 $0$，下一步有 $a$ 的概率去往 $1$，有 $1-a$ 的概率留在 $0$；
• 若当前在 $1$，下一步有 $a$ 的概率去往 $0$，有 $1-a$ 的概率留在 $1$。

写成状态转移矩阵 (Transition Probability Matrix) $P$ 的形式（行表示当前状态，列表示下一时刻状态）：

$P = \begin{bmatrix} 1-a & a \\ a & 1-a \end{bmatrix}$

二、 状态转移与 $P^n$ 的计算

在笔记第二页（IMG_20260531_181324.jpg）中，你对 $n$ 步转移的计算公式表示了困惑。我们在这里进行通俗和严谨的拆解：

2.1 深入理解公式 $\pi_n = \pi_0 P^n$

解答你在 IMG_20260531_181324.jpg 中的疑问：

• 问题：“这个公式我并不理解作用，也不知道应该如何使用。”
• 直观解释：
  • 设想有大量的粒子在状态空间中根据转移概率移动。
  • $\pi_0$ 是第 $0$ 天这些粒子在各个状态的分布比例。
  • 经过 $1$ 天的转移后，第 $1$ 天的分布为 $\pi_1 = \pi_0 P$。
  • 经过 $2$ 天的转移后，分布为 $\pi_2 = \pi_1 P = (\pi_0 P) P = \pi_0 P^2$。
  • 依此类推，经过 $n$ 天转移后，分布就是 $\pi_n = \pi_0 P^n$。
  • 它的作用：允许我们仅通过初始状态分布和转移矩阵，直接预测任意未来的第 $n$ 步时，系统处于各个状态的概率。

2.2 双状态马尔可夫链 $P^n$ 的详细推导过程

针对你提到的“双状态马尔可夫链的计算我也看不懂”，我们使用矩阵特征值对角化方法来完美推导并还原 CS 70 课程 note 中的公式 (6)：

我们需要计算：

$P^n = \begin{bmatrix} 1-a & a \\ a & 1-a \end{bmatrix}^n$

推导步骤：

1. 求特征值： 解特征方程 $\det(P - \lambda I) = 0$：

   $\det\begin{bmatrix} 1-a-\lambda & a \\ a & 1-a-\lambda \end{bmatrix} = (1-a-\lambda)^2 - a^2 = 0$

   由此可得 $1-a-\lambda = \pm a$，解得两个特征值为：

   $\lambda_1 = 1, \quad \lambda_2 = 1-2a$

2. 求特征向量：

   • 对于 $\lambda_1 = 1$：

     $(P - I)v_1 = 0 \Rightarrow \begin{bmatrix} -a & a \\ a & -a \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = 0 \Rightarrow v_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$

   • 对于 $\lambda_2 = 1-2a$：

     $(P - (1-2a)I)v_2 = 0 \Rightarrow \begin{bmatrix} a & a \\ a & a \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = 0 \Rightarrow v_2 = \begin{bmatrix} 1 \\ -1 \end{bmatrix}$

3. 对角化重组 $P^n = V D^n V^{-1}$： 令对角矩阵 $D = \begin{bmatrix} 1 & 0 \\ 0 & 1-2a \end{bmatrix}$，特征向量矩阵 $V = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$。其逆矩阵为 $V^{-1} = \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$。 因此：

   $P^n = V D^n V^{-1} = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & (1-2a)^n \end{bmatrix} \left( \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \right)$

   $P^n = \frac{1}{2} \begin{bmatrix} 1 & (1-2a)^n \\ 1 & -(1-2a)^n \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = \begin{bmatrix} \frac{1}{2} + \frac{1}{2}(1-2a)^n & \frac{1}{2} - \frac{1}{2}(1-2a)^n \\ \frac{1}{2} - \frac{1}{2}(1-2a)^n & \frac{1}{2} + \frac{1}{2}(1-2a)^n \end{bmatrix}$

这正是 CS 70 课程笔记中的公式 (6)！当 $0 < a < 1$ 时，随着 $n \to \infty$，恒有 $(1-2a)^n \to 0$，因此：

$\lim_{n\to\infty} P^n = \begin{bmatrix} 1/2 & 1/2 \\ 1/2 & 1/2 \end{bmatrix}$

这意味着无论初始状态是什么，长期来看，系统处于状态 $0$ 和 $1$ 的概率都将趋近于 $\frac{1}{2}$。

2.3 经典例题：天气预测

针对你手写笔记第二、三页（IMG_20260531_181324.jpg 与 IMG_20260531_181334.jpg）中的天气例题：

纠错说明： 手写原文中写道：“若今天无雨，明天60%雨”。根据你列出的转移矩阵 $P = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix}$，“无雨”即晴天（状态0），但晴天转移已定义为“明天70%晴（即30%雨）”。因此，“若今天无雨，明天60%雨”属于笔误，应修正为：“若今天雨天，明天60%雨天（即40%晴天）”。

【题目描述】

设状态 $0$ 为晴天，状态 $1$ 为雨天。天气变化的转移概率如下：

• 若今天晴天，明天有 $70\%$ 概率晴天， $30\%$ 概率雨天。
• 若今天雨天，明天有 $60\%$ 概率雨天， $40\%$ 概率晴天。

其转移矩阵为：

$P = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix}$

【问题 1：连续事件的条件概率（链式法则）】

问：若今天晴天（$X_0 = 0$），求明天晴天（$X_1 = 0$）且后天雨天（$X_2 = 1$）的联合概率。 解：利用马尔可夫链的无记忆性与乘法公式：

$\mathbb{P}[X_0 = 0, X_1 = 0, X_2 = 1] = \mathbb{P}[X_0 = 0] \cdot P(0,0) \cdot P(0,1)$

由于已知今天必定晴天，则 $\mathbb{P}[X_0 = 0] = 1$：

$\mathbb{P}[X_0 = 0, X_1 = 0, X_2 = 1] = 1 \times 0.7 \times 0.3 = 0.21$

这证实了“连续随机事件的发生概率可以使用各步转移概率连续相乘”。

【问题 2：预测第 $n$ 天的概率分布】

问：若今天晴天，即 $\pi_0 = [1, 0]$，求后天（第2天）天气的概率分布 $\pi_2$。 解： 根据 $\pi_2 = \pi_0 P^2$，我们先计算 $P^2$：

$P^2 = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} (0.7 \times 0.7 + 0.3 \times 0.4) & (0.7 \times 0.3 + 0.3 \times 0.6) \\ (0.4 \times 0.7 + 0.6 \times 0.4) & (0.4 \times 0.3 + 0.6 \times 0.6) \end{bmatrix}$

$P^2 = \begin{bmatrix} 0.49 + 0.12 & 0.21 + 0.18 \\ 0.28 + 0.24 & 0.12 + 0.36 \end{bmatrix} = \begin{bmatrix} 0.61 & 0.39 \\ 0.52 & 0.48 \end{bmatrix}$

因此：

$\pi_2 = [1, 0] \begin{bmatrix} 0.61 & 0.39 \\ 0.52 & 0.48 \end{bmatrix} = [0.61, 0.39]$

即：后天有 $61\%$ 的概率为晴天，$39\%$ 的概率为雨天。

三、 不变分布与收敛性

3.1 什么是不变分布？它有什么用？

在手写笔记第三、四页（IMG_20260531_181334.jpg 与 IMG_20260531_181339.jpg）中，你提出了疑问。

解答与纠错：

• 问题：“到底什么是不变分布，有什么用呢？”
• 直观解答：不变分布（Invariant / Stationary Distribution） $\pi$ 满足 $\pi = \pi P$。也就是说，如果系统在某时刻的概率分布已经达到了 $\pi$，那么经过一步转移后，它的分布依然保持 $\pi$ 不变。
• 手写笔记纠错：你在第四页（IMG_20260531_181339.jpg）写道：“不变分布可以帮我们求初始分布”。这是不对的。初始分布 $\pi_0$ 是我们人为设定的起点，不需要通过不变分布去求。相反，不变分布代表的是马尔可夫链的“长期稳态（Steady State）”。无论你初始分布 $\pi_0$ 是什么，只要时间足够长（$n \to \infty$），系统最终都会收敛到这个唯一的不变分布 $\pi$。
• 核心用途：它能告诉我们系统在经历长期演变后的稳态概率。例如，在 Google 的 PageRank 算法中，不变分布 $\pi(v)$ 就代表了用户长期随机浏览网页时，停留在网页 $v$ 的概率（即网页的重要性排名权重）。

3.2 稳态收敛的两个核心条件（补充缺失内容）

在手写笔记中，你只提到了“不可约性”。要保证系统在长期运行后一定能收敛到唯一的稳态，必须同时满足两个条件：

1. 不可约性 (Irreducibility) —— 对应 IMG_20260531_181334.jpg 笔记

• 定义：从任意一个状态出发，都可以在有限步内到达其他任意一个状态（即状态转移图是强连通的）。
• 作用：确保没有状态会被永远孤立。

2. 非周期性 (Aperiodicity) —— 补充手写笔记遗漏部分

• 定义：各状态的周期为 $1$。周期是指从一个状态出发回到自身所需步数的最大公约数。
• 直观理解：如果系统是周期的（例如在两个状态之间像钟摆一样单调地来回跳动，周期为2），它的概率分布就会永远振荡，而不会收敛到一个静止的极限分布。
• 快速判断法：若转移图中至少包含一个自环（Self-loop），则该马尔可夫链必然是非周期的。

3.3 经典例题：三网页简化 PageRank 计算

结合你第四页（IMG_20260531_181339.jpg）给出的联立方程组，我们还原其背后的转移模型并进行求解。

【模型构建】

假设有三个网页 A、B、C。其转移规律（对应你列出的方程组）满足转移矩阵：

$P = \begin{bmatrix} 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \\ 1 & 0 & 0 \end{bmatrix}$

【求解过程】

设不变分布为 $\pi = [\pi(A), \pi(B), \pi(C)]$，满足 $\pi P = \pi$：

$\begin{bmatrix} \pi(A) & \pi(B) & \pi(C) \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \\ 1 & 0 & 0 \end{bmatrix} = \begin{bmatrix} \pi(A) & \pi(B) & \pi(C) \end{bmatrix}$

展开得到方程组：

$\begin{cases} \pi(A) = 0.5\pi(B) + \pi(C) \\ \pi(B) = \pi(A) \\ \pi(C) = 0.5\pi(B) \end{cases}$

由于概率总和为 1，我们引入归一化条件：

$\pi(A) + \pi(B) + \pi(C) = 1$

将前三个关系代入归一化公式：

$\pi(A) = \pi(B)$

$\pi(C) = 0.5\pi(A)$

$\pi(A) + \pi(A) + 0.5\pi(A) = 1 \Rightarrow 2.5\pi(A) = 1 \Rightarrow \pi(A) = 0.4$

解得唯一的不变分布：

$\pi(A) = 0.4, \quad \pi(B) = 0.4, \quad \pi(C) = 0.2$

3.4 无向图上的随机游走 (Random Walk on Graph)

你在第四页（IMG_20260531_181339.jpg）记录了公式：

$\pi(v) = \frac{\text{deg}(v)}{2|E|}$

【知识点补充】

在一个无向图 $G=(V,E)$ 上，若每个结点的转移概率是等概率地流向它的所有邻居结点（即 $\text{deg}(v)$ 个邻居），只要该图是连通的且非二部图，其长期访问概率（稳态分布）就与结点的度数（Degree）成正比。

【新增简单例题】

【题目】 设一个三角形无向图，顶点为 $A, B, C$，各顶点两两相连。求顶点 $A$ 的长期稳态访问概率。 【解】

1. 边的总数 $|E| = 3$。分母为 $2|E| = 6$。

2. 每个顶点的度数 $\text{deg}(A) = \text{deg}(B) = \text{deg}(C) = 2$。

3. 利用公式计算：

   $\pi(A) = \frac{\text{deg}(A)}{2|E|} = \frac{2}{6} = \frac{1}{3}$

   由于对称性，每个顶点被访问的稳态概率均为 $\frac{1}{3}$。

四、 命中时间 (Hitting Time)

命中时间（或击中时间） $\beta(i)$ 是指：从状态 $i$ 出发，首次到达目标状态集合 $A$ 所需的期望步数。

4.1 第一步方程 (First-Step Equations)

其求解的核心思想是根据“第一步去往何处”进行全概率展开：

$\beta(i) = \begin{cases} 0, & i \in A \\ 1 + \sum_{j} P(i,j)\beta(j), & i \notin A \end{cases}$

4.2 经典例题：2级楼梯登顶问题（手写笔记第4-5页完整还原）

对应你笔记（IMG_20260531_181339.jpg 与 IMG_20260531_181345.jpg）中的例题，你尝试求解了 $2$ 级楼梯的情况。

【题目描述】

你当前在第 0 级。每一步：有 $p = 0.5$ 的概率升 $1$ 级，有 $1-p = 0.5$ 的概率滑落回第 $0$ 级。求登顶（到达第 $2$ 级）所需的期望步数。 目标集合 $A = \{2\}$，因此末端条件为 $\beta(2) = 0$。

【列出第一步方程】

根据状态转移规则列出方程：

1. 对于状态 $0$：

   $\beta(0) = 1 + 0.5\beta(1) + 0.5\beta(0)$

2. 对于状态 $1$：

   $\beta(1) = 1 + 0.5\beta(2) + 0.5\beta(0) = 1 + 0.5(0) + 0.5\beta(0) = 1 + 0.5\beta(0)$

【求解步骤】

1. 整理状态 0 的方程：

   $\beta(0) - 0.5\beta(0) = 1 + 0.5\beta(1) \Rightarrow 0.5\beta(0) = 1 + 0.5\beta(1) \Rightarrow \beta(0) = 2 + \beta(1)$

2. 将状态 1 的方程代入：

   $\beta(0) = 2 + (1 + 0.5\beta(0)) \Rightarrow \beta(0) = 3 + 0.5\beta(0)$

   $0.5\beta(0) = 3 \Rightarrow \beta(0) = 6$

3. 计算 $\beta(1)$：

   $\beta(1) = 1 + 0.5(6) = 4$

结论：从地面出发，平均需要 $6$ 步才能成功登上 $2$ 级楼梯顶端。这完美对应了你手写笔记第5页的结论：“\beta(0) = 6，6步登顶”。

【拓展：20级楼梯的一般公式】

若楼梯变为 20 级，利用 CS 70 Note 21 中的公式 (13)：

$\beta(0) = \frac{p^{-20} - 1}{1 - p}$

• 当 $p = 0.9$ 时， $\beta(0) \approx 72$ 步。
• 当 $p = 0.8$ 时， $\beta(0) \approx 429$ 步。

五、 在 B 之前到达 A 的概率与赌徒输光游戏

针对你在最后一页（IMG_20260531_181345.jpg）写下的疑问：

解答你在 IMG_20260531_181345.jpg 中的疑问：

• 问题：“看不懂，赌徒输光游戏？”
• 概念大白话翻译：
  • 想象你在赌场玩游戏。你带了 $n$ 元钱。
  • 你的目标是赚到 $M$ 元钱（集合 $A = \{M\}$）。
  • 你的底线是输光破产，也就是 $0$ 元钱（集合 $B = \{0\}$）。
  • 只要你手里的钱还没达到 $M$ 且没输光到 $0$，你就得继续赌下去。
  • “在 B 之前到达 A 的概率”就是问：“你在中途破产（输到0）之前，成功赢到目标金额 $M$ 离场的概率是多少？” 这就是概率论中经典的赌徒输光问题 (Gambler’s Ruin)。

5.1 第一步方程

设 $\alpha(n)$ 为拥有 $n$ 元钱时，成功赢到 $M$ 元（先于破产 $0$ 元）的概率。

• 边界条件：$\alpha(M) = 1$ （已经达到目标）， $\alpha(0) = 0$ （已经破产）。

• 中途方程（设每局获胜概率为 $p$，输掉概率为 $1-p$）：

  $\alpha(n) = p\alpha(n+1) + (1-p)\alpha(n-1) \quad (\text{其中 } 0 < n < M)$

5.2 经典例题：不公平硬币的赌博

【题目描述】

你携带 $10$ 元钱进入赌场（即初始资金 $n = 10$）。每一局你有 $p = 0.48$ 的概率赢 $1$ 元，有 $1-p = 0.52$ 的概率输 $1$ 元。你的目标是达到 $100$ 元（即 $M = 100$）后离场。求你成功达到 $100$ 元的概率。

【推导与求解】

这是典型的差分方程问题。 设 $\rho = \frac{1-p}{p} = \frac{0.52}{0.48} \approx 1.0833 > 1$。 其特征根方程为：

$p\lambda^2 - \lambda + (1-p) = 0 \Rightarrow (\lambda - 1)\left(\lambda - \frac{1-p}{p}\right) = 0$

通解形式为：$\alpha(n) = c_1 \cdot 1^n + c_2 \cdot \rho^n = c_1 + c_2 \rho^n$。

结合边界条件 $\alpha(0) = 0$ 与 $\alpha(M) = 1$：

1. $c_1 + c_2 = 0 \Rightarrow c_2 = -c_1$
2. $c_1(1 - \rho^M) = 1 \Rightarrow c_1 = \frac{1}{1 - \rho^M}$

从而得到通解公式（即 CS 70 Note 21 中的公式 14）：

$\alpha(n) = \frac{1 - \rho^n}{1 - \rho^M}$

将本题数据 $n = 10$, $M = 100$, $\rho \approx 1.0833$ 代入：

$\alpha(10) = \frac{1 - 1.0833^{10}}{1 - 1.0833^{100}} \approx \frac{1 - 2.22}{1 - 2948.3} \approx 4 \times 10^{-4} = 0.04\%$

结论与警示： 在单局胜率稍微偏向庄家（$48\%$ vs $52\%$）的不公平游戏中，如果你妄图通过连续不断的“小额投注”赚取大钱，你在中途破产的概率高达 $99.96\%$。这也是为什么赌场（Casino）总是立于不败之地的数学原因！