鞅与停时定理 最后更新于 2025-04-07 17:06:41

## 离散时间鞅 定义一个随机过程 $(X_0,X_1,X_2,\cdots)$ 为离散时间鞅，当且仅当。 * $E(|X_n|)< \infty$ * $E(X_{n+1}-X_n|X_0,X_1,X_2,\cdots,X_n)=0$ 第二个条件讲人话就是当 $X_0,X_1,X_2,\cdots,X_n$ 都确定时，$E(X_n)=E(X_{n+1})$。 ## 停时 定义一个非负的时间变量 $T$ 为停时，满足任意时刻 $n$ 你可以通过观察 $X_n$ 得到 $n$ 与 $T$ 的关系。（说人话就是你可以知道它有没有结束） 对于一个随机过程 $(X_0,X_1,\cdots)$ 对应的带停时的随机过程 $(Y_0,Y_1,\cdots)$ 满足 $$Y_n = \begin{cases} X_n & n\le T \\ X_T & n\gt T \\ \end{cases}$$ 说人话就是在 $T$ 之后 $X_n$ 不会继续改变，可以发现一个鞅钦定停时后还是一个鞅。 ## 鞅的停时定理 设 $T$ 为鞅 $(X_0,X_1,\cdots)$ 的停时，当且仅当下列三个条件之一成立时 $E(X_T)=X_0$。 * $T$ 几乎有界，即存在 $K$，$P(T\le K)=1$ * $|X_{i+1}-X_i|$ 有界，且 $E(T)$ 有限。 * $X_n$ 几乎有界。 ## 势能函数 设 $T$ 为鞅 $(X_0,X_1,\cdots)$ 的停时，构造势能函数 $\varphi(X_n)$ 满足以下条件： * $E(\varphi(X_{n+1})-\varphi(X_n)|X_0,X_1,X_2,\cdots,X_n)=-1$ * $\varphi(X_T)$ 为常数，且 $\varphi(X_T)\neq \varphi(X_n)$。 换句话就是每次势能期望减 $1$，且 $T$ 时刻的势能唯一。 可知 $E(\varphi(X_T))=E(\varphi(X_0))-T$， 则 $T=E(\varphi(X_T))-E(\varphi(X_0))$。 ## 例题 ### [Company Acquisitions](https://www.luogu.com.cn/problem/CF1025G) 题解： 设 $cnt_u$ 为 $u$ 的儿子个数，令全局的势能函数为 $\sum{\varphi(cnt_u)}$。 考虑两次合并过程，考虑选的点是 $u$ 和 $v$，其儿子个数为 $x$ 和 $y$。 考虑到 $\varphi(x)+\varphi(y)-1=(\varphi(x+1)+y\varphi(0))\times \frac{1}{2}+(\varphi(y+1)+x\varphi(0))\times \frac{1}{2}$ 不妨令 $\varphi(0)=0$，可得 $\varphi(x)+\varphi(y)-1=(\varphi(x+1)+\varphi(y+1))\times \frac{1}{2}$ 不妨令 $\varphi(x)-\frac{1}{2}=\varphi(x+1)\times \frac{1}{2}$。 可得 $\varphi(x)=1-2^x$。 用初始状态 $\sum\varphi(cnt_u)$ 减去结束状态 $\varphi(n)$ 即是答案。 ### 其他例题 [School Clubs](https://www.luogu.com.cn/problem/CF1479E) [Slime and Biscuits](https://www.luogu.com.cn/problem/CF1349D) [Rainbow Balls](https://www.luogu.com.cn/problem/CF850F) 大多情况都能得出一个形同 $af(x-1)+bf(x)+cf(x+1)=d$ 的方程，递推即可得出答案。