因为我比较菜，这里主要侧重在算法竞赛中的应用，一些数学部分没有深入学习，所以有的地方可能不那么严谨 ## 鞅 如果有一个随机变量序列 $M_n$，在已知过去和现在所有信息的前提下，下一步 $M_{n+1}$ 的期望，恰好等于当前 $M_n$ 的已知值，这个序列就叫鞅。 举一个简单抛硬币的例子，赢一次钱 $+1$，输一次 $-1$，并且概率相等，那么当前资金就是鞅。 鞅并不是说每一步都不变，而是说平均不变，即是一个条件期望：$\mathbb E[M_{n+1}\mid\text{历史信息}]=M_n$ 鞅要求的是：对每一种当前局面，下一步平均都公平。在算法题中决策会根据当前状态改变，必须保证自适应之后，期望仍然公平。 ## 停时 停时由已经发生的事情决定。 $$ T=\text{第一次进入终止状态的时刻} $$ 例如： * 第一次走到边界； * 第一次出现某个结构； * 第一次达到目标分数…… 关键要求是：到了第 $n$ 步，你能只根据前 $n$ 步判断是否已经停止，不能看到未来。 ## 停时定理 如果 $M_n$ 是鞅，$T$ 是一个合适的停时，那么： $$ \mathbb E[M_T]=\mathbb E[M_0] $$ 简单来说就是：一个公平的随机过程，不能仅仅通过选择一个合法的停止时机，把期望值变大。 下面三条合起来，是停时定理的一组常用充分条件（具体证明这里就不展开了）： - $\Pr(T<\infty)=1$，在某个有限时刻终止的概率为 $1$ - $\mathbb E|M_T|<\infty$，游戏结束那一瞬间，$M$ 期望必须是一个有限的数值 - $\lim_{n\to\infty}\mathbb E\left[|M_n|I_{\{T>n\}}\right]=0$，到第 $n$ 步还没停止的状态，它们对期望的贡献最终必须趋近于 0 算法竞赛中一般天然满足第一个和第二个，很多时候可以直接用。 ## 应用：构建势能函数求期望步数 设状态为 $X_n$，终止时间为 $T$。我们想求从初始状态出发到终止的期望步数。 定义一个势能函数 $\Phi(x)$，满足： 当 $x$ 为终止状态时 $\Phi(x)=0$ 并且非终止时：$\Phi(x) = \mathbb E[\Phi(y)] + 1$，$x$ 为当前状态，$y$ 为走一步后可能到达的新状态 因此：$M_n=\Phi(X_n)+n$ 在停止前： * 势能平均减 1； * 时间增加 1； 所以 $M_n$ 期望不变，这就证明了 $M_n$ 在停止前是一个鞅。 根据停时定理，游戏结束时的期望等于初始状态的期望 $$ \mathbb E[M_T] = \mathbb E[M_0] $$ 将 $M_T = \Phi(X_T) + T$ 和 $M_0 = \Phi(X_0) + 0$ 展开代入 $$ \mathbb E[\Phi(X_T) + T] = \mathbb E[\Phi(X_0)] $$ 初始状态 $X_0$ 是定值，所以最终得出： $$ \mathbb E[T] = \mathbb E[\Phi(X_0)] - \mathbb E[\Phi(X_T)] $$ 很多题目中终止势能为 $0$，可得 $$ \mathbb E[T]=\Phi(X_0) $$ 要求 $\Phi(X_0)$，在许多算法竞赛题中，这类题目写成普通 DP 是这样的：$E(x)=1+\sum_y p(x\to y)E(y)$ 当完整状态由许多结构相似的部分组成时，可以尝试猜测总势能具有可加形式 $$ \Phi(a_1,\ldots,a_k)=f(a_1)+f(a_2)+\cdots+f(a_k) $$ 由于期望的线性性，可得 $$ \mathbb E\left[\sum_i f(a_i')\right] = \sum_i\mathbb E[f(a_i')] $$ 例题：[CCPC 2025 哈尔滨 H](https://qoj.ac/contest/2575/problem/14821) 题解：[「2025CCPC哈尔滨」H. 匹配题解 - Konn's site](https://konny.eu.org/archives/155/) ## 应用：字符串期望的鞅模型 有一只猴子在键盘上每次独立且等概率敲出一个小写字母，求敲出某个长度为 $len$ 的小写字符串 $S$ 期望要多少次。 我们假设存在无数个赌徒，每当猴子打出第 $n$ 个字母前，会有一个新的赌徒带着 $1$ 枚金币进入赌场，下注当前字符为 $S_1$，如果猜错将血本无归，猜对将获得 $26$ 枚金币，并且他会继续把当前手上所有金币下注猴子敲出的下一个字符（即第 $n+1$ 个字符）为 $S_2$，同理，猜错将输完所有金币，猜对将继续赌博下去。 我们把所有赌徒作为一个整体来看。设 $M_n$ 为第 $n$ 步结束时，所有赌徒手上的总金币数减去总投入成本（每个时刻成本恰好 $+1$），设 $W_n$ 为第 $n$ 个字符出现后，所有未出局赌徒的总资金。 这是一个公平赌博，$M_n=W_n-n$ 是一个鞅，整个系统的停时 $T$ 为第一次敲出完整字符串 $S$ 的时刻 因此 $$ 0=\mathbb E[M_T] =\mathbb E[W_T-T] $$ $$ \mathbb E[T]=\mathbb E[W_T] $$ 最终总资金为能够坚持到最后不破产的赌徒，其入场时间恰好对应字符串 $S$ 的每一个 $Border$（公共前后缀，这里要求包含完整字符串），可得： $$ \mathbb E[T] = \sum_{\ell\in\operatorname{Border}(S)} \frac1{\Pr(S_1S_2\cdots S_\ell)} $$ $\Pr(S_1S_2\cdots S_\ell)$ 表示一次敲出这些字符的概率，在这里为 $\frac{1}{26^{\ell}}$ 如果敲出每个字符的概率不同，每个赌徒仍然带入一个金币，输了后将亏光所有金币，为了赌博公平，获胜后金币数将乘上 $\frac{1}{P(S_i)}$，$i$ 依次为 $1,2,3,\dots,len$。 例题： [2024 上海 CPC H.出金记录](https://codeforces.com/gym/105229/attachments) [P4548 [CTSC2006] 歌唱王国 - 洛谷](https://www.luogu.com.cn/problem/P4548) [P3334 [ZJOI2013] 抛硬币 - 洛谷](https://www.luogu.com.cn/problem/P3334) Loading... 因为我比较菜，这里主要侧重在算法竞赛中的应用，一些数学部分没有深入学习，所以有的地方可能不那么严谨 ## 鞅 如果有一个随机变量序列 $M_n$，在已知过去和现在所有信息的前提下，下一步 $M_{n+1}$ 的期望，恰好等于当前 $M_n$ 的已知值，这个序列就叫鞅。 举一个简单抛硬币的例子，赢一次钱 $+1$，输一次 $-1$，并且概率相等，那么当前资金就是鞅。 鞅并不是说每一步都不变，而是说平均不变，即是一个条件期望：$\mathbb E[M_{n+1}\mid\text{历史信息}]=M_n$ 鞅要求的是：对每一种当前局面，下一步平均都公平。在算法题中决策会根据当前状态改变，必须保证自适应之后，期望仍然公平。 ## 停时 停时由已经发生的事情决定。 $$ T=\text{第一次进入终止状态的时刻} $$ 例如： * 第一次走到边界； * 第一次出现某个结构； * 第一次达到目标分数…… 关键要求是：到了第 $n$ 步，你能只根据前 $n$ 步判断是否已经停止，不能看到未来。 ## 停时定理 如果 $M_n$ 是鞅，$T$ 是一个合适的停时，那么： $$ \mathbb E[M_T]=\mathbb E[M_0] $$ 简单来说就是：一个公平的随机过程，不能仅仅通过选择一个合法的停止时机，把期望值变大。 下面三条合起来，是停时定理的一组常用充分条件（具体证明这里就不展开了）： - $\Pr(T<\infty)=1$，在某个有限时刻终止的概率为 $1$ - $\mathbb E|M_T|<\infty$，游戏结束那一瞬间，$M$ 期望必须是一个有限的数值 - $\lim_{n\to\infty}\mathbb E\left[|M_n|I_{\{T>n\}}\right]=0$，到第 $n$ 步还没停止的状态，它们对期望的贡献最终必须趋近于 0 算法竞赛中一般天然满足第一个和第二个，很多时候可以直接用。 ## 应用：构建势能函数求期望步数 设状态为 $X_n$，终止时间为 $T$。我们想求从初始状态出发到终止的期望步数。 定义一个势能函数 $\Phi(x)$，满足： 当 $x$ 为终止状态时 $\Phi(x)=0$ 并且非终止时：$\Phi(x) = \mathbb E[\Phi(y)] + 1$，$x$ 为当前状态，$y$ 为走一步后可能到达的新状态 因此：$M_n=\Phi(X_n)+n$ 在停止前： * 势能平均减 1； * 时间增加 1； 所以 $M_n$ 期望不变，这就证明了 $M_n$ 在停止前是一个鞅。 根据停时定理，游戏结束时的期望等于初始状态的期望 $$ \mathbb E[M_T] = \mathbb E[M_0] $$ 将 $M_T = \Phi(X_T) + T$ 和 $M_0 = \Phi(X_0) + 0$ 展开代入 $$ \mathbb E[\Phi(X_T) + T] = \mathbb E[\Phi(X_0)] $$ 初始状态 $X_0$ 是定值，所以最终得出： $$ \mathbb E[T] = \mathbb E[\Phi(X_0)] - \mathbb E[\Phi(X_T)] $$ 很多题目中终止势能为 $0$，可得 $$ \mathbb E[T]=\Phi(X_0) $$ 要求 $\Phi(X_0)$，在许多算法竞赛题中，这类题目写成普通 DP 是这样的：$E(x)=1+\sum_y p(x\to y)E(y)$ 当完整状态由许多结构相似的部分组成时，可以尝试猜测总势能具有可加形式 $$ \Phi(a_1,\ldots,a_k)=f(a_1)+f(a_2)+\cdots+f(a_k) $$ 由于期望的线性性，可得 $$ \mathbb E\left[\sum_i f(a_i')\right] = \sum_i\mathbb E[f(a_i')] $$ 例题：[CCPC 2025 哈尔滨 H](https://qoj.ac/contest/2575/problem/14821) 题解：[「2025CCPC哈尔滨」H. 匹配题解 - Konn's site](https://konny.eu.org/archives/155/) ## 应用：字符串期望的鞅模型 有一只猴子在键盘上每次独立且等概率敲出一个小写字母，求敲出某个长度为 $len$ 的小写字符串 $S$ 期望要多少次。 我们假设存在无数个赌徒，每当猴子打出第 $n$ 个字母前，会有一个新的赌徒带着 $1$ 枚金币进入赌场，下注当前字符为 $S_1$，如果猜错将血本无归，猜对将获得 $26$ 枚金币，并且他会继续把当前手上所有金币下注猴子敲出的下一个字符（即第 $n+1$ 个字符）为 $S_2$，同理，猜错将输完所有金币，猜对将继续赌博下去。 我们把所有赌徒作为一个整体来看。设 $M_n$ 为第 $n$ 步结束时，所有赌徒手上的总金币数减去总投入成本（每个时刻成本恰好 $+1$），设 $W_n$ 为第 $n$ 个字符出现后，所有未出局赌徒的总资金。 这是一个公平赌博，$M_n=W_n-n$ 是一个鞅，整个系统的停时 $T$ 为第一次敲出完整字符串 $S$ 的时刻 因此 $$ 0=\mathbb E[M_T] =\mathbb E[W_T-T] $$ $$ \mathbb E[T]=\mathbb E[W_T] $$ 最终总资金为能够坚持到最后不破产的赌徒，其入场时间恰好对应字符串 $S$ 的每一个 $Border$（公共前后缀，这里要求包含完整字符串），可得： $$ \mathbb E[T] = \sum_{\ell\in\operatorname{Border}(S)} \frac1{\Pr(S_1S_2\cdots S_\ell)} $$ $\Pr(S_1S_2\cdots S_\ell)$ 表示一次敲出这些字符的概率，在这里为 $\frac{1}{26^{\ell}}$ 如果敲出每个字符的概率不同，每个赌徒仍然带入一个金币，输了后将亏光所有金币，为了赌博公平，获胜后金币数将乘上 $\frac{1}{P(S_i)}$，$i$ 依次为 $1,2,3,\dots,len$。 例题： [2024 上海 CPC H.出金记录](https://codeforces.com/gym/105229/attachments) [P4548 [CTSC2006] 歌唱王国 - 洛谷](https://www.luogu.com.cn/problem/P4548) [P3334 [ZJOI2013] 抛硬币 - 洛谷](https://www.luogu.com.cn/problem/P3334) 最后修改：2026 年 08 月 04 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏