Markov 性质 — 核心定义
\[ \mathbb{P}(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = \mathbb{P}(X_{n+1} = j \mid X_n = i) \]
直觉："给定现在，未来与过去无关"——系统的全部信息浓缩在当前状态中。
类比：下棋时，只需要看当前棋盘局面，不需要记住整个对局历史。股价的技术分析若满足 Markov 性，则"K线历史"在数学上不提供额外信息。
转移矩阵与 Chapman–Kolmogorov
状态分类
| 状态类型 | 定义 | 金融类比 |
|---|
| 吸收态 | \(P_{ii}=1\)，进入后无法离开 | 违约状态、到期 |
| 常返态 | \(\mathbb{P}(T_i < \infty \mid X_0=i) = 1\) | 均值回归价格 |
| 暂态 | \(\mathbb{P}(T_i < \infty \mid X_0=i) < 1\) | 趋势性资产 |
| 周期态 | 最大公因子 \(d(i)>1\) | 季节性周期 |
稳态分布 (Stationary Distribution)
物理意义：想象一大批粒子同时在链上游走。\(\pi_j\) = 长期下来有多少比例的粒子在状态 j。流入 = 流出。
求解套路：列 \(\pi P = \pi\)，去掉一个方程（线性相关），换成 \(\sum \pi_i = 1\)。
定理 — 遍历定理 (Ergodic Theorem)
若链不可约且遍历（正常返 + 非周期），则：
\[ \lim_{n\to\infty} P^n_{ij} = \pi_j \quad \text{（与初始状态无关）} \]
\[ \pi_j = \frac{1}{\mathbb{E}[T_j \mid X_0=j]} \quad \text{（稳态概率 = 平均回访时间的倒数）} \]
细致平衡 (Detailed Balance)
击中时间 (Hitting Time)
吸收链：基本矩阵
例题 01 — 经典 Simple Random Walk（Gambler's Ruin）
粒子在 \(\{0,1,2,3\}\) 上游走，0 和 3 为吸收壁，从内部状态 \(i\) 以概率 \(p\) 向右走，\(q=1-p\) 向左走。
(a) 从状态 1 出发到达状态 3 的概率。
(b) 期望吸收时间的方程组。
(a) \(u_i = P(\text{到达}3\mid X_0=i)\)，\(u_0=0, u_3=1\)，内部：\(u_i = p u_{i+1} + q u_{i-1}\)
若 \(p\neq q\)：\(\displaystyle u_i = \frac{1-(q/p)^i}{1-(q/p)^3}\)；若 \(p=q=\frac{1}{2}\)：\(u_i = \frac{i}{3}\)
故 \(u_1 = \dfrac{1-(q/p)}{1-(q/p)^3}\)
(b) \(e_i = \mathbb{E}[T\mid X_0=i]\)，\(e_0=e_3=0\)：
\[e_1 = 1 + p e_2, \quad e_2 = 1 + q e_1\]
若 \(p=q=\frac{1}{2}\)：\(e_1 = e_2 = 2\)
Markov 性质 — 连续时间
\[ \mathbb{P}(X_t = j \mid \mathcal{F}_s) = \mathbb{P}(X_t = j \mid X_s), \quad \forall s \leq t \]
Q 矩阵（生成元矩阵）
稳态分布 (CTMC)
生灭过程 (Birth-Death Process)
状态空间 \(\{0,1,2,\ldots\}\)，仅允许 \(\pm1\) 跳转，速率 \(\lambda_i\)（生）、\(\mu_i\)（死）。
例题 — M/M/1 排队模型
到达率 \(\lambda\)，服务率 \(\mu\)，单服务台，\(\rho = \lambda/\mu < 1\)。求稳态分布、平均队长、平均等待时间。
稳态分布（几何）：\(\pi_n = (1-\rho)\rho^n\)
队列平均长度：\(\mathbb{E}[N] = \dfrac{\rho}{1-\rho} = \dfrac{\lambda}{\mu-\lambda}\)
平均系统时间：\(\mathbb{E}[W] = \dfrac{1}{\mu-\lambda}\)；平均等待时间：\(\mathbb{E}[W_q] = \dfrac{\lambda}{\mu(\mu-\lambda)}\)
Little's Law：\(\mathbb{E}[N] = \lambda \cdot \mathbb{E}[W]\)
超高频考点
三种等价定义
叠加与细化
PASTA性质
三种等价定义
定义 1 — 计数过程（公理化）
\(\{N(t), t \geq 0\}\) 是速率为 \(\lambda\) 的 Poisson 过程，若：
- \(N(0) = 0\)
- 独立增量：不重叠区间上的增量相互独立
- 平稳增量：\(N(t+s) - N(s) \overset{d}{=} N(t)\)
- \(N(t) \sim \text{Poisson}(\lambda t)\)，即 \(\mathbb{P}(N(t)=k) = \dfrac{(\lambda t)^k e^{-\lambda t}}{k!}\)
定义 2 — 到达间隔（构造性）
相邻到达时间间隔 \(X_i = T_i - T_{i-1}\) i.i.d. \(\sim \text{Exp}(\lambda)\)
定义 3 — 无穷小（微分刻画）
\[ \mathbb{P}(N(t+h) - N(t) = 1) = \lambda h + o(h) \]
\[ \mathbb{P}(N(t+h) - N(t) \geq 2) = o(h) \]
\[ \mathbb{P}(N(t+h) - N(t) = 0) = 1 - \lambda h + o(h) \]
三种定义完全等价
以上三种定义可以互相推出，使用哪种取决于问题情境：公理化用于理论推导，构造性用于模拟，微分刻画用于 CTMC 嵌入分析。
核心性质
指数分布的无记忆性
定理 — 无记忆性 ⟺ 指数分布（连续情形唯一）
\[ \mathbb{P}(X > s + t \mid X > s) = \mathbb{P}(X > t) \]
证明：\(\dfrac{P(X>s+t)}{P(X>s)} = \dfrac{e^{-\lambda(s+t)}}{e^{-\lambda s}} = e^{-\lambda t} = P(X>t)\)
直觉：已经等了 \(s\) 时间，未来还需等待的时间分布与刚开始等一样——"没有记忆"。
到达时刻分布
条件均匀性（面试重点）
定理 — 给定 \(N(t)=n\)，到达时刻均匀分布
给定 \(N(t) = n\)，则 \(n\) 个到达时刻 \((T_1, \ldots, T_n)\) 联合分布等价于 \([0,t]\) 上 \(n\) 个
独立均匀随机变量的
次序统计量：
\[ f(t_1,\ldots,t_n \mid N(t)=n) = \frac{n!}{t^n}, \quad 0 < t_1 < \cdots < t_n < t \]
直觉：已知 \([0,t]\) 内恰好有 \(n\) 个到达，每个到达点均匀散布在区间内。
叠加与细化
PASTA 性质
PASTA — Poisson Arrivals See Time Averages
泊松到达者看到的系统状态分布 = 时间平均分布。这是排队论的核心性质，对非泊松过程一般
不成立。
例题 — Poisson 过程综合
Poisson 过程，速率 \(\lambda = 2\)（每小时2次）。
(a) 在 \([0,3]\) 内恰好 5 次到达的概率。
(b) 已知 \([0,2]\) 内恰好 3 次到达，3 次到达均在 \([0,1]\) 内的概率。
(c) 第 4 次到达时刻的期望。
(a) \(N(3) \sim \text{Poisson}(6)\)：
\[\mathbb{P}(N(3)=5) = \frac{6^5 e^{-6}}{5!} = \frac{7776\,e^{-6}}{120} \approx 0.1606\]
(b) 利用条件均匀性：给定 \(N(2)=3\)，3次到达均匀分布在 \([0,2]\)。
3次均在 \([0,1]\) 的概率 = \(\left(\dfrac{1}{2}\right)^3 = \dfrac{1}{8}\)
(c) \(S_4 = X_1+X_2+X_3+X_4\)，\(X_i\sim\text{Exp}(2)\)，期望 \(1/2$ 小时：
\[\mathbb{E}[S_4] = \frac{4}{\lambda} = \frac{4}{2} = 2 \text{ 小时}\]
超高频考点
面试必背
指数最小值
核心结论（三合一）
定理 — 竞争指数
设 \(T_1 \sim \text{Exp}(\lambda_1), \ldots, T_n \sim \text{Exp}(\lambda_n)\) 独立，令 \(M = \min(T_1, \ldots, T_n)\)，则：
① 最小值仍是指数分布：
\[ M \sim \text{Exp}(\lambda_1 + \cdots + \lambda_n) \]
② 谁最小的概率：
\[ P(T_i = \min) = \frac{\lambda_i}{\lambda_1 + \cdots + \lambda_n} \]
③ 谁最小与最小值无关（独立性）：
\[ \{T_i = \min\} \perp M \]
完整证明（\(n=2\)）
与 Poisson 过程的联系
两个独立 Poisson 过程 \(N_1 \sim \text{PP}(\lambda_1)\)，\(N_2 \sim \text{PP}(\lambda_2)\)，第一次到达时刻分别为 \(T_1, T_2\)。
竞争指数 = 两个过程谁先发生一次事件的问题。\(P(T_1 < T_2) = \lambda_1/(\lambda_1+\lambda_2)\) 就是 \(N_1\) 先到一步的概率。
经典例题：\(X > Y\) 的概率
例题 — X, Y 独立指数，求 P(X > Y)
\(X \sim \text{Exp}(1/6)\)（均值 6），\(Y \sim \text{Exp}(1/8)\)（均值 8），独立。求 \(P(X > Y)\)。
方法 1：直接积分
\[P(X > Y) = \int_0^\infty \frac{1}{8}e^{-y/8}\left(\int_y^\infty \frac{1}{6}e^{-x/6}dx\right)dy = \int_0^\infty \frac{1}{8}e^{-y/8} \cdot e^{-y/6}\,dy\]
\[= \frac{1/8}{1/8 + 1/6} = \frac{1/8}{7/24} = \boxed{\frac{3}{7}}\]
方法 2：竞争指数通用公式（\(\lambda_X=1/6\)，\(\lambda_Y=1/8\)）：
\[P(X > Y) = P(Y \text{ 先到}) = \frac{\lambda_Y}{\lambda_X + \lambda_Y} = \frac{1/8}{1/6+1/8} = \frac{3}{7}\]
直觉验证：\(X\) 均值更大（速率更小），更"慢"，所以 \(P(X>Y) = 3/7 < 1/2\)，符合直觉。
例题 — 多个竞争指数 + 独立性
三台机器，寿命分别为 \(T_1\sim\text{Exp}(1)\)，\(T_2\sim\text{Exp}(2)\)，\(T_3\sim\text{Exp}(3)\)，独立。
(a) 最先坏的机器是机器 2 的概率。
(b) 最先坏的机器坏掉时，距现在的期望时间。
(c) 机器 2 最先坏掉后，剩余两台中下一个坏掉的期望时间。
(a) \(P(T_2 = \min) = \dfrac{2}{1+2+3} = \dfrac{1}{3}\)
(b) \(M = \min(T_1,T_2,T_3) \sim \text{Exp}(1+2+3) = \text{Exp}(6)\)，期望 \(= \dfrac{1}{6}\)
(c) 关键：由无记忆性，已知 \(T_2\) 最先坏，\(T_1\) 和 \(T_3\) 的剩余寿命分布不变（仍为 \(\text{Exp}(1)\) 和 \(\text{Exp}(3)\)）。
下一台坏掉的时间 \(\sim \text{Exp}(1+3) = \text{Exp}(4)\)，期望 \(= \dfrac{1}{4}\)。
核心技巧：独立性与无记忆性联合使用——"已知谁最先，其余的未来分布不变"，这正是指数分布无记忆性的关键作用。
例题 — 混合指数分布 · 均值与方差（Q2.3 原题）
以各 50% 概率随机选择参数 \(\lambda_1\) 或 \(\lambda_2\) 的指数分布，作为混合分布 \(T\)。求 \(\mathbb{E}[T]\) 与 \(\text{Var}(T)\)。
密度：\(f_T(t) = \dfrac{1}{2}\lambda_1 e^{-\lambda_1 t} + \dfrac{1}{2}\lambda_2 e^{-\lambda_2 t}\)
均值（全期望）：
\[\mathbb{E}[T] = \frac{1}{2}\cdot\frac{1}{\lambda_1} + \frac{1}{2}\cdot\frac{1}{\lambda_2}\]
方差（全方差公式）：
\[\text{Var}(T) = \underbrace{\mathbb{E}[\text{Var}(T|I)]}_{\text{组内方差}} + \underbrace{\text{Var}(\mathbb{E}[T|I])}_{\text{组间方差}}\]
\[= \frac{1}{2\lambda_1^2} + \frac{1}{2\lambda_2^2} + \frac{1}{4}\left(\frac{1}{\lambda_1}-\frac{1}{\lambda_2}\right)^2\]
验证：若 \(\lambda_1=\lambda_2=\lambda\)，则 \(\text{Var}=\frac{1}{\lambda^2}\) ✓（组间方差为0）
速查表
| 情形 | 结论 |
|---|
| \(\min(T_1,\ldots,T_n)\) 的分布 | \(\text{Exp}(\sum\lambda_i)\) |
| \(P(T_i = \min)\) | \(\lambda_i / \sum\lambda_j\) |
| 谁最小 与 最小值 | 独立！ |
| \(P(X>Y)\)，\(X\sim\text{Exp}(\lambda)\)，\(Y\sim\text{Exp}(\mu)\) | \(\mu/(\lambda+\mu)\) |
| 无记忆性后继续等待 | 分布不变，剩余寿命仍为原指数 |
实际面试题
QR Interview
Philadelphia · Nov 2024
Q56 — Good Day / Bad Day Chain · 稳态 + 击中时间
Good→Good: 0.6，Good→Bad: 0.4；Bad→Good: 0.3，Bad→Bad: 0.7。
从 Bad 出发，期望多少天后再次遇到 Bad 天？
方法一（最快）：稳态分布倒推。
\[0.4\pi_G = 0.3\pi_B \Rightarrow \pi_B = \frac{4}{7}\]
平均回访时间 = \(\dfrac{1}{\pi_B} = \boxed{1.75 \text{ 天}}\)
方法二：直接列方程
\[h_G = 1 + 0.6 h_G \Rightarrow h_G = 2.5, \quad h_B = 1 + 0.3 h_G = 1.75\]
Q57/Q58 — Consecutive Heads · 一步分析法
公平硬币，期望多少次投掷首次出现连续 2 次正面 (HH)？
状态机：\(S_0\)（初始）、\(S_H\)（刚出现1次H）、\(S_{HH}\)（结束）。
设 \(e_0, e_H\) = 从各状态出发的期望步数：
\[e_0 = 1 + \frac{1}{2}e_H + \frac{1}{2}e_0 \Rightarrow e_0 = 2 + e_H\]
\[e_H = 1 + \frac{1}{2}\cdot 0 + \frac{1}{2}e_0 \Rightarrow e_H = 1 + \frac{1}{2}e_0\]
联立：\(e_0 = 2 + 1 + \frac{1}{2}e_0 \Rightarrow e_0 = \boxed{6}\)
Q60 — Ball Replacement · 吸收链
袋中 2 红 1 蓝，每次随机取出一个球，放入一个蓝球（不管取出什么），直到所有球为蓝。从初始状态出发，期望几次？
状态 = 红球数。初始状态 2，目标状态 0。
状态 2（2红1蓝）：取出红（概率2/3）→状态1；取出蓝（概率1/3）→状态2
状态 1（1红2蓝）：取出红（概率1/3）→状态0；取出蓝（概率2/3）→状态1
\[e_1 = 1 + \frac{2}{3}e_1 \Rightarrow e_1 = 3\]
\[e_2 = 1 + \frac{1}{3}e_2 + \frac{2}{3}e_1 \Rightarrow e_2 = \boxed{4.5}\]
Q61 — Alternating Dice · 生成函数
骰子 A 和 B 交替掷（A 先），游戏在 A 掷出 6 时结束。
(a) 游戏在 A 轮次结束的概率。(b) 总掷骰次数期望。
(a) 概率 = 1（只有 A 能终止游戏）。
(b) 第 \(k\) 轮 A 成功时，已掷 \(2k-1\) 次（A 掷 k 次，B 掷 k-1 次）：
\[\mathbb{E} = \sum_{k=1}^\infty \left(\frac{5}{6}\right)^{k-1}\frac{1}{6}(2k-1) = \frac{1}{6}\cdot\frac{1+5/6}{(1/6)^2} = \boxed{11}\]
直觉验证：A 平均第 6 轮成功，前 5 轮各有一次 B 的掷骰 = 5+6 = 11 次。✓
高难度题型
阶段分解
Gambler's Ruin应用
问题设定
圆环 \(N\) 个位置，从 0 出发，以概率 \(p\) 向右，\(q=1-p\) 向左（模 \(N\) 循环）。
Cover Time \(T_C\) = 首次访问所有 \(N\) 个位置所需的步数。
为什么难？击中时间有固定目标可列方程；Cover Time 的目标集合动态变化，需要阶段分解。
关键引理 — 已访问集合是连续弧段
任意时刻已访问集合形如 \([-L, R]\)（圆环上的弧），覆盖完成 \(\Leftrightarrow L+R=N-1\)。
定理 — 公平游走 Cover Time（\(p = 1/2\)）
\[\mathbb{E}[\Delta_k] = k \quad (\text{每阶段平均需要 }k\text{ 步})\]
\[\mathbb{E}[T_C] = \sum_{k=1}^{N-1} k = \frac{N(N-1)}{2}\]
| 情形 | 期望 Cover Time | 量级 |
|---|
| 圆环，\(p=1/2\) | \(\dfrac{N(N-1)}{2}\) | \(O(N^2)\) |
| 圆环，\(p\to1\) | \(N-1\)（直接绕圈） | \(O(N)\) |
| 完全图 \(K_N\) | \(N H_N \approx N\ln N\) | \(O(N\log N)\) |
例题 — N=5 圆环完整推导
圆环 \(N=5\)，公平游走。写出各阶段期望并求 \(\mathbb{E}[T_C]\)。
\(\mathbb{E}[\Delta_1]=1\)，\(\mathbb{E}[\Delta_2]=2\)，\(\mathbb{E}[\Delta_3]=3\)，\(\mathbb{E}[\Delta_4]=4\)
\[\mathbb{E}[T_C] = 1+2+3+4 = \boxed{10} = \frac{5\times4}{2}\]
若 \(p=0.7\)：偏右使游走更接近"确定性绕圈"，\(\mathbb{E}[T_C] \approx 5.8 < 10\)，当 \(p\to1\) 时趋向 4。
超高频考点
OST定理
鞅构造
简单随机游走基础
定义
\(\xi_i\) i.i.d.，\(P(\xi_i=+1)=p\)，\(P(\xi_i=-1)=q\)，\(S_n = \sum_{i=1}^n \xi_i\)，\(S_0=0\)。
三个标准鞅
Optional Stopping Theorem (OST)
定理 — 可选停时定理
若 \(M_n\) 是鞅，\(\tau\) 是停时，满足以下任一条件，则 \(\mathbb{E}[M_\tau] = \mathbb{E}[M_0]\)：
- \(\tau\) 有界（\(\tau \leq N\) 几乎处处）
- \(\mathbb{E}[\tau] < \infty\) 且 \(|M_{n+1} - M_n|\) 一致有界
- \(M_{n\wedge\tau}\) 一致可积
OST 陷阱：公平游走首达 +1 的期望时间 \(\mathbb{E}[\tau_1] = +\infty\)，OST 不能直接适用！
经典 Gambler's Ruin（鞅方法）
例题 A — 标准 OST 流程（公平游走）
公平游走，\(S_0=0\)，停时 \(\tau = \min\{n: S_n=3 \text{ 或 } S_n=-1\}\)。
用鞅方法求 (a) \(P(S_\tau=3)\) 和 (b) \(\mathbb{E}[\tau]\)。
(a) 鞅①：\(\mathbb{E}[S_\tau]=0\)，设 \(u=P(S_\tau=3)\)：
\[3u + (-1)(1-u) = 0 \Rightarrow 4u=1 \Rightarrow \boxed{u=\frac{1}{4}}\]
验证：\(a=3,b=1\)，\(P=b/(a+b)=1/4\) ✓
(b) 鞅②：\(\mathbb{E}[\tau] = \mathbb{E}[S_\tau^2] = 9\cdot\frac{1}{4} + 1\cdot\frac{3}{4} = 3\)
验证：\(\mathbb{E}[\tau]=ab=3\times1=3\) ✓
例题 B — 有偏游走：吸收概率 + 期望停时
有偏游走，\(p=2/3\)，\(q=1/3\)，\(S_0=0\)，边界 \(+2\) 和 \(-1\)。
(a) \(P(S_\tau=+2)\)（用指数鞅 \((q/p)^{S_n}=(1/2)^{S_n}\)）。
(b) 用 \(S_n-n(p-q)\) 求 \(\mathbb{E}[\tau]\)。
(a) OST 用 \((1/2)^{S_\tau}\)，设 \(u=P(S_\tau=2)\)：
\[\frac{u}{4} + 2(1-u) = 1 \Rightarrow u = \frac{4}{7}\]
验证 Gambler's Ruin 公式：\(\dfrac{1-(1/2)^1}{1-(1/2)^3} = \dfrac{4}{7}\) ✓
(b) 鞅 \(S_n - n/3\)，OST：\(\mathbb{E}[S_\tau] = \frac{1}{3}\mathbb{E}[\tau]\)
\[\mathbb{E}[S_\tau] = 2\cdot\frac{4}{7} + (-1)\cdot\frac{3}{7} = \frac{5}{7}\]
\[\mathbb{E}[\tau] = \frac{5/7}{1/3} = \boxed{\frac{15}{7}}\]
例题 C — 单边无穷破产（指数鞅 + 截断法）
有偏游走 \(p=2/3\)，\(S_0=0\)，无右边界，左边界 \(-3\)（破产）。求永远不破产的概率。
用指数鞅 \(\rho^{S_n}=(1/2)^{S_n}\)，截断停时 \(\tau_N = \min(\tau_{-3}, N)\)，OST 给 \(\mathbb{E}[\rho^{S_{\tau_N}}]=1\)。
令 \(N\to\infty\)：若不破产则 \(S_n\to+\infty\)，\(\rho^{S_n}\to0\)；若破产则 \(S_{\tau_{-3}}=-3\)：
\[\rho^{-3}\cdot P(\tau_{-3}<\infty) + 0 = 1 \Rightarrow P(\tau_{-3}<\infty) = \rho^3 = \frac{1}{8}\]
\[\boxed{P(\text{永不破产}) = \frac{7}{8}}\]
一般结论：有偏游走（\(p>1/2\)），从 0 出发，破产到 \(-b\) 的概率 \(= (q/p)^b\)。
鞅方法解题模板总结
| 目标 | 使用的鞅 | OST 给出 |
|---|
| 吸收概率（公平） | \(S_n\) | \(\mathbb{E}[S_\tau]=0\)，解比例 |
| 期望停时（公平） | \(S_n^2 - n\) | \(\mathbb{E}[\tau]=ab\) |
| 吸收概率（有偏） | \((q/p)^{S_n}\) | Gambler's Ruin 推广 |
| 期望停时（有偏） | \(S_n - n(p-q)\) | 联立吸收概率 |
| 单边无穷破产 | \((q/p)^{S_n}\)（截断法） | \(P(\text{破产})=(q/p)^b\) |
高频面试陷阱
| 命题 | 对/错 | 原因 |
|---|
| "公平游走必然到达 +1" | ✅ 对 | 一维公平 RW 常返 |
| "公平游走到达 +1 的期望时间有限" | ❌ 错 | \(\mathbb{E}[\tau_1]=+\infty\) |
| "鞅的停时期望等于初始值"（无条件） | ❌ 错 | 需验证 OST 条件 |
| "\(S_n^2\) 是鞅" | ❌ 错 | \(S_n^2-n\) 才是鞅 |
| "\(|S_n|\) 是鞅" | ❌ 错 | 是下鞅（凸函数 of 鞅） |
| "从 \(x\) 出发，边界 \(+a,-b\) 的期望停时是 \(ab\)" | ❌ 错 | 仅从 0；从 \(x\) 出发是 \((a-x)(b+x)\) |
从 \(x\) 出发，边界在 \(+a\) 和 \(-b\) 的通用期望停时：
\[\mathbb{E}[\tau \mid S_0=x] = (a-x)(b+x)\]
验证：\(x=0\) 时 \(=ab\) ✓；\(x=a\) 时 \(=0\) ✓；\(x=-b\) 时 \(=0\) ✓。