随机过程和马尔可夫链

在前面「指示随机变量」一节中，我们曾用递推方法解决了羽毛球发球权问题——第 n 回合的发球状态仅取决于第 n-1 回合的结果。这种「未来只依赖于现在，而与过去无关」的性质，正是随机过程和马尔可夫链的数学本质。

随机过程初步

随机过程的概念

随机过程（Stochastic Process）是一族随时间演化的随机变量 \{X_t : t \in T\}。其中 T 称为参数集（或指标集），X_t 在每个时刻 t 都是一个随机变量。根据参数集 T 的取值类型，随机过程可分为两类：

离散时间随机过程：T = \{0, 1, 2, \dots\}，通常记作 \{X_n\}_{n=0}^{\infty}。例如：每天记录一次股票价格、每轮比赛后的比分状态
连续时间随机过程：T = [0, \infty) 或 \mathbb{R}，通常记作 \{X_t\}_{t \ge 0}。例如：布朗运动、泊松过程

随机变量 X_t 所有可能取值的集合称为状态空间（State Space），记作 S。状态空间可以是离散的（如 \{1, 2, \dots, n\}）或连续的（如 \mathbb{R}）。对于高中阶段，我们主要关注离散时间、离散状态空间的随机过程。

直观地说，随机过程是对一个「随时间随机演化的系统」的数学描述。每一次完整的演化轨迹 \{x_0, x_1, x_2, \dots\} 称为该过程的一条样本路径（Sample Path）。

独立增量过程

设 \{X_t\} 是一个随机过程。如果对于任意选定的时刻 t_0 < t_1 < t_2 < \dots < t_n，增量

X_{t_1} - X_{t_0},\; X_{t_2} - X_{t_1},\; \dots,\; X_{t_n} - X_{t_{n-1}}

相互独立，则称 \{X_t\} 为独立增量过程（Independent Increment Process）。典型的例子包括：

泊松过程（Poisson Process）：描述随机事件在时间轴上的发生次数，每个不相交时间段内的事件数是独立的
布朗运动（Brownian Motion）：描述微粒在液体中的随机运动，每个不重叠时间段的位移是独立的

独立增量过程的核心在于「不相交的时间段上的变化互不干扰」，这与马尔可夫过程「未来只依赖于现在」的假设不同：独立增量过程的要求更强——它要求增量本身具备独立性。

平稳过程

平稳过程（Stationary Process）是指其统计特性不随时间平移而改变的随机过程。根据平稳性的强弱，分为两类：

严平稳过程（Strictly Stationary）：对于任意时刻 t_1, t_2, \dots, t_n 和任意平移量 \tau，(X_{t_1}, X_{t_2}, \dots, X_{t_n}) 与 (X_{t_1 + \tau}, X_{t_2 + \tau}, \dots, X_{t_n + \tau}) 具有相同的联合分布
宽平稳过程（Weakly Stationary）：只要求均值函数为常数、自协方差函数仅依赖于时间差（而不依赖于绝对时刻）

平稳过程的直观理解是：无论你从哪个时刻开始观察系统，其随机行为「看起来都是一样的」。这一性质在马尔可夫链的「平稳分布」概念中有重要体现——当链演化到平稳分布后，它满足的正是「下一时刻的分布等于当前时刻的分布」。

马尔可夫过程

马尔可夫链的定义

一个随机过程 \{X_n, n = 0, 1, 2, \dots\} 如果满足马尔可夫性质（Markov Property），则称为马尔可夫链（Markov Chain）：

P(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i)

用通俗的语言说：系统下一时刻的状态仅取决于当前时刻的状态，而与历史路径无关。这被称为「无记忆性」（Memorylessness）。

💡直观理解：想象一个在棋盘上随机跳跃的棋子。如果棋子下一步跳到哪里，只取决于它当前在哪个格子，而与它之前经过哪些格子完全无关，那么这个过程就是马尔可夫链。天气预报、网页排名、语音识别——这些都可以建模为马尔可夫链。

马尔可夫链由三个要素构成：

状态空间 S = \{1, 2, \dots, N\}：系统可能处于的所有状态
转移概率 p_{ij} = P(X_{n+1} = j \mid X_n = i)：从状态 i 转移到状态 j 的概率
初始分布 \pi_0：系统在 n = 0 时处于各状态的概率分布

如果转移概率 p_{ij} 不随时间 n 而变化，则称该链是时齐的（Time-Homogeneous）。本章中我们只讨论时齐马尔可夫链。

马尔可夫链的常规解法：递推建模

在解决具体概率问题时，我们常常不直接写出转移矩阵，而是利用马尔可夫性质建立递推关系。这是高中阶段的常用方法，其核心步骤为：

明确状态集：找出所有互斥且完备的状态。
画出转移图：标出每条有向边上的转移概率。
建立递推关系：对每个状态的概率变量，用全概率公式写出其由上一时刻所有状态转移过来的线性组合。
求解与验证：利用数列技巧（特征根、构造等比）求通项，或直接求稳态。

示例（两点链）：一枚硬币，若第 n 次抛掷后系统状态为 X_n，有两种状态：A 和 B。转移规则：

若当前为 A，下次为 A 的概率为 p，为 B 的概率为 1-p；
若当前为 B，下次为 B 的概率为 q，为 A 的概率为 1-q。

则第 n+1 次处于 A 的概率 a_{n+1} 可写为： a_{n+1} = a_n \cdot p + b_n \cdot (1-q) 由于 b_n = 1 - a_n，代入得： a_{n+1} = (p + q - 1)a_n + (1-q) 这是一个一阶线性递推数列，可用特征根法或不动点法求解 a_n 的通项，并研究其极限。

转移矩阵

将所有的转移概率排成矩阵，即得到转移矩阵（Transition Matrix）P：

P = \begin{pmatrix} p_{11} & p_{12} & \dots & p_{1N} \\ p_{21} & p_{22} & \dots & p_{2N} \\ \vdots & \vdots & \ddots & \vdots \\ p_{N1} & p_{N2} & \dots & p_{NN} \end{pmatrix}

核心性质：P 是一个行随机矩阵（Row-Stochastic Matrix），即每行元素非负且和为 1：

\sum_{j=1}^{N} p_{ij} = 1,\quad \forall i

这一定义的物理直觉非常自然：第 i 行描述的是「从状态 i 出发，转移到各个状态的概率分布」，其和必然为 1——因为你从状态 i 出发，必然要转移到某个状态（包括留在原地）。

设第 n 步的状态分布向量为 \pi_n = [P(X_n = 1), P(X_n = 2), \dots, P(X_n = N)]，则系统的演化由下式驱动：

\pi_{n+1} = \pi_n P

通过迭代可得：

\pi_n = \pi_0 P^n

Chapman-Kolmogorov 方程：对于任意非负整数 m 和 n，

P^{m+n} = P^m P^n,\quad \text{即}\quad p_{ij}^{(m+n)} = \sum_k p_{ik}^{(m)} p_{kj}^{(n)}

其中 p_{ij}^{(n)} = (P^n)_{ij} 表示从状态 i 出发，经过 n 步后到达状态 j 的概率。C-K 方程本质上是全概率公式在矩阵形式下的表述——「从 i 到 j 的所有路径的概率之和」。

例 1（简单天气模型）：假设天气只有「晴」（状态 1）和「阴」（状态 2）两种。

若今天晴，明天晴的概率为 0.7，阴的概率为 0.3
若今天阴，明天晴的概率为 0.4，阴的概率为 0.6

构造转移矩阵：

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

若今天晴（\pi_0 = [1, 0]），则：

\begin{aligned} \pi_1 &= \pi_0 P = [0.7, 0.3] \\ \pi_2 &= \pi_0 P^2 = \pi_1 P = [0.61, 0.39] \end{aligned}

两天后晴天的概率为 0.61。

在马尔可夫链的教材中，多数采用行向量 \pi P 的约定（此时 P 的每行和为 1）。这与条件概率的阅读直觉一致：P_{ij} 的第一个下标 i 代表起点，第二个下标 j 代表终点，从左向右阅读恰好对应「从 i 到 j」的逻辑顺序。

如果你习惯使用列向量 P\pi，只需将 P 转置即可，两种写法在数学上完全等价。本章统一采用行向量约定。

状态分类

分析马尔可夫链的长期行为时，需要对状态进行分类。

可达与互通：

称状态 j 从状态 i 可达（Accessible），若存在 n \ge 0 使得 p_{ij}^{(n)} > 0，记作 i \to j
若 i \to j 且 j \to i，则称 i 与 j 互通（Communicate），记作 i \leftrightarrow j

互通是一种等价关系，它将状态空间划分为若干个互通类（Communicating Class）。

不可约与可约：

若链中所有状态都互通（即只有一个互通类），则称该链是不可约的（Irreducible）。此时从任何状态出发都能到达任何其他状态
若存在多个互通类，则称该链是可约的（Reducible）。可约链可以分解为更小的独立子链

周期：

从状态 i 出发，所有能回到 i 的步数集合 \{n \ge 1 : p_{ii}^{(n)} > 0\} 的最大公约数称为状态 i 的周期，记作 d(i)。若 d(i) = 1，则称 i 是非周期的（Aperiodic）。

周期为 2 的例子：一维简单随机游走——从位置 1 出发，必须经过偶数步才能回到 1
非周期的例子：天气模型——从晴天出发，一步就能回到晴天（p_{11} = 0.7 > 0），所以 d(1) = 1

常返与瞬时：

设 f_i 为从状态 i 出发最终回到 i 的概率。若 f_i = 1，则称 i 是常返的（Recurrent）；若 f_i < 1，则称 i 是瞬时的（Transient）
直观理解：常返状态是「你迟早会再回来」的状态；瞬时状态是「有一定概率离开后再也不回来」的状态

对于有限状态空间的马尔可夫链，至少存在一个常返状态。若链是不可约的，则所有状态要么全是常返的，要么全是瞬时的。有限不可约链的所有状态都是常返的。

当状态空间为无限时（如随机游走在 \mathbb{Z} 上），情况更复杂。一维和二维的对称随机游走是常返的（最终几乎必然回到原点），而三维及以上的对称随机游走是瞬时的——这意味着一个三维空间中的醉汉，有一定概率永远找不到回家的路。

平稳分布与正则链

随着时间推移，许多马尔可夫链会「忘记」初始状态，趋于一个稳定的概率分布。这个分布称为平稳分布（Stationary Distribution），记作 \pi。

定义：若存在一个概率分布 \pi 满足

\pi P = \pi,\quad \sum_{i=1}^{N} \pi_i = 1

则称 \pi 为该马尔可夫链的一个平稳分布。从线性代数的角度看，\pi 是转移矩阵 P 对应于特征值 \lambda = 1 的左特征向量。

正则链：若存在 k 使得 P^k 的所有元素严格大于 0，则链是正则的（Regular）。正则链一定是不可约且非周期的。此时 \lim_{n\to\infty} P^n = \mathbf{1}\mathbf{w}，其中行向量 \mathbf{w} 是唯一的平稳分布。

存在性与唯一性：对于有限状态空间、不可约、非周期的马尔可夫链，平稳分布存在且唯一。此时对任意初始分布 \pi_0，都有：

\lim_{n \to \infty} \pi_n = \lim_{n \to \infty} \pi_0 P^n = \pi

这一性质被称为收敛到平稳分布——无论从何处出发，长期来看系统都会「忘记」起点，趋于同一个稳定状态。

求解技巧：直接解方程组 \pi (P - I) = 0，再加上归一化条件 \sum \pi_i = 1。相比求 P^n 的复杂幂次，这一方法能瞬间得到长期概率。例如上文两点链的稳态为：

\pi_A = \frac{1-q}{2-p-q},\quad \pi_B = \frac{1-p}{2-p-q}

例 2（天气模型的平稳分布）：设平稳分布为 \pi = [x, y]（x + y = 1），解方程 [x, y] P = [x, y]：

\begin{cases} 0.7x + 0.4y = x \\ 0.3x + 0.6y = y \\ x + y = 1 \end{cases}

由第一个方程得 0.4y = 0.3x，即 y = \dfrac{3}{4}x。代入 x + \dfrac{3}{4}x = 1，得 x = \dfrac{4}{7}，y = \dfrac{3}{7}。长期来看，晴天的概率约为 57.1\%，阴天的概率约为 42.9\%。

吸收马尔可夫链

一类特别重要的马尔可夫链是吸收链（Absorbing Markov Chain），其特点是：存在某些状态，一旦进入就再也无法离开。这些状态称为吸收状态（Absorbing State）。若从任何状态出发，最终都能到达某个吸收状态，则称该链为吸收链。

标准型：通过重新排列状态顺序，吸收链的转移矩阵可以写成如下分块形式：

P = \begin{pmatrix} I & 0 \\ R & Q \end{pmatrix}

其中：

Q：瞬时状态（Transient States）之间的转移子矩阵
R：从瞬时状态到吸收状态的转移子矩阵
I：单位矩阵（吸收状态之间的转移——进去了就不出来）
0：零矩阵（吸收状态无法回到瞬时状态）

基础矩阵（Fundamental Matrix）定义为：

N = (I - Q)^{-1}

N 的元素 n_{ij} 的物理含义是：从瞬时状态 i 出发，在被吸收之前，访问瞬时状态 j 的期望次数。基础矩阵是吸收链分析的核心工具——一旦求出 N，期望吸收时间、吸收概率等都可以通过它计算得出。

具体地：

从瞬时状态 i 出发，到达吸收状态的期望步数为 N \mathbf{1} 的第 i 个分量，其中 \mathbf{1} 是全 1 列向量。
从瞬时状态 i 出发，最终被吸收到某个吸收状态 j 的概率为 N R 中对应元素。

在高中竞赛中，我们不写矩阵也可以处理吸收链问题，常用的手法是「势函数法」或「差分方程」。例如赌徒破产问题：设从 k 元出发，赢 1 元概率 p，输 1 元概率 q。吸收概率 u_k 满足递推 u_k = p u_{k+1} + q u_{k-1}，结合边界 u_0=0, u_N=1 求解。特征根为 q/p，这里直接体现了「鞅」和公平性的思想。

马尔可夫链中的期望方程

在上一章「数学期望」中，我们学习了条件期望、全期望公式和期望方程。本节将从马尔可夫链的视角重新审视这些方法，使两者融合为一个统一的框架。

首步分析法与状态转移

回顾期望方程的核心步骤：定义状态、写出「当前状态的期望 = 1 + 下一步状态期望的加权平均」、解方程。在马尔可夫链中，这等价于为每个瞬时状态 i 建立方程：

E_i = 1 + \sum_{j \in T} p_{ij} E_j

其中 T 表示瞬时状态的集合。将所有状态写为向量形式：

\mathbf{E} = \mathbf{1} + Q \mathbf{E}

整理得：

(I - Q)\mathbf{E} = \mathbf{1}

于是：

\mathbf{E} = (I - Q)^{-1} \mathbf{1} = N \mathbf{1}

核心结论：从每个瞬时状态出发的期望吸收时间，就是基础矩阵 N 对应行的元素之和。这个公式将看似独立的期望方程统一在了马尔可夫链的基础矩阵框架下。

完整例题：甲乙竞答问题

题目：甲乙两人参加知识竞答，两人第一轮答对的概率都是 1/2。第二轮及以后，和上一轮结果相同的答对概率是 3/4，答错概率是 2/3（即若上一轮答对则本轮继续答对的概率为 3/4，若上一轮答错则本轮继续答错的概率为 2/3）。甲乙两人互不影响。如果两人同时答错，游戏停止。

（1）设 A_n 为「甲在第 n 轮活动中答对」，求 P(A_n)；（2）设停止游戏时进行了 Y 轮，求 E(Y)。

分析：甲乙两人互不影响，因此（1）只需分析单人的状态转移。（2）需要分析联合状态——游戏停止的条件是两人同时答错，所以状态空间是甲乙答对/答错的四种组合。

第一问：求 P(A_n)

设 p_n = P(A_n) 表示甲在第 n 轮答对的概率。

甲在第 n 轮答对，有两种可能：

第 n-1 轮答对且本轮保持答对：概率为 p_{n-1} \cdot \dfrac{3}{4}
第 n-1 轮答错且本轮转为答对：答错的概率是 1 - p_{n-1}，而「答错 \to 答错」的概率是 \dfrac{2}{3}，所以「答错 \to 答对」的概率是 1 - \dfrac{2}{3} = \dfrac{1}{3}，故概率为 (1 - p_{n-1}) \cdot \dfrac{1}{3}

由全概率公式：

p_n = \frac{3}{4} p_{n-1} + \frac{1}{3}(1 - p_{n-1}) = \frac{5}{12} p_{n-1} + \frac{1}{3}

寻找不动点：令 x = \dfrac{5}{12}x + \dfrac{1}{3}，解得 x = \dfrac{4}{7}。构造等比数列：

p_n - \frac{4}{7} = \frac{5}{12}\left(p_{n-1} - \frac{4}{7}\right)

已知 p_1 = \dfrac{1}{2}，则 p_1 - \dfrac{4}{7} = -\dfrac{1}{14}。因此：

\boxed{P(A_n) = \frac{4}{7} - \frac{1}{14}\left(\frac{5}{12}\right)^{n-1}}

当 n \to \infty 时，P(A_n) \to \dfrac{4}{7}——这是甲长期答对的稳定概率，恰好是平稳分布中「答对」状态的概率。

第二问：求 E(Y)

游戏的停止条件是两人同时答错。定义联合状态：

状态 S_{11}：两人都答对
状态 S_{10}：甲对、乙错
状态 S_{01}：甲错、乙对
状态 S_{00}：两人都错（吸收状态）

设 E_{11}, E_{10}, E_{01} 分别表示从对应状态出发，还需进行多少轮才会停止。目标是用首步分析法建立期望方程。

从 S_{11} 出发：进入下一轮后，有四种可能：

两人都保持答对或转为答对，回到 S_{11}：概率 \dfrac{3}{4} \times \dfrac{3}{4} = \dfrac{9}{16}
甲保持/转为答对、乙变为答错，进入 S_{10}：概率 \dfrac{3}{4} \times \dfrac{1}{4} = \dfrac{3}{16}
甲变为答错、乙保持/转为答对，进入 S_{01}：概率 \dfrac{1}{4} \times \dfrac{3}{4} = \dfrac{3}{16}
两人都答错，停止：概率 \dfrac{1}{4} \times \dfrac{1}{4} = \dfrac{1}{16}

加上本轮本身的 1 轮：

E_{11} = 1 + \frac{9}{16}E_{11} + \frac{3}{16}E_{10} + \frac{3}{16}E_{01}

从 S_{10} 出发（甲对、乙错）：下一轮甲的保持/转变概率与人的状态有关。甲本轮答对，下一轮保持答对的概率为 \dfrac{3}{4}；甲本轮答错（若转变），下一轮答对的概率为 \dfrac{1}{3}。但这里乙本轮答错，下一轮保持答错的概率为 \dfrac{2}{3}。

实际上，这道题目需要更精确地分析。已知：

若上一轮答对，本轮答对的概率为 \dfrac{3}{4}（所以答错的概率为 \dfrac{1}{4}）
若上一轮答错，本轮答错的概率为 \dfrac{2}{3}（所以答对的概率为 \dfrac{1}{3}）

注意：文中「和上一轮相同的答对或者答错概率分别是 3/4 和 2/3」应解读为：若上一轮答对，本轮继续答对的概率为 3/4；若上一轮答错，本轮继续答错的概率为 2/3。由此可得：

从答对到答对：3/4；从答对到答错：1/4
从答错到答对：1/3；从答错到答错：2/3

在状态 S_{10}（甲对、乙错）中：

甲（上一轮对）：\to 对 3/4，\to 错 1/4
乙（上一轮错）：\to 对 1/3，\to 错 2/3

下一轮四种可能：

甲对、乙对 \to S_{11}：\dfrac{3}{4} \times \dfrac{1}{3} = \dfrac{1}{4}
甲对、乙错 \to S_{10}：\dfrac{3}{4} \times \dfrac{2}{3} = \dfrac{1}{2}
甲错、乙对 \to S_{01}：\dfrac{1}{4} \times \dfrac{1}{3} = \dfrac{1}{12}
甲错、乙错 \to S_{00}（停止）：\dfrac{1}{4} \times \dfrac{2}{3} = \dfrac{1}{6}

因此：

E_{10} = 1 + \frac{1}{4}E_{11} + \frac{1}{2}E_{10} + \frac{1}{12}E_{01}

由对称性，E_{01} = E_{10}。方程组简化为：

\begin{cases} E_{11} = 1 + \dfrac{9}{16}E_{11} + \dfrac{6}{16}E_{10} \\[8pt] E_{10} = 1 + \dfrac{1}{4}E_{11} + \dfrac{1}{2}E_{10} + \dfrac{1}{12}E_{10} \end{cases}

化简得：

\begin{cases} \dfrac{7}{16}E_{11} - \dfrac{3}{8}E_{10} = 1 \\[8pt] \dfrac{1}{4}E_{11} - \dfrac{5}{12}E_{10} = -1 \end{cases}

由第二个方程：E_{10} = \dfrac{12 + 3E_{11}}{5}。代入第一个：

\frac{7}{16}E_{11} - \frac{3}{8} \cdot \frac{12 + 3E_{11}}{5} = 1

两边乘 80：

35E_{11} - 6(12 + 3E_{11}) = 80

35E_{11} - 72 - 18E_{11} = 80

17E_{11} = 152

E_{11} = \frac{152}{17},\quad E_{10} = \frac{12 + 3 \cdot \frac{152}{17}}{5} = \frac{132}{17}

计算总期望 E(Y)：第一轮结束后，四种状态等可能（各 1/4）：

\begin{aligned} E(Y) &= 1 + \frac{1}{4}(E_{11} + E_{10} + E_{01} + 0) \\ &= 1 + \frac{1}{4}\left(\frac{152}{17} + \frac{132}{17} + \frac{132}{17}\right) \\ &= 1 + \frac{1}{4} \cdot \frac{416}{17} = 1 + \frac{104}{17} = \boxed{\frac{121}{17}} \end{aligned}

与基础矩阵视角的关联：本题的方程组 \dfrac{7}{16}E_{11} - \dfrac{3}{8}E_{10} = 1 和 \dfrac{1}{4}E_{11} - \dfrac{5}{12}E_{10} = -1 正是 (I - Q)\mathbf{E} = \mathbf{1} 的展开。从矩阵形式可以直接得到答案，无需手动消元——这就是吸收马尔可夫链基础矩阵的威力所在。

当你面对「重复进行直到满足条件才停止」的问题时：

找状态：把所有可能导致后续概率不同的情况定义为状态
写方程：E_{\text{now}} = 1 + \sum P_{\text{next}} \cdot E_{\text{next}}
解方程：算出每个状态的期望，最后结合初始概率求总期望

这种方法不需要矩阵知识，只需要基础概率的加法/乘法法则和二元一次方程组。它与吸收马尔可夫链的基础矩阵方法是完全等价的——前者是朴素的方程法，后者是矩阵形式的统一表述。

马尔可夫链的总结与反思

核心思想：马尔可夫链的本质是将复杂的时序概率系统，压缩为状态间的一步转移关系。其灵魂在于无后效性：未来只由现在决定，历史被折叠进了当前状态。

解题逻辑模板：

语义解析 → 状态定义：将题目描述的随机事件抽象为互斥的状态集合（例如“持有球数”“硬币正反面”“栅栏位置”）。
关系映射 → 转移方程：用全概率公式或矩阵直接编码规则。若参数对称，可以尝试提取公共因子或使用均值技巧。
动态分析 → 通项/极限：
- 短期行为：解递推数列，关注通项中 n 的线性或指数依赖。
- 长期行为：直接解平稳方程组 \pi P = \pi，或利用吸收链标准型。

陷阱与迁移：

陷阱点：状态定义不完备导致遗漏概率，或误用“无后效性”（如果下一步概率依赖于更早的历史，必须扩充状态定义，将历史信息包含进当前状态）。
迁移场景：
- 遗传学：Hardy-Weinberg 平衡就是一个马尔可夫链稳态。
- 页面排序：Google PageRank 是随机游走的平稳分布。
- 期望值问题：结合全期望公式，对“首次到达某状态”的期望步数建立一步转移的期望方程，这是竞赛热点。

通过这一套框架，任何离散时间、有限状态的随机过程问题，都能被降维成你熟悉的线性代数或数列问题。反复训练“建状态-画转移-列方程”的动作，就能从算力堆砌转向结构洞察。

RainPPR, Bot