Lecture 26: Markov Chains & Conditional Expectation（马尔可夫链与条件期望）

目录 · ← l26 · appendix →

Lecture 26: Markov Chains & Conditional Expectation（马尔可夫链与条件期望）

概述

前几讲的随机变量都是”一次性”的：抛一次硬币、掷一次骰子、抽一次样。但真实系统几乎都是随时间演化的：网页浏览者从一个链接跳到下一个链接、赌徒的资产一分一分地变化、机器的状态在”正常/故障”之间切换。本讲研究这类随机过程 (random process) 中最基本的一类：有限马尔可夫链 (finite Markov chain)。

马尔可夫链的全部精髓是一句话：未来只取决于现在，与过去无关（马尔可夫性质 (Markov property)）。这条”健忘”假设看似极强，但它覆盖了大量真实系统，而且让所有计算都变成矩阵代数（转移矩阵 $P$）与线性方程组（平衡方程、首步方程）。

本讲要回答四类问题：

1. 长期行为：链跑很久后，处于各状态的时间比例是多少？答案由平稳分布 (stationary distribution) $\pi$ 给出，满足 $\pi P = \pi$。
2. 吸收概率：从状态 $i$ 出发，最终被某个吸收态吸收的概率是多少？用首步分析 (first-step analysis) 列方程组。
3. 吸收时间：期望多少步被吸收？同样是首步方程。
4. 条件期望：如何在只掌握部分信息时给出最优估计，以及如何用全期望公式把复杂期望”分而治之”。

最后两项（首步分析与条件期望）本质上是同一个工具的两种面貌：首步方程就是一次条件期望展开。

核心概念的直观解释

随机过程与状态 (Random Process and State)

• 定义：随机过程是一族带时间下标的随机变量 $\{X_n : n = 0,1,2,\dots\}$。状态空间 (state space) $\mathcal{X}$ 是 $X_n$ 所有可能取值的集合。本课只讨论有限情形，即 $\mathcal{X} = \{1,2,\dots,K\}$（有时用 $\{0,1,\dots,K-1\}$ 或 $\{A,B,C,\dots\}$）。$X_n$ 称为过程在时刻/步 (step) $n$ 的状态 (state)。
• 直观解释：把 $X_n$ 想成”游戏在第 $n$ 步所处的位置”。状态空间是”所有可能站的位置”，随机过程是”位置的随机游走轨迹”。
• 具体示例：$\mathcal{X} = \{\text{晴},\text{阴},\text{雨}\}$，$X_n$ = 第 $n$ 天的天气。或 $\mathcal{X} = \{0,1,\dots,100\}$，$X_n$ = 赌徒在第 $n$ 局的资金。

马尔可夫链 (Markov Chain) 与马尔可夫性质 (Markov Property)

• 定义：设状态空间 $\mathcal{X} = \{1,\dots,K\}$。给定初始分布 (initial distribution) $\pi_0$（$\pi_0(i)\ge0$、$\sum_i\pi_0(i)=1$）与转移概率矩阵 (transition probability matrix) $P$（$K\times K$，$P(i,j)\ge0$、$\sum_j P(i,j)=1$），定义随机序列 $\{X_n\}$ 为 \(\Pr[X_0 = i] = \pi_0(i), \qquad \Pr[X_{n+1} = j \mid X_n = i,\ X_{n-1},\dots,X_0] = P(i,j) \quad(\forall n\ge0).\) 第二条即马尔可夫性质：给定当前状态 $X_n=i$，下一状态的条件分布不依赖更早的历史 $X_{n-1},\dots,X_0$。等价地 \(\Pr[X_{n+1}=j \mid X_n = i,\ X_{n-1},\dots,X_0] = \Pr[X_{n+1}=j\mid X_n=i] = P(i,j).\)

• 直观解释（”它是什么意思？”）：链是健忘 (amnesic) 的。以两状态链（$\mathcal{X}=\{0,1\}$，参数 $a\in[0,1]$）为例：若在状态 $0$，就抛一枚正面概率为 $a$ 的硬币，正面则跳到 $1$、反面则留在 $0$；若在状态 $1$，同样抛这枚硬币，正面则跳到 $0$、反面则留在 $1$。“它是从状态 $0$ 待了很久才跳到 $1$ 的，还是刚跳进状态 $0$ 的”，对下一步毫无影响——因为在状态 $0$ 时它总是抛同样一枚硬币。
  • 现实类比：醉汉走路——他下一步往哪走只看他现在站在哪，不记得自己是怎么走到这里的。天气——明天是否下雨只取决于今天（在这个简化模型里），不取决于前天的天气。棋子位置——国际象棋的局面（棋子的完整配置）是马尔可夫的：从当前局面出发，未来只由规则和当前局面决定，与走到这个局面的历史无关。注意这一点很微妙：”棋子的位置”不够（要知道”这个兵是否还没走过”，所以状态必须是完整局面）——选对状态空间是建模马尔可夫链的关键难点。

• 具体示例（两状态链，$a=0.3$）： \(P = \begin{pmatrix} 1-a & a \\ a & 1-a\end{pmatrix} \overset{a=0.3}{=} \begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7\end{pmatrix}.\) 注意这条链是完全对称的（两条对角元都是 $1-a$、两条非对角元都是 $a$），所以由对称性，长期来看它状态 $0$ 与状态 $1$ 各占一半时间。脚本模拟 $10^6$ 步得状态 $0$ 的时间比例 $0.49983$，与理论 $0.5$ 吻合。

  作为对照，另一条非对称的两状态链 \(P^{\prime} = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6\end{pmatrix}\) （从 $0$ 跳到 $1$ 的概率是 $0.3$，从 $1$ 跳到 $0$ 的概率是 $0.4$——两个方向不一样）。它的长期时间比例不再是各半，而是解 $\pi P^{\prime}=\pi$ 得到的 $\pi = (\frac47,\frac37) = (0.571429, 0.428571)$。脚本验算 $\pi P^{\prime} = \pi$ ✓（幂迭代 $P^{\prime}^{50}$ 的两行都等于 $(4/7, 3/7)$ ✓），且 $2\times10^6$ 步模拟的时间比例是 $0.57091$ ✓。这两条链必须严格区分：本讲后面凡涉及 $(1-2a)^n$ 这类闭式，都只对对称链成立。

转移矩阵 (Transition Matrix) 与状态转移图 (State Transition Diagram)

• 定义：$P_{ij} = P(i,j) = \Pr[X_{n+1}=j\mid X_n=i]$。$P$ 必须满足 \(P_{ij}\ge0\ \ \forall i,j, \qquad \sum_{j=1}^{K}P_{ij} = 1\ \ \forall i.\) 满足第二条的矩阵称为行随机矩阵 (row-stochastic matrix)——每一行的和为 $1$（不是每一列！）。
• 直观解释：第 $i$ 行描述”从 $i$ 出发，下一步去哪儿”的完整概率分布。行和为 $1$ 是”必须走到某个地方”的必然结果。状态转移图则把 $P$ 画成有向图：$P_{ij}>0$ 时从 $i$ 画一条指向 $j$ 的箭头，并在箭头旁标注概率（或”等概率”）。
• 具体示例（$2\times2$）：上面的两状态链，图如下。

  两状态对称链 (a = 0.3)           三状态"天气链"
                                  P(S|S)=0.5, P(C|S)=0.3, P(R|S)=0.2 ...
     0.7        0.7
   +----+    +----+
   |    v    v    |
  (0)            (1)              +--------- 0.5 --------+
   ^    +    ^    |               |                      |
   |    |    |    |               v                      |
   +----+    +----+              (S) --0.3--> (C) --0.2--> (R)
     0.3        0.3               ^  \       /  \        /  ^
                                  |   \     /    \      /   |
                                  |    0.2 0.6   0.3  0.3   |
                                  |     \  /        \  /    |
                                  |      v            v     |
                                  +----- 0.3 <------- 0.4 --+
                                         0.3      0.2 and 0.3

  行随机性检查:
    两状态:  行0: 0.7+0.3 = 1  ✓    行1: 0.3+0.7 = 1  ✓
    天气链:  行S: 0.5+0.3+0.2 = 1 ✓
             行C: 0.2+0.6+0.2 = 1 ✓
             行R: 0.3+0.3+0.4 = 1 ✓
  注意: 每行和为 1，但每列和不要求为 1!
    两状态链列和: 0.7+0.3 = 1.0  (这条对称链碰巧是 1，但对角线一下的
    非对称链 P'=[[0.7,0.3],[0.4,0.6]] 列和是 0.7+0.4=1.1 ≠ 1，完全正常)

$t$ 步转移概率 (t-step Transition Probability) 与 Chapman–Kolmogorov 方程

• 定义：$P^{(n)}(i,j) := \Pr[X_n = j \mid X_0 = i]$，即从 $i$ 出发走 $n$ 步后到 $j$ 的概率。
• 定理（Chapman–Kolmogorov）：$P^{(n)} = P^n$（矩阵的 $n$ 次幂）。
• 直观解释：“走 $n$ 步的概率 = 矩阵连乘 $n$ 次”。为什么？因为”从 $i$ 经中间点 $k$ 到 $j$”的概率是 $P(i,k)P(k,j)$，对所有可能的中间点 $k$ 求和，正是矩阵乘法的定义。“对所有中间状态求和”就是矩阵乘法的全部内容——这是本讲最实用的一个认识。

• 具体示例（$t$ 步转移概率）：对对称链 $P=\begin{pmatrix}1-a&a\\a&1-a\end{pmatrix}$，脚本直接乘得（$a=0.3$） \(P^2 = \begin{pmatrix} 0.58 & 0.42 \\ 0.42 & 0.58\end{pmatrix},\) 逐项核对：$P^2(0,0) = 0.7\times0.7+0.3\times0.3 = 0.49+0.09 = 0.58$ ✓；$P^2(0,1) = 0.7\times0.3+0.3\times0.7 = 0.21+0.21 = 0.42$ ✓。 此外有闭式 $P^n = \begin{pmatrix}\frac12+\frac12(1-2a)^n & \frac12-\frac12(1-2a)^n\\[2pt] \frac12-\frac12(1-2a)^n & \frac12+\frac12(1-2a)^n\end{pmatrix}$。用 $n=2$ 核对：$a=0.3$ 时 $\frac12+\frac12(0.4)^2 = 0.5+0.08 = 0.58$ ✓（与直接相乘一致）。脚本验算 $P^n(0,0)$：$n=1{:}0.700000$、$n=2{:}0.580000$、$n=3{:}0.532000$、$n=4{:}0.512800$、$n=5{:}0.505120$——清楚地向 $0.5$ 收敛。

  对非对称链 $P^{\prime}=\begin{pmatrix}0.7&0.3\\0.4&0.6\end{pmatrix}$ 则没有这个对称闭式，脚本直接乘得 \((P^{\prime})^2 = \begin{pmatrix} 0.61 & 0.39 \\ 0.52 & 0.48\end{pmatrix},\) 核对：$(P^{\prime})^2(0,0) = 0.7\times0.7+0.3\times0.4 = 0.49+0.12 = 0.61$ ✓；$(P^{\prime})^2(0,1) = 0.7\times0.3+0.3\times0.6 = 0.21+0.18 = 0.39$ ✓。把这两个 $P^2$ 放在一起对比，就能看出”对称性”带来的差别（$0.58$ vs $0.61$）——它们不是同一个矩阵。

状态的分类：可达、互通、不可约

• 可达 (Accessible)：若存在 $n\ge0$ 使 $P^n(i,j)>0$，则称 $j$ 从 $i$ 可达，记 $i\to j$。在状态图上即”存在一条从 $i$ 到 $j$ 的有向路径”。
• 互通 (Communicate)：若 $i\to j$ 且 $j\to i$，则称 $i$ 与 $j$ 互通，记 $i\leftrightarrow j$。互通是状态空间上的等价关系（自反、对称、传递），因此把状态划分成等价类 (communicating classes)。
• 不可约 (Irreducible)：若所有状态两两互通（即整个状态图是一个强连通分量），则称链不可约。
• 直观解释：不可约 = “从任何地方都能到任何地方“。它是”长期行为唯一”的关键条件：如果链卡在两个互不往来的区域里，长期比例就取决于你从哪里出发，谈不上”唯一”。
• 具体示例：上面的两状态链在 $0<a<1$ 时不可约（$0\to1$（概率 $a>0$）、$1\to0$（概率 $a>0$））；而 $a=0$ 时 $P=I$，$0\not\to1$，可约 (reducible)。

常返与瞬态 (Recurrent vs Transient)；周期与非周期 (Periodic vs Aperiodic)

• 常返 (Recurrent)：从 $i$ 出发，以概率 $1$ 无限多次回到 $i$ 的状态。
• 瞬态 (Transient)：从 $i$ 出发，只有有限多次回到 $i$ 的概率为正（即”有可能再也不回来”）的状态。有限链中，常返态等价于”访问次数期望为 $\infty$”，瞬态等价于”访问次数期望有限”。
• 周期 (Period)：对不可约链，定义 \(d(i) := \gcd\{n>0 : P^n(i,i) > 0\},\) 即”所有能回到 $i$ 的步数的最大公约数”。可以证明 $d(i)$ 与 $i$ 无关（记公共值为 $d$）。$d=1$ 时称链非周期 (aperiodic)，否则称周期为 $d$ (periodic with period $d$)。
• 直观解释：周期性的意思是”链按固定的节拍振荡”。最经典的例子是 $a=1$ 的两状态链：它每步必然切换状态，$0\to1\to0\to1\to\cdots$，所以从 $0$ 出发只能在偶数步回到 $0$，$d(0)=\gcd\{2,4,6,\dots\}=2$。这时 $\Pr[X_n=0]$ 在 $1$ 与 $0$ 之间来回跳，不收敛。
• 具体示例（周期 vs 非周期）：
  • $a=1$（周期 $2$）：$\Pr[X_n=0]$ 依次为 $1,0,1,0,1,0,\dots$（$n=0..5$，脚本验算）——振荡，不收敛。
  • $a\in(0,1)$（非周期）：$d(0)=\gcd\{1,2,3,\dots\}=1$，且 $\Pr[X_n=0]\to1/2$——收敛。
  • 天气链（三状态）：$P^2(S,S)=0.37>0$ 且 $P^3(S,S)>0$，故 $d(S)=\gcd\{2,3,\dots\}=1$，非周期 ✓。

  周期的陷阱: a = 1 的两状态链
     Pr[X_n = 0]
      1 |#   #   #   #        <- 偶数步必然在状态 0
        |   #   #   #   #
      0 +---+---+---+---+---> n
        0   1   2   3   4
     没有极限！"时间比例"却仍然存在:
       前 n 步里状态 0 出现约一半 -> 时间比例 = 1/2
     这就是"时间平均"与"分布收敛"的区别:
       定理 26.3 (时间比例):  只要不可约, 1/n*sum 1{Xm=i} -> pi(i)   [周期无所谓]
       定理 26.4 (分布收敛):  还需要非周期, Pr[Xn=i] -> pi(i)        [周期会破坏]

平稳分布 (Stationary / Invariant Distribution)

• 定义：概率向量 $\pi = (\pi(1),\dots,\pi(K))$（$\pi(i)\ge0$、$\sum_i\pi(i)=1$）若满足平衡方程组 (balance equations) \(\pi = \pi P, \quad\text{即}\quad \pi(j) = \sum_{i=1}^{K}\pi(i)P(i,j)\ \ \forall j,\) 则称 $\pi$ 为链（或 $P$）的平稳分布（不变分布，invariant distribution）。
• 直观解释（”它是什么意思？”）：$\pi$ 是”驻留比例“——链跑很久之后，处于各状态的时间比例收敛到 $\pi$。它也是”流动的平衡“：从每个状态 $i$ 流出到 $j$ 的”概率流量” $\pi(i)P(i,j)$，对所有 $i$ 求和后恰好等于流进 $j$ 的量 $\pi(j)$。类比：一个装满水的水池，各区域的水位都不再变化——不是因为没有流动，而是流入 = 流出。
• 矩阵语言：$\pi P = \pi$ 说明 $\pi$ 是 $P$ 的左特征向量、对应特征值 $1$（转置一下：$\pi$ 是 $P^T$ 对应特征值 $1$ 的右特征向量）。行随机矩阵必有特征值 $1$（因为 $P\mathbf{1}=\mathbf{1}$，故 $1$ 是 $P$ 的特征值），所以平稳分布总是存在（有限维、概率向量约束下），但不一定唯一。
• 具体示例（三状态天气链）：设 \(P = \begin{pmatrix} 0.5 & 0.3 & 0.2 \\ 0.2 & 0.6 & 0.2 \\ 0.3 & 0.3 & 0.4\end{pmatrix} \quad(S=\text{晴}, C=\text{阴}, R=\text{雨}).\) 解 $\pi P=\pi$ 与归一化条件，得 \((\pi_S,\pi_C,\pi_R) = \left(\frac{9}{28}, \frac{3}{7}, \frac14\right) = (0.321429,\ 0.428571,\ 0.250000).\) 脚本验算：$\pi P$ 的每个分量与 $\pi$ 逐位相同（误差 $<10^{-8}$）✓；用 $10^6$ 步模拟的时间比例为 $(0.32124, 0.42863, 0.25014)$ ✓。

吸收态 (Absorbing State) 与吸收马尔可夫链 (Absorbing Markov Chain)

• 定义：状态 $i$ 是吸收态，若 $P(i,i)=1$（一旦进入就永远出不来，图中是一个只有自环、没有出边的点）。若链中至少有一个吸收态，且从任何状态出发都能以正概率到达某个吸收态，则称此为吸收马尔可夫链。
• 直观解释：吸收态是”游戏结束“的状态：破产、通关、被淘汰。吸收链是可约的（吸收态无法回到其他状态），因此它的长期行为不适用平稳分布理论，而要用首步分析算”被吸收的概率”与”期望吸收时间”。
• 具体示例：赌徒破产中的 $\$0$ 与 $$M$；棋盘上的”将死”；迷宫里的出口。

首步分析 (First-Step Analysis)

• 定义：设 $h(i)$ 是”从状态 $i$ 出发、最终被某个目标集合 $A$ 吸收的概率”。则对一切 $i \notin A \cup B$（$A$ 为”成功”吸收集、$B$ 为”失败”吸收集） \(h(i) = \sum_{j} P(i,j)\,h(j), \qquad h(i) = 1 \ (i\in A), \qquad h(i) = 0\ (i\in B).\) 类似地，设 $t(i)$ 是”从 $i$ 出发被吸收所需的期望步数“，则 \(t(i) = 0\ (i\in A\cup B), \qquad t(i) = 1 + \sum_j P(i,j)\,t(j)\ (i\notin A\cup B).\)
• 直观解释：“先走一步，然后递归”。这一步之后你有几种可能（按 $P(i,j)$ 分布），进入状态 $j$ 之后问题就一模一样地重来一遍（这就是马尔可夫性质！），所以是 $h(j)$。因为已经花掉了一步，所以期望时间的方程里有个 $+1$。这是”分而治之 + 动态规划”在概率里的化身：把”从 $i$ 出发”的问题归约成”从 $j$ 出发”的更小问题。
• 为什么叫”首步”：我们只看第一步，剩下的全部打包进 $h(j)$。这就是它能变成线性方程组的原因——未知量只有 $h(\cdot)$ 本身，方程是”未知量的线性组合 = 已知常数”。
• 具体示例（两次连续正面）：反复抛公平硬币直到出现连续两次正面。状态 $S$（开始）、$T$（上次是反面）、$H$（上次是正面但还没连续两次）、$E$（成功，吸收）。$t(S)=6$（见下面的完整推导与脚本验算）。

条件期望 (Conditional Expectation)

• 定义：设 $X,Y$ 是离散随机变量。 \(\mathbb{E}[X \mid Y = y] = \sum_x x\,\Pr[X = x \mid Y = y] = \sum_x x\,\frac{\Pr[X=x, Y=y]}{\Pr[Y=y]}\quad(\Pr[Y=y]>0).\) 把 $y$ 换成随机变量 $Y$，就得到 $\mathbb{E}[X\mid Y]$——它是一个随机变量（是 $Y$ 的函数）。
• 直观解释（”它是什么意思？”）：“知道 $Y$ 之后，对 $X$ 的最优猜测”。不知道 $Y$ 时最优猜测是 $\mathbb{E}[X]$（一个数）；观测到 $Y=y$ 后，$\Pr[X=x]$ 被修正为 $\Pr[X=x\mid Y=y]$，在这个新分布下的期望就是新猜测 $\mathbb{E}[X\mid Y=y]$。所以 $\mathbb{E}[X\mid Y]$ 是”随观测值变化的最优猜测“。
  • 类比：估计一个箱子里球重量的平均值。若不知道是哪只箱子，就报全体平均 $\mathbb{E}[X]$；若知道是哪只箱子（$Y=y$），就报那只箱子的平均 $\mathbb{E}[X\mid Y=y]$。整个”按箱子取值的猜测表”就是随机变量 $\mathbb{E}[X\mid Y]$。
  • 最优性的严格表述（讲次 20）：$\mathbb{E}[X\mid Y]$ 是在所有 $Y$ 的函数 $g(Y)$ 中使均方误差 $\mathbb{E}[(X-g(Y))^2]$ 最小的那个，即 MMSE；几何上它是 $X$ 在”$Y$ 的函数构成的空间”上的正交投影。
• 具体示例：抛两枚公平硬币，$X$ = 正面数，$Y$ = 第一枚的结果（$0$ 或 $1$）。则 $\mathbb{E}[X\mid Y=0] = 0 + \tfrac12 = 0.5$，$\mathbb{E}[X\mid Y=1] = 1 + \tfrac12 = 1.5$。所以 $\mathbb{E}[X\mid Y]$ 是一个两值的随机变量：$Y=0$ 时取 $0.5$、$Y=1$ 时取 $1.5$，各以 $1/2$ 概率。注意 $\mathbb{E}\big[\mathbb{E}[X\mid Y]\big] = 0.5\cdot0.5 + 0.5\cdot1.5 = 1 = \mathbb{E}[X]$ ✓——这就是全期望公式。

全期望公式（Law of Total Expectation / Tower Property / Smoothing）

• 定义：对任意随机变量 $X,Y$（只要期望存在）， \(\mathbb{E}[X] = \sum_y \mathbb{E}[X\mid Y=y]\,\Pr[Y=y] = \mathbb{E}\big[\mathbb{E}[X\mid Y]\big].\)
• 直观解释：“分组平均再平均”。把样本按 $Y$ 的取值分成若干组，在每组内部求平均，然后按各组的”大小”（概率权重）加权，得到总体平均。类比：算全国平均身高 → 先算各省平均，再按各省人口加权。同样可以先按”第一步走到哪里”分组，这就把全期望公式与首步分析连起来了。
• 具体示例：$Y$ 均匀取 $\{1,2,3,4\}$，给定 $Y=y$ 时 $X \sim B(y,\tfrac12)$。则 $\mathbb{E}[X\mid Y=y] = y/2$，故 \(\mathbb{E}[X] = \sum_{y=1}^{4}\frac y2\cdot\frac14 = \frac{1}{4}\cdot\frac{1+2+3+4}{2} = \frac{1}{4}\cdot5 = 1.25.\) 脚本蒙特卡洛 $5\times10^5$ 次得 $1.2515$ ✓（与解析 $1.25$ 吻合）。

完整证明与推导（核心）

定理 26.1（$n$ 步分布：$\pi_n = \pi_0 P^n$）：设链的初始分布为 $\pi_0$（行向量），则 $X_n$ 的分布为 \(\pi_n = \pi_0 P^n, \quad n\ge0.\) 特别地，若 $\pi_0(i)=1$（从 $i$ 确定出发），则 $\pi_n(j) = P^n(i,j) = \Pr[X_n = j\mid X_0=i]$。

证明策略：对 $n$ 做归纳 + 用马尔可夫性质把路径概率因式分解。选择这个策略是因为”链的联合分布”天然按时间顺序条件分解（这正是马尔可夫性质给的东西），分解完再对所有中间状态求和，求和就是矩阵乘法。

逐步推导：

第 1 步（写出路径概率的因式分解）。对任意状态序列 $i_0,i_1,\dots,i_n$，用条件概率的链式法则： \(\Pr[X_0=i_0, X_1=i_1,\dots,X_n=i_n] = \Pr[X_0=i_0]\prod_{k=1}^{n}\Pr[X_k=i_k \mid X_0=i_0,\dots,X_{k-1}=i_{k-1}].\) 由马尔可夫性质，每个条件概率只需看前一项： \(= \pi_0(i_0)\,P(i_0,i_1)\,P(i_1,i_2)\cdots P(i_{n-1},i_n).\)

第 2 步（边缘化到 $X_n$）。对所有 $i_0,\dots,i_{n-1}$ 求和（$i_n$ 固定）： \(\Pr[X_n = i_n] = \sum_{i_0,\dots,i_{n-1}} \pi_0(i_0)P(i_0,i_1)\cdots P(i_{n-1},i_n).\)

第 3 步（认出这是矩阵乘法）。最强的做法是对 $n$ 归纳。

• 基础情形 $n=1$： \(\pi_1(j) = \Pr[X_1 = j] = \sum_{i}\Pr[X_0=i]\Pr[X_1=j\mid X_0=i] = \sum_i \pi_0(i)P(i,j) = (\pi_0 P)(j).\ ✓\)
• 归纳步骤：设 $\pi_n = \pi_0 P^n$。则 \(\pi_{n+1}(j) = \Pr[X_{n+1}=j] = \sum_i \Pr[X_n=i]\Pr[X_{n+1}=j\mid X_n=i] = \sum_i \pi_n(i)P(i,j) = (\pi_n P)(j) = (\pi_0P^{n+1})(j).\) 关键：第二个等号处用到马尔可夫性质——$\Pr[X_{n+1}=j\mid X_n=i]$ 与更早的历史无关，所以只要知道 $X_n$ 的边缘分布就能算 $X_{n+1}$ 的分布。这就是”马尔可夫链的分布演化完全由当前分布决定” 的含义。

第 4 步（结论）：由归纳原理，$\pi_n = \pi_0P^n$ 对一切 $n\ge0$ 成立。取 $\pi_0 = e_i$（第 $i$ 个单位向量，即从 $i$ 确定出发），得 $\pi_n(j) = (e_iP^n)(j) = P^n(i,j)$ ✓。

第 5 步（脚本验算）。两状态对称链 $a=0.3$（$P=\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}$）：$\pi_0 = (\tfrac12,\tfrac12)$ 时 $\pi_n$ 恒为 $(\tfrac12,\tfrac12)$（因为它是平稳分布）；$\pi_0 = (1,0)$ 时 \(\pi_1 = (0.7, 0.3),\ \pi_2 = (0.58, 0.42),\ \pi_3 = (0.532, 0.468),\ \pi_4 = (0.5128, 0.4872),\ \pi_5 = (0.50512, 0.49488).\) 与 $\frac12+\frac12(1-2a)^n = 0.5+0.5\cdot0.4^n$ 逐个一致（$0.70, 0.58, 0.532, 0.5128, 0.50512$ ✓）。收敛速度由 $\vert 1-2a\vert $ 决定：$a=0.1$ 时 $\vert 1-2a\vert =0.8$，$n=10$ 误差 $5.37\times10^{-2}$、$n=50$ 误差 $7.14\times10^{-6}$；$a=0.49$ 时 $\vert 1-2a\vert =0.02$，$n=10$ 误差已是 $5.12\times10^{-18}$（几乎瞬间混合）；$a=0.01$ 时 $\vert 1-2a\vert =0.98$，$n=50$ 误差仍高达 $0.182$（混合极慢）。

【证明机制解说】：证明的”灵光一现”是把路径概率拆成”初始分布 × 一串转移概率”，然后对所有中间状态求和。而”对所有中间状态求和”这个操作恰好就是矩阵乘法的定义，所以概率问题自动翻译成矩阵代数。请注意第 3 步归纳中用到马尔可夫性质的方式：我们不需要知道 $X_n$ 从哪里来，只需要知道它在哪。若过程有记忆（例如 $X_{n+1}$ 依赖 $X_n$ 和 $X_{n-1}$），$\pi_{n+1}$ 就无法由 $\pi_n$ 单独确定，整个矩阵框架会立刻崩溃。这也是建模时”状态必须包含所有相关历史”的原因。

定理 26.2（平稳分布的不动点刻画）：$\pi_n = \pi_0$ 对一切 $n\ge0$ 成立 $\iff$ $\pi_0$ 是平稳分布（即 $\pi_0 P = \pi_0$）。

证明策略：双向蕴含的直接证明。

逐步推导：

第 1 步（$\Rightarrow$）。若 $\pi_n=\pi_0$ 对一切 $n\ge0$，则特别地 $\pi_1 = \pi_0$。而由定理 26.1，$\pi_1 = \pi_0 P$，故 $\pi_0P = \pi_0$，即 $\pi_0$ 满足平衡方程，是平稳分布。

第 2 步（$\Leftarrow$）。设 $\pi_0P=\pi_0$。则 $\pi_1 = \pi_0P = \pi_0$。再用归纳：若 $\pi_n=\pi_0$，则 \(\pi_{n+1} = \pi_nP = \pi_0P = \pi_0.\) 由归纳原理，$\pi_n=\pi_0$ 对一切 $n\ge0$ 成立。

【证明机制解说】：这条定理把”分布不随时间变化“翻译成了”$\pi$ 是 $P$ 的特征值 $1$ 的左特征向量“。所以”求平稳分布”就是”求特征值 $1$ 的特征向量（再归一化）“——一个纯粹的线性代数问题。注意”平稳”不是说链不动（它可能每步都在跳），而是说分布不动：流出的量与流入的量恰好平衡。

定理 26.3（不可约有限链的时间比例收敛与平稳分布的唯一性）：设有限马尔可夫链不可约、转移矩阵 $P$。则对任意初始分布 $\pi_0$，存在唯一的平稳分布 $\pi$，且对每个状态 $i$ \(\lim_{n\to\infty}\frac1n\sum_{m=0}^{n-1}\mathbf{1}\{X_m = i\} = \pi(i),\) 这个极限以概率 $1$ 成立（也依概率成立）。

证明策略：用”返回时间”给平稳分布一个构造性定义，再用大数定律（讲次 23）把时间比例算出来，最后验证它满足平衡方程。严格的完整证明（含耦合论证）超出本课范围，但下面给出五个步骤的完整论证骨架——它是”直觉上为什么成立”的最清楚的路径。

逐步推导：

第 1 步（用返回时间构造 $\pi$）。固定状态 $i$，设 $\pi_0(i)=1$（从 $i$ 出发），令 $T(i)$ 为首次返回 $i$ 所需步数（$T(i)\ge1$）。定义 \(\pi(i) := \frac{1}{\mathbb{E}[T(i)]}.\) 直观：访问 $i$ 的间隔平均是 $\mathbb{E}[T(i)]$ 步，长程来看”平均每 $\mathbb{E}[T(i)]$ 步访问一次 $i$”，所以时间比例是 $1/\mathbb{E}[T(i)]$。脚本验证（天气链）：$\mathbb{E}[T(S)] = 1/\pi_S = 28/9 = 3.111111$（模拟 $3.1084$ ✓）、$\mathbb{E}[T(C)] = 7/3 = 2.333333$（模拟 $2.3316$ ✓）、$\mathbb{E}[T(R)] = 4$（模拟 $3.9894$ ✓）。

第 2 步（所有状态都常返）。有限链中至少有一个状态常返（若全为瞬态，则总访问次数有限，但链有无穷多步，矛盾）。设 $i$ 常返。对任意其他状态 $j$，由不可约性，从 $i$ 出发有正概率 $p>0$ 在返回 $i$ 之前先访问 $j$（否则从 $i$ 永远到不了 $j$）。每次访问 $i$ 都独立地以概率 $p$ 触发一次”访问 $j$”（马尔可夫性质！），而 $i$ 被访问无限多次，故 $j$ 也被访问无限多次——所有状态都常返。类比：以 $p>0$ 的概率抛正面抛无限多次，必然见到无限多个正面（讲次 19 的几何分布/Borel–Cantelli 直觉）。

第 3 步（时间比例 = $1/\mathbb{E}[T(i)]$）。设 $T_1, T_2, T_3,\dots$ 是连续访问 $i$ 之间的间隔。由马尔可夫性质，每次进入 $i$ 后过程”重新开始”，故 $T_1,T_2,\dots$ 独立同分布。由（强）大数定律（讲次 23）， \(\frac{T_1+\cdots+T_k}{k} \longrightarrow \mathbb{E}[T_1] \quad\text{（依概率）}\implies \frac{k}{T_1+\cdots+T_k}\longrightarrow \frac{1}{\mathbb{E}[T_1]} = \pi(i).\) 左端的含义正是”到第 $k$ 次访问为止的访问频率 $\approx$ 时间比例”。

第 4 步（$\pi(i)>0$ 且时间比例之和为 $1$）。时间比例非负、加起来必须等于 $1$（因为链总在某个状态），故不可能所有 $\pi(i)$ 都为 $0$，即至少有一个 $\pi(i)>0$。再由第 2 步的论证（”访问 $i$ 无限多次 $\Rightarrow$ 访问每个 $j$ 无限多次”），$\pi(j)>0$ 对一切 $j$ 成立。

第 5 步（$\pi$ 满足平衡方程）。链在长 $n$ 步中访问 $j$ 大约 $n\pi(j)$ 次。设 $i$ 是某个状态。每次访问 $j$ 之后有概率 $P(j,i)$ 紧接着访问 $i$，所以”先 $j$ 后 $i$”这种相邻对出现约 $n\pi(j)P(j,i)$ 次。而”在 $i$ 的访问”总次数等于”任意 $j$ 之后紧接着 $i$”的次数之和： \(n\pi(i) \approx \sum_{j} n\pi(j)P(j,i) \implies \pi(i) = \sum_j \pi(j)P(j,i),\) 即 $\pi=\pi P$。平衡方程证明完毕。

第 6 步（唯一性）。设 $\nu$ 是另一个平稳分布，取 $\pi_0=\nu$。则 $\Pr[X_n=i]=\nu(i)$ 对一切 $n$ 恒成立，故时间比例序列 $\frac1n\sum_m\mathbf{1}\{X_m=i\}$ 的期望恒为 $\nu(i)$。由第 3 步该序列收敛到 $\pi(i)$，而”收敛 + 有界（取值在 $[0,1]$）”蕴含期望也收敛到 $\pi(i)$（严谨论证：对任意 $\epsilon>0$，当 $n$ 充分大时 $\Pr[\vert Y_n-\pi(i)\vert \le\epsilon]\ge1-\epsilon$，于是 $\mathbb{E}[\vert Y_n-\pi(i)\vert ]\le\epsilon(1-\epsilon)+\epsilon\le2\epsilon$，再对一切 $m\ge n$ 成立），故 $\nu(i)=\pi(i)$。平稳分布唯一。

【证明机制解说】：这条定理最深刻的地方是“平稳分布 = 访问频率 = $1/\mathbb{E}[\text{返回时间}]$” 这个三重等价。它把”代数对象 $\pi$”（特征向量）与”概率对象”（时间比例）与”几何对象”（返回时间的倒数）打通了。注意本定理只要求不可约，不要求非周期——时间比例对周期链照样收敛（因为”分摊到长期”把振荡抹平了）。这正是下面定理 26.4 与非周期的分水岭。

定理 26.4（非周期链的分布收敛）：设有限链不可约、非周期（即某个状态的周期为 $1$，由定理 26.3 的讨论知所有状态的周期都为 $1$）。则 \(\Pr[X_n = i] \longrightarrow \pi(i) \quad\text{对一切 } i,\ \text{当 } n\to\infty,\) 其中 $\pi$ 是唯一的平稳分布。

证明策略：耦合论证 (coupling argument)——构造两条独立的链，一条从平稳分布 $\pi$ 出发、一条从任意初始分布 $\pi_0$ 出发，证明它们在有限时间内以概率 $1$ “相遇”，相遇之后”粘在一起”（couple）走。于是从 $\pi_0$ 出发的那条链的分布最终与从 $\pi$ 出发的相同，即趋于 $\pi$。

逐步推导：

第 1 步（周期为 $1$ 蕴含”最终连续可达”）。令 $S(i) = \{n>0 : P^n(i,i)>0\}$。若 $\gcd S(i)=1$，则可证存在整数 $n(i)$ 使得 $\{n(i), n(i)+1, n(i)+2,\dots\}\subseteq S(i)$（即”从某个时刻起，每个步数都能回到 $i$”）。理由：$\gcd S(i)=1$ 时存在 $a,b\in S(i)$ 且 $\gcd\{a,b\}=1$；用扩展欧几里得（讲次 5）得整数 $m,n$ 使 $ma+nb=1$；取 $k=m^-a+n^-b$，则 $k$ 与 $k+1$ 都在 $S(i)$；于是任何 $n\ge k^2$ 都可以写成 $n = (a^{\prime}-b^{\prime})k + b^{\prime}(k+1)$（$b^{\prime}\in\{0,\dots,k-1\}$）的形式，从而 $n\in S(i)$。

• 具体示例：天气链的状态 $E$（借用官方例子）满足 $S(E)=\{4,5,6,\dots\}$，$n(E)=4$。脚本对天气链验证：$P^n(S,S)>0$ 对一切 $n\ge2$ 成立。

第 2 步（所有状态的周期都是 $1$）。设 $d(i)=1$。对任意 $j$，由不可约性存在 $a$ 步 $j\to i$ 与 $b$ 步 $i\to j$。于是从 $j$ 出发可走 $a+n(i)+b$ 步回到 $j$，也可以走 $a+n(i)+1+b$ 步回到 $j$（先 $j\to i$、再 $i\to i$ 走 $n(i)$ 或 $n(i)+1$ 步、再 $i\to j$）。两个连续整数都在 $S(j)$ 里，故 $\gcd S(j) \mid 1$，即 $d(j)=1$。

第 3 步（存在统一的”汇合时刻”）。固定状态 $i$。对每个 $j$ 由不可约性存在 $m(j,i)$ 使 $P^{m(j,i)}(j,i)>0$。由第 1 步，$P^n(j,j)>0$ 对一切 $n\ge n(j)$。故对 $n \ge n(j)+m(j,i)$， \(P^n(j,i) \ge P^{n - m(j,i)}(j,j)\cdot P^{m(j,i)}(j,i) > 0.\) 取 $k := \max_j\{n(j)+m(j,i)\}$，则从任何状态 $j$ 出发，走恰好 $k$ 步到达 $i$ 的概率都严格为正。记这个概率的下界为 $p := \min_j P^k(j,i) > 0$。

第 4 步（两条独立链在 $k$ 步后以概率 $\ge p$ 相遇）。设 $X_n$ 从 $\pi$ 出发（于是 $\Pr[X_n=i]=\pi(i)$ 对一切 $n$）、$Z_n$ 从任意 $\pi_0$ 出发，两条链独立。则

（更精细的做法：把 $Z$ 的初始分布分解到各状态，用 $\min_j P^k(j,i)\ge p$。）总之，在时刻 $k$，”两条链都在 $i$”有正概率。若没遇上，再过 $k$ 步又有一个独立的正概率 $p$，如此反复：设 $\tau = \min\{n\ge0 : X_n = Z_n\}$，则 \(\Pr[\tau > km]\le(1-p)^m \longrightarrow 0 \quad (m\to\infty).\) 所以它们几乎必然在有限时间内相遇。

第 5 步（粘合）。定义第三条链 \(Y_n := \begin{cases} Z_n, & n < \tau,\\ X_n, & n \ge \tau.\end{cases}\) 即”跟着 $Z$ 走，直到撞上 $X$，之后就永远贴着 $X$ 走“。由马尔可夫性质与强马尔可夫性，$Y_n$ 仍然是转移矩阵为 $P$、初始分布为 $\pi_0$ 的马尔可夫链（在 $\tau$ 时刻 $Y_\tau = X_\tau$，从那里往后复制 $X$ 的走向，因为 $X$ 本身是 $P$-链）。

第 6 步（收尾）。因为 $\Pr[X_n\ne Y_n]=\Pr[\tau>n]\to0$，故对任意 $i$， \(\vert \Pr[X_n=i] - \Pr[Y_n=i]\vert \le \Pr[X_n\ne Y_n] \longrightarrow 0.\) 而 $\Pr[X_n=i]=\pi(i)$ 对一切 $n$ 成立（$X$ 从平稳分布出发），故 $\Pr[Y_n=i]\to\pi(i)$。但 $Y_n$ 与 $Z_n$ 同分布（同一个 $P$、同一个 $\pi_0$），所以 $\Pr[Z_n=i]\to\pi(i)$。这对任意初始分布 $\pi_0$ 成立，定理得证。

【证明机制解说】：耦合论证的”灵光一现”是让两条独立的链赛跑，然后强行把它们粘起来。这解决了两个技术困难：(i) 直接比较 $\pi_0P^n$ 与 $\pi$ 需要控制矩阵幂的收敛，很难；(ii) 耦合把”分布收敛”变成”两条轨道相遇的概率“，而后者只需一个下界 $p>0$ 加上反复尝试。注意哪里用到了非周期：第 1 步需要”从某个时刻起每一步都能回到 $i$”，这正是 $d(i)=1$ 给的。若 $d=2$（如 $a=1$ 的两状态链），从 $0$ 到 $0$ 只能在偶数步，两条链在奇偶相位不同时永远不能同时落在 $i$，耦合失败——这就是周期链 $\Pr[X_n=i]$ 不收敛的机制。

反例（周期性破坏收敛）：取两状态链 $a=1$，即 $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$。它不可约（$0\leftrightarrow1$）、有唯一平稳分布 $\pi=(\tfrac12,\tfrac12)$（脚本验算 $\pi P=\pi$ ✓），时间比例也收敛到 $\tfrac12$。但取 $\pi_0=(1,0)$，则 $\Pr[X_n=0]$ 依次为 $1,0,1,0,1,0,\dots$，永不收敛（脚本验算 $n=0..5$ 得到 $1,0,1,0,1,0$）。所以定理 26.4 的”非周期”条件不可删——这是”不可约 + 有唯一平稳分布”还不够的一个漂亮反例。

反例（可约链平稳分布不唯一）：取 $P = \begin{pmatrix}0.5&0.5&0\\0.5&0.5&0\\0&0&1\end{pmatrix}$（状态 $\{1,2,3\}$）。状态 $3$ 吸收，$\{1,2\}$ 是一个闭的互通类，$1,2$ 到不了 $3$、$3$ 也到不了 $1,2$，故链可约。于是 \(\pi^{(1)}=\left(\tfrac12,\tfrac12,0\right),\qquad \pi^{(2)}=(0,0,1)\) 都是平稳分布，而且它们的任意凸组合 $\pi = t\pi^{(1)}+(1-t)\pi^{(2)}$（$t\in[0,1]$）也都是平稳分布——无穷多个。脚本验算：$\pi^{(1)}P=\pi^{(1)}$ ✓、$\pi^{(2)}P=\pi^{(2)}$ ✓、$(0.3,0.3,0.4)P = (0.3,0.3,0.4)$ ✓。这说明”不可约”是”平稳分布唯一”的必要条件。 直观上，从 $1$ 出发你永远到不了 $3$，长期时间比例是 $(1/2,1/2,0)$；从 $3$ 出发是 $(0,0,1)$——长期行为依赖初始条件，谈不上唯一。

定理 26.5（首步分析：吸收概率）：设 $A,B\subseteq\mathcal{X}$ 不交，$h(i)$ 为”从 $i$ 出发、在进入 $B$ 之前先进入 $A$ 的概率”。则 $h$ 是下述线性方程组的唯一解： \(h(i) = 1\ (i\in A),\qquad h(i)=0\ (i\in B),\qquad h(i)=\sum_{j\in\mathcal{X}}P(i,j)h(j)\ (i\notin A\cup B).\)

证明策略：全期望公式 + 马尔可夫性质。选择这个策略是因为”第一步走到哪里”给出了一个天然的分组（partition）：事件”先从 $A$ 而非 $B$ 被吸收”可以按第一步的去向 $j$ 分成互不相交的若干份，于是全期望/全概率公式直接可用。

逐步推导：

第 1 步（边界条件）。若 $i\in A$，则在”进入 $A$ 之前先进入 $A$”是必然事件（已经在了），故 $h(i)=1$。若 $i\in B$，同理 $h(i)=0$。

第 2 步（按第一步分组）。对 $i\notin A\cup B$，设事件 $E_i$ = “从 $i$ 出发先进入 $A$ 而非 $B$”。按第一步落点 $j$ 做划分：$\{X_1=j\}$ 两两不交、并起来是整个样本空间（因为链一定要走一步到某处）。由全概率公式， \(h(i) = \Pr[E_i] = \sum_{j\in\mathcal{X}}\Pr[E_i \mid X_1=j]\cdot\Pr[X_1=j] = \sum_j \Pr[E_i\mid X_1=j]\,P(i,j).\)

第 3 步（用马尔可夫性质化简条件概率）。关键一步：给定 $X_1 = j$，”从 $i$ 出发先进入 $A$”这件事与 $X_0=i$ 无关，等价于”从 $j$ 出发先进入 $A$”。形式化地： \(\Pr[E_i\mid X_1=j] = \Pr[E_j] = h(j).\) 依据：马尔可夫性质说”给定现在，未来与过去独立”；而已知 $X_1=j$ 时”未来是否先撞 $A$”完全由从 $j$ 出发的演化决定。这正是”首步分析”这个名字的由来：只看第一步，其余打包成 $h(j)$。

第 4 步（合并）： \(h(i) = \sum_j P(i,j)h(j), \quad i\notin A\cup B.\)

第 5 步（唯一性）。这是一个 $\vert \mathcal{X}\setminus(A\cup B)\vert $ 个未知量的线性方程组。在吸收链中，从每个非吸收态出发以正概率到达吸收态（即”瞬态”部分没有闭的互通类），可以证明该方程组的系数矩阵 $I - Q$（$Q$ 为限制在非吸收态上的子矩阵）可逆，因为 $\sum_{m\ge0}Q^m = (I-Q)^{-1}$ 收敛（$Q^m\to0$，瞬态部分最终会离开）。故解唯一，即 $h$ 被完全确定。

第 6 步（完整算例：赌徒破产 Gambler’s Ruin）。赌徒从 $\$m$ 出发，每局以概率 $p$ 赢 $$1$、以概率 $q=1-p$ 输 $\$1$，直到资金达到 $0$（破产）或 $M$（成功）。状态 $n\in{0,1,\dots,M}$，$0$ 与 $M$ 吸收。设 $\alpha(n)$ = “从 $n$ 出发最终赢到 $M$ 而非输光”的概率，则 \(\alpha(n) = q\,\alpha(n-1) + p\,\alpha(n+1)\ (0<n<M), \qquad \alpha(0)=0,\quad \alpha(M)=1.\) 解这个递推（用特征方程法）：

• 试探解 $\alpha(n)=\lambda^n$（无常数项时递推是齐次的）。代入得 $\lambda^n = q\lambda^{n-1}+p\lambda^{n+1}$，两边除 $\lambda^{n-1}$：$\lambda = q + p\lambda^2$，即 $p\lambda^2-\lambda+q=0$。用求根公式， \(\lambda = \frac{1\pm\sqrt{1-4pq}}{2p}.\) 因为 $4pq = 4p(1-p)$，而 $1-4p+4p^2 = (1-2p)^2$，所以 $\sqrt{1-4pq} = \sqrt{(1-2p)^2} = \vert 1-2p\vert $。在 $p<1/2$ 的常见情形下 $1-2p>0$，故 $\sqrt{1-4pq} = 1-2p$，两个根分别是 \(\lambda_1 = \frac{1-(1-2p)}{2p} = \frac{2p}{2p} = 1, \qquad \lambda_2 = \frac{1+(1-2p)}{2p} = \frac{2-2p}{2p} = \frac{1-p}{p} = \frac qp.\) 即 \(\lambda_1 = 1, \qquad \lambda_2 = \rho := \frac{q}{p}.\) 快速自检：两根之积应为 $q/p = \rho$（韦达定理，常数项/首项系数），而 $1\cdot\rho = \rho$ ✓；两根之和应为 $1/p$，而 $1+\frac qp = \frac{p+q}{p} = \frac1p$ ✓。
• 通解 $\alpha(n) = a + b\rho^n$。代入边界条件： \(\alpha(0) = a + b = 0 \implies b = -a;\qquad \alpha(M) = a + b\rho^M = 1 \implies a(1-\rho^M) = 1 \implies a = \frac{1}{1-\rho^M}.\)
• 故 \(\boxed{\ \alpha(n) = \frac{1-\rho^n}{1-\rho^M},\qquad \rho = \frac{q}{p}\ (p\ne q).\ }\)
• $p=q=1/2$ 的情形：此时 $\rho=1$，上面的公式是 $0/0$。回到递推 $\alpha(n) = \frac12\alpha(n-1)+\frac12\alpha(n+1)$，即 $\alpha(n+1)-\alpha(n) = \alpha(n)-\alpha(n-1)$：差分为常数，故 $\alpha$ 是线性的，配上边界条件得 $\alpha(n) = n/M$。
• 脚本验算（$p=0.4$，$\rho=1.5$，$M=5$）：公式给出 $\alpha(0)=0$、$\alpha(1)=0.075829$、$\alpha(2)=0.189573$、$\alpha(3)=0.360190$、$\alpha(4)=0.616114$、$\alpha(5)=1$；直接解线性方程组（Gauss 消元）得到完全相同的六个数 ✓；且递推自检 $q\alpha(n-1)+p\alpha(n+1)$ 对 $n=1,2,3,4$ 逐项复现 $\alpha(n)$ ✓。公平情形 $p=q=0.5$ 同样验算：$n/M = 0,0.2,0.4,0.6,0.8,1$，与直接解方程一致 ✓；蒙特卡洛 $3\times10^5$ 次实验从 $n=2$ 出发，实测胜率 $0.3998$（理论 $0.4$）✓。
• 赌场的算例（官方数值，脚本验算）：$p=0.48$、$M=100$、起始 $\$10$： \(\alpha(10) = \frac{1-\rho^{10}}{1-\rho^{100}},\qquad \rho = \frac{0.52}{0.48} = \frac{13}{12} \approx 1.083333.\) 脚本得 $\alpha(10)\approx4.0983\times10^{-4}$。于是赌场对每位这样的赌客的期望收益是 \((1-4.1\times10^{-4})\times\$10 - 4.1\\times10^{-4}\\times\\$990 \approx \$9.60.\) 对比”一局定胜负”的赌客：赌场期望收益只有 $0.52\times\$10-0.48\times$10 = \$0.40$。“不推你的运气 (don^{\prime}t push your luck)”的含义在这里：赌徒因为”想多赢”而把本金反复暴露在 $48\%$ 的劣势下，反而把赌场的期望收益从 $$0.40$ 放大到 $\$9.60$——玩得越久，劣势的累积越致命。这也说明小概率的大收益（$4\times10^{-4}$ 概率赢 $$990$）无法弥补高概率的小损失，因为 $0.9996\times10 \gg 4\times10^{-4}\times990$。

【证明机制解说】：首步分析的”灵光一现”是第 3 步：Pr[E_i \| X_1 = j] = h(j)。这一步把”从 $i$ 出发的整个未来”替换成”从 $j$ 出发的同一个问题”——这正是马尔可夫性质的内容（未来只依赖现在 $X_1=j$，不依赖过去 $X_0=i$）。剩下的一切都是线性代数。请注意两个常见错误：(i) 漏掉边界条件：不代入 $\alpha(0)=0,\alpha(M)=1$ 就只能得到”带两个自由常数的通解”，无法定出 $\alpha$；(ii) 误以为 $n$ 很大时能用稳态代替：这是吸收链，没有平稳分布（可约！），必须解方程。

反例（漏掉边界条件的后果）：仍以赌徒破产为例。若忘记 $\alpha(0)=0$、$\alpha(M)=1$，只拿到通解 $\alpha(n) = a+b\rho^n$。此时若错误的”对称性论证”给出 $\alpha(n) = n/M$（只在 $p=1/2$ 时才对），在 $p=0.4$ 时会得到 $\alpha(2)=0.4$，而正确值是 $0.189573$——错了一倍多。再看极端情形：$p=0.4$、$M=100$ 时 $\alpha(10) = 4.1\times10^{-4}$，而”线性猜测” $\alpha(10)=0.1$，差了 244 倍。边界条件承载了全部的非线性信息，绝不能丢。

定理 26.6（首步分析：期望吸收时间）：设 $t(i)$ 为从 $i$ 出发到进入吸收集 $A$ 的期望步数。则 \(t(i) = 0\ (i\in A),\qquad t(i) = 1 + \sum_{j}P(i,j)\,t(j)\ (i\notin A).\)

证明策略：全期望公式（把期望按第一步分组）+ 线性性。选择这个策略的理由：期望的线性性让”已经走了一步”与”剩下的期望步数”可以直接相加。

逐步推导：

第 1 步（边界）。$i\in A$ 时已经到达，需 $0$ 步，故 $t(i)=0$。

第 2 步（按第一步分组）。设 $T_i$ 为从 $i$ 出发到进入 $A$ 的步数。则 $T_i = 1 + T_{X_1}$（走一步到 $X_1$，再走 $T_{X_1}$ 步）。用全期望公式按 $X_1$ 分组： \(t(i) = \mathbb{E}[T_i] = \mathbb{E}\big[1 + T_{X_1}\big] = 1 + \sum_j \Pr[X_1=j]\cdot\mathbb{E}[T_{X_1}\mid X_1=j] = 1 + \sum_j P(i,j)t(j).\) 关键：$\mathbb{E}[T_{X_1}\mid X_1=j] = t(j)$，又是马尔可夫性质。

第 3 步（完整算例 A：五状态链的命中时间）。考虑下面的五状态链（网页浏览模型的变体，状态 $A,B,C,D,E$）： \(P = \begin{pmatrix} 0 & 1/2 & 0 & 1/2 & 0\\ 0&0&1&0&0\\ 1&0&0&0&0\\ 1/3&1/3&0&0&1/3\\ 0&1/2&1/2&0&0 \end{pmatrix}.\) 设 $\beta(i)$ 为从 $i$ 出发首次到达 $E$ 的期望步数。首步方程为 \(\beta(A) = 1 + \tfrac12\beta(B)+\tfrac12\beta(D),\quad \beta(B) = 1+\beta(C),\quad \beta(C)=1+\beta(A),\) \(\beta(D) = 1+\tfrac13\beta(A)+\tfrac13\beta(B)+\tfrac13\beta(E),\quad \beta(E)=0.\) 逐步求解（代入消元，手动可追踪）：

• 由第三式 $\beta(C) = 1+\beta(A)$；代入第二式：$\beta(B) = 1 + (1+\beta(A)) = 2+\beta(A)$。
• 代入第四式：$\beta(D) = 1 + \tfrac13\beta(A) + \tfrac13(2+\beta(A)) + 0 = 1+\tfrac23+\tfrac13\beta(A)+\tfrac13\beta(A) = \tfrac53+\tfrac23\beta(A)$。
• 代入第一式： \(\beta(A) = 1 + \tfrac12(2+\beta(A)) + \tfrac12\left(\tfrac53+\tfrac23\beta(A)\right) = 1 + 1 + \tfrac12\beta(A) + \tfrac56 + \tfrac13\beta(A) = \tfrac{17}{6} + \tfrac56\beta(A).\) 故 $\beta(A) - \tfrac56\beta(A) = \tfrac16\beta(A) = \tfrac{17}{6}$，得 $\beta(A) = 17$。
• 回代：$\beta(B) = 19$、$\beta(C) = 18$、$\beta(D) = \tfrac53+\tfrac{34}{3} = 13$、$\beta(E)=0$。
• 脚本验算：把 $\beta=(17,19,18,13,0)$ 代回五条方程，逐条精确成立 ✓。蒙特卡洛模拟 $2\times10^5$ 次（从各状态出发）：$\beta(A)=17.0297$、$\beta(B)=19.0260$、$\beta(C)=18.0219$、$\beta(D)=13.0948$ ✓。
• 注意直觉核对：$\beta(C)=18 > \beta(B)=19$？不对——$\beta(B)=19$ 确实大于 $\beta(C)=18$，因为 $B$ 必须先走到 $C$ 再走 $\beta(C)$ 步，多一步。同理 $\beta(C)=18 \approx \beta(A)+1 = 18$ ✓，$\beta(B)=19 = \beta(C)+1$ ✓。这些”差一步”的关系是检验解是否合理的快速方法。

第 4 步（完整算例 B：两次连续正面）。反复抛公平硬币直到出现 $HH$。状态 $S$（开始）、$T$（上次反面）、$H$（上次正面、还没连两个）、$E$（成功）。转移：$S\to T$ 或 $H$（各 $1/2$）；$T\to T$ 或 $H$（各 $1/2$）；$H\to T$ 或 $E$（各 $1/2$）；$E\to E$。首步方程： \(\beta(S) = 1+\tfrac12\beta(T)+\tfrac12\beta(H),\quad \beta(T) = 1+\tfrac12\beta(T)+\tfrac12\beta(H),\) \(\beta(H) = 1+\tfrac12\beta(T)+\tfrac12\beta(E),\quad \beta(E)=0.\) 注意 $\beta(S)=\beta(T)$（两者的转移分布完全相同，首步方程一样）。故设 $\beta(T)=x$、$\beta(H)=y$： \(x = 1+\tfrac12x+\tfrac12y \implies \tfrac12x - \tfrac12y = 1 \implies x - y = 2.\) \(y = 1+\tfrac12x \implies y = 1+\tfrac12x.\) 代入：$x - (1+\tfrac12x) = 2 \implies \tfrac12x = 3 \implies x = 6$，$y = 1+3 = 4$。故 $\beta(T)=6$、$\beta(S)=6$、$\beta(H)=4$、$\beta(E)=0$。

• 脚本验算：代入逐条成立 ✓；蒙特卡洛 $5\times10^5$ 次实测平均步数 $5.9999$（理论 $6$）✓。
• 直觉核对：$\beta(H)=4 < \beta(T)=6$ 合理——已经在”上次是正面”时更接近成功。$\beta(S)=6=\beta(T)$ 也合理——第一步总要抛一次，把 $S$ 变成 $T$ 或 $H$。

第 5 步（完整算例 C：掷骰子直到相邻两次和为 8）。状态 $S$（开始）、$1,\dots,6$（上次掷出的点数）、$E$（成功，相邻两次和为 $8$）。若在状态 $i$ 且下一次掷出 $j$ 使得 $i+j=8$，则进入 $E$；否则新状态是 $j$。首步方程： \(\beta(S) = 1+\frac16\sum_{i=1}^{6}\beta(i),\qquad \beta(i) = 1+\sum_{j:\ i+j\ne8}\frac16\beta(j).\) 由对称性（$\beta(2)=\cdots=\beta(6)$？不成立！），要小心。由对称性，只有 $1$ 是特殊的（因为 $1+7=8$ 但 $7$ 不是骰子面，所以从状态 $1$ 出发永远不可能在下一次就成功）。其余 $2,\dots,6$ 各自都有一个”致命”的对手点数（$6,5,4,3,2$），结构完全相同，故 $\beta(2)=\cdots=\beta(6)=:\gamma$。又 $\beta(1)=\beta(S)$（从状态 $1$ 出发，下一次掷出 $j$ 之后的新状态就是 $j$，与从 $S$ 出发一样；而 $1$ 不可能立刻成功）。 于是方程化为两个未知量： \(\beta(S) = 1+\frac16\big[\beta(S)+5\gamma\big] = 1+\frac16\beta(S)+\frac56\gamma,\) \(\gamma = 1+\frac16\big[\beta(S)+4\gamma\big] = 1+\frac16\beta(S)+\frac23\gamma.\)

• 第一式：$\tfrac56\beta(S) = 1+\tfrac56\gamma \implies \beta(S) = \tfrac65+\gamma$。
• 第二式：$\tfrac13\gamma = 1+\tfrac16\beta(S) \implies \gamma = 3+\tfrac12\beta(S)$。
• 代入：$\gamma = 3+\tfrac12(\tfrac65+\gamma) = 3+\tfrac35+\tfrac12\gamma = \tfrac{18}{5}+\tfrac12\gamma \implies \tfrac12\gamma = \tfrac{18}{5} \implies \gamma = \tfrac{36}{5} = 7.2$。
• 于是 $\beta(S) = \tfrac65+\tfrac{36}{5} = \tfrac{42}{5} = 8.4$。
• 脚本验算：$\gamma=7.2$、$\beta(S)=8.4$，代回两条方程精确成立 ✓；蒙特卡洛 $5\times10^5$ 次实测 $8.3990$（理论 $8.4$）✓。

第 6 步（完整算例 D：梯子问题）。20 级梯子，从地面（第 $0$ 级）出发，每步以概率 $p$ 上升一级、以概率 $1-p$ 摔回地面。设 $\beta(i)$ 为从第 $i$ 级到顶端（第 $20$ 级）的期望步数： \(\beta(i) = 1+(1-p)\beta(0)+p\,\beta(i+1),\quad i=0,\dots,19;\qquad \beta(20)=0.\) 解法（差分方程）：试探 $\beta(i) = a + b\lambda^i$。代入并匹配系数：

• 常数部分：$a = 1+(1-p)(a+b)+pa$，整理得 $b = -(1-p)^{-1}$（因为 $(1-p)b + 1 = 0$）。
• 指数部分：$\lambda^i = p\lambda^{i+1} \implies \lambda = p^{-1}$。 故 $\beta(i) = a - (1-p)^{-1}p^{-i}$。用边界条件 $\beta(20)=0$ 定出 $a = (1-p)^{-1}p^{-20}$，所以 \(\boxed{\ \beta(i) = \frac{p^{-20}-p^{-i}}{1-p}\ },\qquad \beta(0) = \frac{p^{-20}-1}{1-p}.\)
• 脚本验算：$p=0.9$ 时 $\beta(0) = \frac{0.9^{-20}-1}{0.1} = 72.2526$（官方给 $\approx72$ ✓）；$p=0.8$ 时 $\beta(0) = 428.6809$（官方给 $\approx429$ ✓）；顺带 $p=0.95$ 时 $\beta(0) = 35.7902$。
• 注意这个结果有多恐怖：成功率从 $0.9$ 降到 $0.8$（只降 $10\%$），期望步数从 $72$ 涨到 $429$（涨了近 $6$ 倍）。原因是 $p^{-20}$ 对 $p$ 极度敏感：$(0.8)^{-20}/(0.9)^{-20} = (0.9/0.8)^{20} = 1.125^{20}\approx 10.5$。这是”高成功率系统的鲁棒性”的定量教训：单步可靠性上的一点点退步会在需要连续成功的任务上被指数放大。相比之下，”一口气爬上”的概率是 $p^{20} = 0.9^{20} = 0.1216$（$p=0.9$）与 $0.8^{20}=0.0115$（$p=0.8$）——差 $10.5$ 倍，与期望步数的放大倍数一致。
• 另一面：为什么摔回地面的惩罚这么严重？因为 $\beta(0)$ 出现在每一条方程里（$20$ 个方程）——一次失手就归零，这让状态 $0$ 成为”超级吸收陷阱”。若改成”每次后退一级”（更温和的惩罚），期望步数会是 $\Theta(n^2/p)$ 量级（随机游走），而不是指数级。

第 7 步（完整算例 E：赌徒破产的期望时间）。对同一个赌徒问题，设 $\beta(n)$ 为从 $\$n$ 出发到”达到 $0$ 或 $M$”的期望步数： \(\beta(n) = 1+q\beta(n-1)+p\beta(n+1)\ (0<n<M),\qquad \beta(0)=\beta(M)=0.\) 解法要点（非齐次线性递推）：先找一个特解，再加齐次通解。试探 $\beta(n) = \alpha n$：代入得 $\alpha n = 1+\alpha n - \alpha + 2p\alpha$，故需 $1-\alpha+2p\alpha = 0$，即 $\alpha = (1-2p)^{-1}$，特解 $\beta_{\text{part}}(n) = n(1-2p)^{-1}$。齐次方程 $\beta(n)=q\beta(n-1)+p\beta(n+1)$ 的两个解是 $\beta=1$ 与 $\beta=\rho^n$（$\rho=q/p$，与吸收概率的推导同一特征方程）。故 \(\beta(n) = \frac{n}{1-2p} + a + b\rho^n.\)

• 边界 $\beta(0)=0$ 给 $a+b=0$，即 $b=-a$。
• 边界 $\beta(M)=0$ 给 $\frac{M}{1-2p}+a(1-\rho^M)=0$，即 $a = -\frac{M(1-2p)^{-1}}{1-\rho^M}$。
• 故 \(\boxed{\ \beta(n) = \frac{n}{1-2p} - \frac{M}{1-2p}\cdot\frac{1-\rho^n}{1-\rho^M}\ },\qquad \rho=\frac qp.\)
• $p=1/2$ 的极限：$1-2p=0$ 使公式发散，需重新解。此时递推为 $\beta(n) = 1+\frac12\beta(n-1)+\frac12\beta(n+1)$，即二阶差分 $\beta(n+1)-2\beta(n)+\beta(n-1) = -2$，故 $\beta$ 是凹二次函数。配上边界条件 $\beta(n) = n(M-n)$。
• 脚本验算（$p=0.4$，$M=5$）：公式给 $\beta = (0, 3.104265, 5.260664, 5.995261, 4.597156, 0)$；直接解 6 元线性方程组（Gauss 消元）逐位一致 ✓。公平情形 $p=0.5$：公式 $n(M-n)$ 给 $(0,4,6,6,4,0)$，与直接解方程一致 ✓；蒙特卡洛 $3\times10^5$ 次从 $n=2$ 出发实测 $5.9977$（理论 $6$）✓。
• 直觉核对：$p=0.4$（劣势）时 $\beta(2)=5.26 < \beta(3)=6.00$——从 $\$3$ 出发反而要等更久？这看起来反直觉，其实合理：从 $$3$ 出发时，离 $M=5$ 只差 $2$ 步、离破产差 $3$ 步，但因为劣势，它有较大概率先”往下漂”到 $2,1$ 甚至破产（较快结束），也有较小概率慢慢往上爬到 $5$（较慢）。在两个吸收态之间，期望时间不是单调的：它由”最快的吸收路径”主导，而不是”距离”。对称情形 $p=0.5$ 时 $\beta(n)=n(M-n)$ 在两端为 $0$、中间最大，形状是抛物线 ✓。

【证明机制解说】：这五个算例展示了同一套机械流程：

1. 识别状态（含”上次结果”这类记忆压缩成的状态，如 $T/H$、上次点数）；
2. 写首步方程（对每个非吸收态写一行，右边是”$1$（时间）或 $0$（概率）$+\sum_j P(i,j)(\cdot)$”）；
3. 利用对称性降维（骰子例把 $6$ 个未知量降成 $2$ 个；两次正面例把 $4$ 个降成 $2$ 个）；
4. 代入消元或差分方程求解；
5. 回代验算每条原方程。 最关键的是第 1 步：马尔可夫链的建模难点从来不是解方程，而是选对状态。第 5 步（骰子例）之所以需要”上次点数”作为状态，是因为”相邻两次和为 $8$”依赖历史；第 4 步（两次正面）需要区分”上次是 $T$ 还是 $H$”；而”已经连续多少个正面”只用到 $2$ 个，因为到 $2$ 个就终止了。状态空间就是”记忆的压缩表示”，多一个维度会让方程数爆炸，少一个维度会让马尔可夫性质失效。

定理 26.7（全期望公式 Law of Total Expectation）：设 $X,Y$ 离散随机变量，$\mathbb{E}[\vert X\vert ]<\infty$。则 \(\mathbb{E}[X] = \sum_y \mathbb{E}[X\mid Y=y]\,\Pr[Y=y] = \mathbb{E}\big[\mathbb{E}[X\mid Y]\big].\)

证明策略：直接证明——把 $\mathbb{E}[X\mid Y=y]$ 的定义代入，交换求和次序，再用全概率公式（或直接看出内层求和等于 $\Pr[X=x]$）。选择这个策略是因为它只用到定义，名副其实的”一行证明”。

逐步推导：

第 1 步（写出定义）： \(\mathbb{E}[X\mid Y=y] = \sum_x x\,\Pr[X=x\mid Y=y] = \sum_x x\,\frac{\Pr[X=x,Y=y]}{\Pr[Y=y]}.\)

第 2 步（代入右边并化简）： \(\sum_y \mathbb{E}[X\mid Y=y]\Pr[Y=y] = \sum_y \left(\sum_x x\frac{\Pr[X=x,Y=y]}{\Pr[Y=y]}\right)\Pr[Y=y] = \sum_y\sum_x x\,\Pr[X=x,Y=y].\)

第 3 步（交换求和次序，用 Fubini/Tonelli）： \(\sum_y\sum_x x\,\Pr[X=x,Y=y] = \sum_x x\sum_y \Pr[X=x,Y=y].\) 这一步需要绝对收敛：由 $\mathbb{E}[\vert X\vert ]=\sum_x\vert x\vert \Pr[X=x]<\infty$，对 $y$ 求和是绝对收敛的（更直接地，$\sum_y\sum_x\vert x\vert \Pr[X=x,Y=y] = \mathbb{E}\vert X\vert <\infty$）。这就是定理里”$\mathbb{E}[\vert X\vert ]<\infty$”这一条件的用处。

第 4 步（认出边缘分布）： \(\sum_y\Pr[X=x,Y=y] = \Pr[X=x] \quad\text{（边缘化 / 全概率公式）}.\)

第 5 步（收尾）： \(\sum_x x\,\Pr[X=x] = \mathbb{E}[X].\ \blacksquare\)

第 6 步（等价的”塔性质”形式）。$\mathbb{E}[X\mid Y]$ 是 $Y$ 的函数，记 $g(Y) := \mathbb{E}[X\mid Y]$。则 \(\mathbb{E}[g(Y)] = \sum_y g(y)\Pr[Y=y] = \sum_y\mathbb{E}[X\mid Y=y]\Pr[Y=y] = \mathbb{E}[X].\) 即 $\mathbb{E}\big[\mathbb{E}[X\mid Y]\big]=\mathbb{E}[X]$——这叫塔性质 (tower property)，或平滑性 (smoothing)。它也可以迭代：$\mathbb{E}\big[\mathbb{E}[X\mid Y,Z]\big\vert Y\big] = \mathbb{E}[X\mid Y]$（对更粗的信息取条件，会”抹平”细节）。

【证明机制解说】：这个证明的全部内容就是”分组加权平均 = 总体平均“。技术要点只有两个：一是交换求和次序需要绝对收敛（这就是那个有限期望条件），二是内层求和认出边缘分布。请注意这条公式的威力：它把”算一个复杂期望”分解成”先固定 $Y$，在条件世界内算期望（通常简单），再对 $Y$ 加权平均“。首步分析（定理 26.5、26.6）就是取 $Y=X_1$（第一步的落点）的特例——所以首步方程 $t(i)=1+\sum_j P(i,j)t(j)$ 中的那个求和，正是全期望公式里的 $\sum_j\Pr[X_1=j]\mathbb{E}[T_i\mid X_1=j]$。

定理 26.8（条件期望的基本性质）：设 $X,Y,Y_1,Y_2$ 是随机变量，$a_1,a_2\in\mathbb{R}$，$h$ 是任意函数。

• (a) 线性性：$\mathbb{E}[a_1Y_1+a_2Y_2\mid X] = a_1\mathbb{E}[Y_1\mid X]+a_2\mathbb{E}[Y_2\mid X]$。
• (b) 取出已知量 (factoring known values)：$\mathbb{E}[h(X)\,Y\mid X] = h(X)\,\mathbb{E}[Y\mid X]$。
• (c) 平滑性：$\mathbb{E}\big[\mathbb{E}[Y\mid X]\big] = \mathbb{E}[Y]$（即定理 26.7）。
• (d) 独立性：若 $Y$ 与 $X$ 独立，则 $\mathbb{E}[Y\mid X] = \mathbb{E}[Y]$（右边是常数）。

证明策略：用条件期望的定义直接验证 (a)、(b)（逐点对每个 $X=x$ 验证）；(c) 已在定理 26.7 证明；(d) 把独立性代入条件概率定义。另一种更漂亮的证法（讲次 20 用的）是正交投影刻画：$\mathbb{E}[Y\mid X]$ 是 $Y$ 在”$X$ 的函数空间”上的正交投影，即对一切 $\phi$ 有 $\mathbb{E}\big[(Y-\mathbb{E}[Y\mid X])\phi(X)\big]=0$；由这个刻画可以一行证明 (a) 与 (b)。

逐步推导（用定义逐点验证）：

(a) 固定 $x$ 且 $\Pr[X=x]>0$。条件分布本身是概率分布，故它对 $Y$ 的期望满足线性性（讲次 20 的期望线性性）： \(\mathbb{E}[a_1Y_1+a_2Y_2\mid X=x] = a_1\mathbb{E}[Y_1\mid X=x]+a_2\mathbb{E}[Y_2\mid X=x].\) 因这对每个 $x$ 成立，作为 $X$ 的函数逐点相等，故随机变量相等。

(b) 固定 $x$。由于 $h(x)$ 在此条件世界里是常数， \(\mathbb{E}[h(X)Y\mid X=x] = h(x)\,\mathbb{E}[Y\mid X=x].\) 逐点成立，故 $\mathbb{E}[h(X)Y\mid X]=h(X)\mathbb{E}[Y\mid X]$。直观：在已知 $X=x$ 的世界里，$h(X)=h(x)$ 是”已知的”，可以当作常数提出来。

(c) 定理 26.7。

(d) 固定 $x$。若 $Y\perp X$，则 $\Pr[Y=y\mid X=x]=\Pr[Y=y]$，故 \(\mathbb{E}[Y\mid X=x] = \sum_y y\Pr[Y=y\mid X=x] = \sum_y y\Pr[Y=y] = \mathbb{E}[Y].\) 与 $x$ 无关，故 $\mathbb{E}[Y\mid X]=\mathbb{E}[Y]$（常数）。

脚本／数值算例（官方原题的完整演算）：设 $X,Y,Z$ i.i.d.，均值 $1/2$、二阶矩 $1/3$（例如 $U[0,1]$）。求 $\mathbb{E}[(Y+2X)^2\mid X]$。

逐步展开（每步都标注依据）： \(\mathbb{E}[(Y+2X)^2\mid X] = \mathbb{E}\big[Y^2+4X^2+4XY \mid X\big]\) \(= \mathbb{E}[Y^2\mid X] + 4\,\mathbb{E}[X^2\mid X] + 4\,\mathbb{E}[XY\mid X] \quad\text{（(a) 线性性）}\) \(= \mathbb{E}[Y^2] + 4X^2 + 4X\,\mathbb{E}[Y\mid X] \quad\text{（(d) 独立 + (b) 取出已知量）}\) \(= \mathbb{E}[Y^2] + 4X^2 + 4X\,\mathbb{E}[Y] \quad\text{（(d) 再用一次独立性）}\) \(= \frac13 + 4X^2 + 2X \quad\text{（代入 }\mathbb{E}[Y^2]=1/3,\ \mathbb{E}[Y]=1/2\text{）}.\)

• 注意这个答案是一个随机变量（$X$ 的函数），这正是条件期望的本质。
• 一致性检验（塔性质）：$\mathbb{E}\big[\frac13+4X^2+2X\big] = \frac13+4\cdot\frac13+2\cdot\frac12 = \frac13+\frac43+1 = \frac83 \approx 2.666667$。脚本对 $X,Y\sim U[0,1]$ 直接蒙特卡洛算 $\mathbb{E}[(Y+2X)^2]$：$2.6655$ ✓（吻合）。
• 为什么不能”直接算”：$Z := (Y+2X)^2$ 关于 $X$ 的条件分布很难写出来（$Z$ 是 $Y$ 与 $X$ 的混合），所以 $\sum_z z\Pr[Z=z\mid X=x]$ 这条路几乎走不通。而用性质 (a)(b)(d) 只需要矩信息（$\mathbb{E}[Y]$、$\mathbb{E}[Y^2]$），完全绕开了条件分布。这是条件期望性质的最大价值。

脚本／数值算例（对称性技巧）：设 $X,Y,Z$ i.i.d.，证明 \(\mathbb{E}[Y \mid Y+X+Z] = \frac13(Y+X+Z).\)

• 推导：由 $X,Y,Z$ 完全对称（交换任意两个不改变联合分布），条件期望 $\mathbb{E}[Y\mid S]$、$\mathbb{E}[X\mid S]$、$\mathbb{E}[Z\mid S]$（其中 $S := Y+X+Z$）三者必须相等（因为它们在业务上扮演完全相同的角色）。记公共值为 $V$。则由线性性， \(3V = \mathbb{E}[Y\mid S]+\mathbb{E}[X\mid S]+\mathbb{E}[Z\mid S] = \mathbb{E}[Y+X+Z\mid S] = \mathbb{E}[S\mid S] = S.\) 故 $V = S/3$。
• 数值／逻辑核对：$\mathbb{E}\big[\frac{Y+X+Z}{3}\big] = \frac13(\mathbb{E}Y+\mathbb{E}X+\mathbb{E}Z) = \mathbb{E}[Y]$（由线性性），与塔性质一致 ✓。
• 注意这个证明的美妙之处：它完全不需要知道 $X,Y,Z$ 的具体分布！只要”i.i.d. + 矩存在”就够。这是对称性论证的典范：当问题在某个置换群下不变时，对称的未知量必然相等，一条方程就解出全部。

脚本／数值算例（优惠券收集器，呼应讲次 20）：有 $n$ 种优惠券，每次随机独立地抽到一种，求集齐全部 $n$ 种所需的期望次数 $\mathbb{E}[T]$。

• 条件期望解法（分而治之）：设已经收集到 $k$ 种，记 $T_k$ 为”从 $k$ 种到 $k+1$ 种”所需次数。抽一次落在已有的 $k$ 种里的概率是 $k/n$，落在新种类的概率是 $1-k/n = (n-k)/n$。所以 $T_k \sim G\!\big(\frac{n-k}{n}\big)$（几何分布，讲次 19），故 \(\mathbb{E}[T_k] = \frac{1}{(n-k)/n} = \frac{n}{n-k}.\)
• 由线性性（这是关键：不需要 $T_k$ 之间独立！它们确实不独立，但线性性不需要）， \(\mathbb{E}[T] = \sum_{k=0}^{n-1}\mathbb{E}[T_k] = \sum_{k=0}^{n-1}\frac{n}{n-k} = n\sum_{j=1}^{n}\frac1j = n\,H_n.\)
• 脚本验算：$n=6$ 时 $\mathbb{E}[T]=6H_6 = 6\times2.45 = 14.7$，蒙特卡洛 $2\times10^5$ 次实测 $14.7222$ ✓；$n=20$ 时 $20H_{20} = 71.954793$，实测 $72.0133$ ✓；$n=3$ 时 $3H_3 = 5.5$；$n=10$ 时 $10H_{10}=29.289683$。
• 这里的”条件期望”体现在哪：$\mathbb{E}[T_k]=n/(n-k)$ 本身就是”给定当前已收集 $k$ 种”这个条件下的期望（条件世界里的几何分布），而总期望靠线性性相加。注意 $T_k$ 之间不独立（收集到哪些种类会影响后续），但线性性照样可用——这是”条件期望 + 线性性”组合拳的典型。

脚本／数值算例（随机和 Random Sum）：设 $N$ 是取非负整数的随机变量，$Y_1,Y_2,\dots$ i.i.d. 且与 $N$ 独立，$X = \sum_{i=1}^{N}Y_i$（$N=0$ 时 $X=0$）。则 \(\mathbb{E}[X] = \mathbb{E}[N]\,\mathbb{E}[Y_1].\)

证明：用全期望公式，按 $N$ 分组： \(\mathbb{E}[X] = \sum_{n\ge0}\mathbb{E}[X\mid N=n]\Pr[N=n] = \sum_{n\ge0}\mathbb{E}\left[\sum_{i=1}^{n}Y_i\right]\Pr[N=n] = \sum_{n\ge0} n\,\mathbb{E}[Y_1]\Pr[N=n] = \mathbb{E}[Y_1]\sum_{n\ge0}n\Pr[N=n] = \mathbb{E}[Y_1]\mathbb{E}[N].\) 这里 $\mathbb{E}[\sum_{i=1}^n Y_i]=n\mathbb{E}[Y_1]$ 用期望线性性（不需要 $Y_i$ 独立，但求和项数 $n$ 是固定的常数，所以是有限和，线性性直接可用）。

脚本验算：取 $N\sim\mathrm{Poisson}(3)$（$\mathbb{E}[N]=3$），$Y_i\sim\mathrm{Exp}(1)$（$\mathbb{E}[Y_i]=1$）。则 $\mathbb{E}[X]=3\times1=3$。蒙特卡洛 $4\times10^5$ 次实测 $2.9987$ ✓。另一个：$N\sim\mathrm{Poisson}(2)$，$Y\sim\mathrm{Exp}(1)$，则 $\mathbb{E}[X]=2$，实测 $2.0034$ ✓。

脚本／数值算例（几何分布的期望，用首步/条件期望）：$Y\sim G(p)$（首次成功所需次数）。用首步分析：$h$ = 从”还没成功”状态到成功的期望步数， \(h = 1 + (1-p)h + p\cdot0 \implies ph = 1 \implies h = \frac1p.\) 脚本验算（$p=0.3$）：$1/p = 3.333333$，蒙特卡洛 $4\times10^5$ 次实测 $3.3324$ ✓。这与讲次 19 用求和 $\sum_{k\ge1}k(1-p)^{k-1}p$ 得到的结果一致，而首步法只用一行。这正是首步分析的价值：它把”无穷级数求和”换成”一元一次方程”。

反例（两条性质容易混淆：$\mathbb{E}[XY\mid X] = X\mathbb{E}[Y\mid X]$ 而非 $X\mathbb{E}[Y]$）：若 $Y$ 与 $X$ 不独立，则 $\mathbb{E}[Y\mid X]$ 是 $X$ 的函数、会随 $X$ 变化，不能替换成常数 $\mathbb{E}[Y]$。具体数值：设 $X\sim U[0,1]$，给定 $X=x$ 时 $Y\sim U[0,x]$。则 $\mathbb{E}[Y\mid X] = X/2\ne 1/4 = \mathbb{E}[Y]$。若误用 $\mathbb{E}[Y]=1/4$ 去算 $\mathbb{E}[XY\mid X]$，会得到 $X/4$；而正确结果是 $X\cdot(X/2) = X^2/2$。两者在 $X=1$ 处差 $2$ 倍。记忆口诀：(b) 只允许把”$X$ 的函数”提出来；”$Y$ 的期望”只有在独立时才能变成常数（性质 (d)）。

与经典问题的联系

（1）PageRank：把网页图变成随机游走。 这是马尔可夫链最重要的现代应用。问题实际背景：如何给网页排序？数学建模：把网页看作状态、把链接看作有向边，浏览者从当前页等概率地点击出链之一，这就是一个马尔可夫链。方案设计：解平衡方程 $\pi P=\pi$、$\sum_i\pi_i=1$，得到的 $\pi$ 就是PageRank——”长期来看浏览者停留在各页面的时间比例”。正确性证明：由定理 26.3，只要链不可约（网页图强连通）就有唯一平稳分布，且时间比例收敛到它。实际修正：真实网页图不强连通（有悬挂节点、有孤立子图），所以 Google 的原始做法是加”阻尼/随机跳转 (damping / teleportation)“：以概率 $\alpha\approx0.85$ 跟随链接、以 $1-\alpha$ 等概率跳到任意网页。修正后的矩阵 $P^{\prime} = \alpha P + (1-\alpha)\frac1K\mathbf{1}\mathbf{1}^T$ 使所有元素严格为正，从而一定不可约且非周期（因为 $P^{\prime}(i,i)>0$ 对一切 $i$），唯一平稳分布与收敛性都得到保证。这个技巧体现了”用数学假设去补救模型缺陷”的工程智慧。

官方的小例子（五状态网页浏览链，脚本验算）：把上面的五状态链看作网页 $A,\dots,E$，平衡方程的解是 \((\pi_A,\pi_B,\pi_C,\pi_D,\pi_E) = \frac{1}{39}(12,9,10,6,2) = (0.307692,\ 0.230769,\ 0.256410,\ 0.153846,\ 0.051282).\) 脚本验算：$\pi P$ 逐位等于 $\pi$（两边同乘 $39$ 后是 $12,9,10,6,2$，完全一致）✓；$\sum\pi_i=1$ ✓；用 $P^{200}$ 的第 $0$ 行做幂迭代，得到 $(0.30769231,0.23076923,0.25641026,0.15384615,0.05128205)$，乘 $39$ 后正好是 $(12,9,10,6,2)$ ✓。排名是 $A,C,B,D,E$——这正是 “PageRank 可以用解平衡方程来确定”的完整演示。

（2）赌徒破产与风险管理的数学化。 背景：赌场游戏（或保险、投资、工程冗余设计）。建模：随机游走 + 两个吸收壁。方案：解首步方程得 $\alpha(n) = \frac{1-\rho^n}{1-\rho^M}$、$\beta(n) = \frac{n}{1-2p}-\frac{M}{1-2p}\cdot\frac{1-\rho^n}{1-\rho^M}$。结论：即使每局胜率是 $48\%$（只差 $2$ 个百分点），起始 $\$10$ 想赢到 $$100$ 的概率只有 $4.1\times10^{-4}$。这给出了一条可迁移的工程洞见：在”负漂移 + 吸收壁”的系统中，延长博弈时间会指数级放大劣势。同一数学模型直接用于：(i) 保险精算（保险公司的资金 = 带正漂移的随机游走，破产概率的估计）；(ii) 冗余系统的可靠性（每个冗余单元是”一次博弈”）；(iii) A/B 测试与赌博式决策的对比（”一次大注”vs”多次小注”的期望损失）。脚本验算的赌场数字：$\alpha(10)\approx4.0983\times10^{-4}$，单客期望收益 $\$9.60$（对比一局定胜负的 $$0.40$）。

（3）算法分析：哈希/随机游走中的命中时间与覆盖时间。 背景：随机图上的搜索、覆盖问题。建模：随机游走在图上（如 $d$ 维超立方体、$d$-正则图）。结论：不可约 + 非周期 + 平稳分布 $\pi$ 的链上，”从 $i$ 到 $j$ 的期望命中时间”与”返回时间”有定量关系（$\mathbb{E}[\text{返回 }i] = 1/\pi(i)$，脚本对天气链验证：$1/\pi = (3.111111, 2.333333, 4.000000)$，模拟 $(3.1084, 2.3316, 3.9894)$ ✓）。“混合时间 (mixing time)” 则是 $\Pr[X_n=i]$ 收敛到 $\pi(i)$ 的速度，由 $\vert 1-2a\vert $ 这类”第二大特征值”控制（脚本：$a=0.49$ 时 $n=10$ 误差已达 $5\times10^{-18}$，而 $a=0.01$ 时 $n=50$ 误差还有 $0.182$）。这直接决定了随机算法的采样代价。

（4）首步分析与动态规划。 背景：任意”带随机性的决策/终止问题”。联系：首步方程 $h(i)=\sum_j P(i,j)h(j)$ 与动态规划的 Bellman 方程在形式上完全一致——”当前值 = 立即回报 + 折扣后的未来期望值”（本讲的链无折扣，但把 $P$ 换成 $\gamma P$ 就得到折扣情形）。因此本讲的方法直接迁移到马尔可夫决策过程 (MDP) 与强化学习。

（5）可靠性工程：系统失效时间。 背景：一个系统由若干部件组成，部件独立地随机失效。建模：系统状态 = “哪些部件还完好”。方案：在状态图上标出”失效状态”，用首步方程求平均失效时间 (MTTF)。两部件串联/并联的简单情形：串联系统任一部件失效即失效，期望寿命可解析；并联系统需全部失效才失效，期望寿命由部件的失效分布（若为指数分布，讲次 24 的无记忆性让状态转移变得马尔可夫！）决定。这解释了为什么”指数寿命 + 马尔可夫链”是可靠性分析的标准组合。

与其他讲次的关联

• 讲次 15–19（概率公理 → 随机变量 → 离散分布）：本讲的状态转移概率 $P(i,j)$ 本质上是条件概率（讲次 17），马尔可夫性质是用条件概率语言陈述的；初始分布 $\pi_0$ 就是讲次 19 的 PMF；首步分析里的几何分布期望 $1/p$（两次正面前的等待、几何例子）直接引用讲次 19 的结论；本讲的算例”两次连续正面”的 $\beta(S)=6$ 可以通过讲次 19 的几何分布来交叉验证（期望 $1/p$ 的串联）。
• 讲次 20（期望与线性性 Expectations & Linearity）：全期望公式（定理 26.7）的证明只用到期望的定义与 Fubini 换序；而”分而治之”的另一半武器——期望线性性——在每一条首步分析算例中都被反复使用（例如 $\beta(A)=1+\frac12\beta(B)+\frac12\beta(D)$ 中把”1 步”与”后续期望”相加，靠的是线性性）。优惠券收集器用一个”线性性 + 条件期望”的组合拳解决，正是讲次 20 主题的延伸。
• 讲次 21（联合分布与独立性 Joint Distributions & Independence of RVs）：条件期望 $\mathbb{E}[X\mid Y]$ 的定义需要联合分布 $\Pr[X=x,Y=y]$ 与条件分布 $\Pr[X=x\mid Y=y]$，这些概念完全来自讲次 21；性质 (d)（独立时 $\mathbb{E}[Y\mid X]=\mathbb{E}[Y]$）就是讲次 21 独立性定义的直接推论。
• 讲次 22（方差与协方差 Variance & Covariance）：本讲的期望分析（平均步数）由讲次 22 的方差视角补全；更重要的是讲次 22 的 $\operatorname{Var}(X+Y)$ 公式与首步分析结合可以给出”吸收时间的方差”（在首步方程两侧再取一次条件期望即可，得到 $\mathbb{E}[T^2]$ 的方程组）。
• 讲次 23（集中不等式 Concentration Inequalities）：定理 26.3 与定理 26.4 的证明中，第 3 步”用大数定律把时间平均”直接引用讲次 23 的（强）大数定律；”访问无限多次”的论证本质是 Borel–Cantelli 型论证，与讲次 23 的切尔诺夫界/Law of Large Numbers 是同一思想家族。本讲是把讲次 23 的极限定理用在”相关序列”（马尔可夫链）上的第一个例子。
• 讲次 24（连续概率与分布 Continuous Probability & Distributions）：讲次 24 定理 24.4 的无记忆性与”指数分布是几何分布的连续极限”在本讲的马尔可夫性质那里找到了解释——无记忆性正是”迈入状态后重新开始”。若把本讲的时间离散改为连续、并把停留时间取为指数分布，就得到连续时间马尔可夫链 (CTMC)；讲次 24 的指数分布是它的必要构件。
• 讲次 25（高斯分布与中心极限定理 Gaussian Distribution & CLT）：本讲只给出了时间比例 $\frac1n\sum_m\mathbf{1}\{X_m=i\}$ 的LLN 型收敛（定理 26.3）；CLT 型的精细化结论（$\sqrt n$ 尺度上的正态波动，即马尔可夫链的中心极限定理）需要讲次 25 的工具。而在定理 26.3 第 6 步的唯一性论证中，”收敛 + 有界 $\Rightarrow$ 期望收敛”的论证用的是讲次 23 的极限论证。
• 讲次 5（欧几里得、费马小定理、中国剩余定理 Euclid, FLT, CRT）：定理 26.4 第 1 步”$\gcd S(i)=1$ 蕴含某个时刻后全部步数可达”的证明恰恰使用了扩展欧几里得算法（把 $1$ 写成 $ma+nb$，从而由 $a,b\in S(i)$ 构造两个连续可达步数）。这是数论工具在概率论里的漂亮出场。
• 讲次 4（模运算 Modular Arithmetic）与讲次 9–10（图论 Graphs）：马尔可夫链的状态转移图就是讲次 9–10 的有向图，”不可约 $\iff$ 状态图是单个强连通分量”直接把概率问题翻译成图论的连通性问题；周期性 $d(i)=\gcd\{n:P^n(i,i)>0\}$ 与图上的”回路长度的 gcd”是同一个概念。
• 讲次 18（独立性与事件组合 Independence & Combination of Events）：在零概率事件（如 $P^n(i,i)=0$ 的”永不返回”）的处理上需要谨慎；而”访问 $j$ 无限多次”的论证（每次访问 $i$ 独立地以概率 $p$ 触发）用到了事件独立性的直觉，这正是讲次 18 的主题。

关键要点

1. 马尔可夫性质 = 无记忆性：$\Pr[X_{n+1}=j\mid X_n=i,X_{n-1},\dots,X_0] = P(i,j)$。未来只依赖现在。建模的第一难点是选对状态（要把所有相关历史压缩进状态，例如”上次的点数”“是否已连续两次正面”）。
2. $P$ 是行随机矩阵：$P_{ij}\ge0$、$\sum_j P_{ij}=1$（每行和为 $1$；列和不必为 $1$）。$n$ 步转移概率由矩阵幂给出：Chapman–Kolmogorov 方程 $P^{(n)} = P^n$，$n$ 步分布 $\pi_n=\pi_0P^n$。
3. 平稳分布 $\pi$ 由平衡方程刻画：$\pi=\pi P$（$\pi$ 是 $P$ 对应特征值 $1$ 的左特征向量），且 $\sum_i\pi_i=1$。$\pi$ 的三重身份：特征向量 / 长期时间比例 / $1/\mathbb{E}[\text{返回时间}]$。
4. 平稳分布唯一性的条件：不可约 保证存在且唯一（定理 26.3），且时间比例从任意初始分布都收敛到它。非周期是”$\Pr[X_n=i]$ 本身收敛”（定理 26.4）所额外需要的。可约链可以有无穷多个平稳分布（例：$P=\begin{pmatrix}1&0\\0&1\end{pmatrix}$ 时任意分布都平稳）。
5. 首步分析 = 全期望公式 + 马尔可夫性质：吸收概率 $h(i)=\sum_j P(i,j)h(j)$（非吸收态），边界 $h(A)=1$、$h(B)=0$；期望时间 $t(i)=1+\sum_j P(i,j)t(j)$，边界 $t(\text{吸收})=0$。永远别忘了边界条件——它们承载了全部的非线性信息。
6. 赌徒破产的两个闭式公式（$0<n<M$，$\rho=q/p$）：
   • 达到 $M$ 的概率：$\alpha(n) = \dfrac{1-\rho^n}{1-\rho^M}$（$p\ne q$），$\alpha(n)=\dfrac nM$（$p=q$）。
   • 期望步数：$\beta(n) = \dfrac{n}{1-2p} - \dfrac{M}{1-2p}\cdot\dfrac{1-\rho^n}{1-\rho^M}$（$p\ne q$），$\beta(n)=n(M-n)$（$p=q$）。
7. 全期望公式（塔性质）：$\mathbb{E}[X] = \sum_y\mathbb{E}[X\mid Y=y]\Pr[Y=y] = \mathbb{E}\big[\mathbb{E}[X\mid Y]\big]$，条件是 $\mathbb{E}[\vert X\vert ]<\infty$（保证可换序）。它是”分而治之”的引擎：先固定 $Y$ 算条件期望（通常简单），再对 $Y$ 加权平均。首步分析就是取 $Y=X_1$ 的特例。
8. 条件期望的四条性质：线性性、取出已知量 $\mathbb{E}[h(X)Y\mid X]=h(X)\mathbb{E}[Y\mid X]$、平滑性 $\mathbb{E}[\mathbb{E}[Y\mid X]]=\mathbb{E}[Y]$、独立性 $\mathbb{E}[Y\mid X]=\mathbb{E}[Y]$。注意 $\mathbb{E}[X\mid Y]$ 是随机变量，不是数。
9. 对称性论证：i.i.d. 的 $X,Y,Z$ 满足 $\mathbb{E}[Y\mid X+Y+Z]=\frac13(X+Y+Z)$——只需一步”三者条件期望相等 + 线性性”，不需要知道具体分布。

常见误区与注意事项

1. 把状态选错，导致马尔可夫性质失效。 例如”数一堆硬币里正面个数”的同时想知道”是否连续两次正面”——那就必须把”上次结果”放进状态。又如国际象棋：“棋子的位置”不是马尔可夫状态（还要知道”这个兵/车是否动过”用于易位），必须用完整局面。判据：如果两个不同的历史在同一个”状态”下会导致不同的未来分布，那这个”状态”就不是马尔可夫状态。
2. 混淆”行随机”与”列随机”。 $P$ 的每一行和为 $1$（从 $i$ 出发必须去某处）。列和一般不是 $1$（两状态链的列和是 $1.1$，完全正常）。相应地，初始分布 $\pi_0$ 是行向量、$\pi_n=\pi_0P^n$（左乘），而平衡方程是 $\pi=\pi P$（也是左乘）。把 $\pi$ 写成列向量去算 $\pi = P\pi$ 会得到”$P$ 的右特征向量”，那是另一个对象（对应列随机的矩阵）。
3. 以为”不可约 + 有唯一平稳分布”就足以保证 $\Pr[X_n=i]$ 收敛。 $a=1$ 的两状态链 $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ 不可约、有唯一平稳分布 $(\frac12,\frac12)$，但 $\Pr[X_n=0]$ 是 $1,0,1,0,\dots$ 振荡不收敛（脚本验算 $n=0..5$）。必须加上非周期。区分清楚两条定理：时间比例收敛只要不可约（定理 26.3）；分布本身收敛还要非周期（定理 26.4）。
4. 平静稳分布当成”唯一”的。 可约链可以有无穷多个平稳分布。反例：$P=\begin{pmatrix}1&0\\0&1\end{pmatrix}$（任意分布都平稳）；$P=\begin{pmatrix}0.5&0.5&0\\0.5&0.5&0\\0&0&1\end{pmatrix}$（$(\frac12,\frac12,0)$、$(0,0,1)$ 及其任意凸组合都平稳，脚本验算全部通过）。只有在不可约时，平稳分布才唯一。
5. 写首步方程时漏掉边界条件或漏掉那个 $+1$。 漏边界：赌徒破产会退化成”$\alpha(n)=n/M$”这种只在公平硬币下成立的错误答案（$p=0.4$、$M=100$、$n=10$ 时真值 $4.1\times10^{-4}$，线性猜测 $0.1$，错 $244$ 倍）。漏 $+1$：期望时间方程必须有 $+1$（已经走了一步），而期望概率方程不能有 $+1$。记忆口诀：时间 +1，概率不加。
6. 在吸收链上套用”平稳分布”。 吸收链是可约的（吸收态出不去），它的长期行为不是”收敛到平稳分布”，而是”以某个概率落到某个吸收态”。此时只能用首步分析。从一个吸收链的转移矩阵强行解 $\pi P=\pi$ 会得到不唯一甚至误导的结果（例如全都落在吸收态上）。
7. 把条件期望当成常数（或把 $\mathbb{E}[Y\mid X]$ 写成 $\mathbb{E}[Y]$）。 $\mathbb{E}[Y\mid X]$ 是随机变量。只有独立时（性质 d）才能换成常数 $\mathbb{E}[Y]$。反例：$X\sim U[0,1]$、给定 $X=x$ 时 $Y\sim U[0,x]$，则 $\mathbb{E}[Y\mid X]=X/2$（随 $X$ 变化），而 $\mathbb{E}[Y]=1/4$。
8. 在使用”取出已知量”时把 $Y$ 的因子也提出来。 性质 (b) 只允许把 $X$ 的函数 $h(X)$ 提出来：$\mathbb{E}[h(X)Y\mid X]=h(X)\mathbb{E}[Y\mid X]$。不能把只含 $Y$ 的式子提出去，也不能在非独立时把 $\mathbb{E}[Y]$ 提出来。
9. 忘记全期望公式要求有限期望。 $\mathbb{E}[X]=\sum_y\mathbb{E}[X\mid Y=y]\Pr[Y=y]$ 需要 $\mathbb{E}[\vert X\vert ]<\infty$ 才能交换求和次序。对重尾分布（如 $X$ 为 Cauchy 型，$\mathbb{E}\vert X\vert =\infty$）这条公式会失效（出现 $\infty-\infty$）。
10. 把”时间比例的收敛”和”分布收敛”混为一句”链会收敛到平稳分布”。 要分三层说：(i) 不可约 $\Rightarrow$ 唯一平稳分布 + 时间比例收敛；(ii) 不可约 + 非周期 $\Rightarrow$ 分布 $\Pr[X_n=i]$ 收敛；(iii) 可约 $\Rightarrow$ 以上都不保证（时间比例依赖初始分布；平稳分布可能不唯一）。

思考题（带答案）

Q1.（纯计算：平稳分布） 考虑三状态链（状态 $\{1,2,3\}$） \(P = \begin{pmatrix} 0.5 & 0.3 & 0.2\\ 0.2 & 0.6 & 0.2\\ 0.3 & 0.3 & 0.4\end{pmatrix}.\) (a) 验证它是行随机矩阵。(b) 计算 $P^2$。(c) 解平衡方程求唯一平稳分布 $\pi$。(d) 从状态 $1$ 出发，长期来看处于状态 $2$ 的时间比例是多少？(e) 从状态 $2$ 出发，平均多少步后第一次回到状态 $2$？(f) 该链是否非周期？

Q2.（首步分析：完整赌徒破产） 一枚硬币正面概率 $p=0.4$，反面概率 $q=0.6$。赌徒起始有 $\$2$，每局赢 $$1$（概率 $p$）或输 $\$1$（概率 $q$），游戏在资金达到 $$0$ 或 $\$5$ 时停止。(a) 写出首步方程组。(b) 解出”最终赢到 $$5$”的概率 $\alpha(n)$（给出全部五个非吸收态的值）。(c) 解出期望步数 $\beta(n)$。(d) 验证 $\alpha$ 满足原方程组。(e) 若硬币公平（$p=0.5$），答案变成什么？

Q3.（概念 + 反例） 判断真假并说明理由：(a) “不可约且非周期的有限链，从任意初始分布出发，$\Pr[X_n=i]$ 都收敛到平稳分布 $\pi(i)$。” (b) “有限链的平稳分布总是存在。” (c) “若 $\pi P=\pi$，则 $\pi_n=\pi$ 对一切 $n\ge0$。” (d) “首步方程 $\alpha(i)=\sum_j P(i,j)\alpha(j)$ 与 $\beta(i)=1+\sum_j P(i,j)\beta(j)$ 的区别只在于后者多了个 $1$，所以两者可以同时用同一套边界条件求解。” (e) “条件期望 $\mathbb{E}[X\mid Y]$ 是一个数。”

Q4.（条件期望：对称性与分而治之） (a) 设 $X_1,\dots,X_n$ i.i.d.，$S=\sum_{i=1}^n X_i$。用对称性求 $\mathbb{E}[X_1\mid S]$。(b) 设 $N\sim\mathrm{Poisson}(\lambda)$ 与序列 $Y_1,Y_2,\dots$（i.i.d.，均值 $\mu$）独立，$X=\sum_{i=1}^{N}Y_i$。用全期望公式求 $\mathbb{E}[X]$。(c) $n$ 种优惠券，每次等概率抽到一种，用条件期望求集齐全部的期望次数，并给出 $n=6$ 的数值。