碎碎念。
嘿嘿，我的嘿嘿。今天怎么这么摆。
什么？你以为这篇文章是鲜花？这是压缩诈骗。
建议大家都学点新东西，不然就会像我一样在 NOIP 模拟赛中被 T2 放 Powerful Number 筛的出题人创死。
我尝试把开头写长一点让预览看不到下面的内容，这样你就要点进来看了，嘿嘿，我是不是很机智。
让我猜猜你随机读鲜花的停时的期望是多少呢？（记住这个问题，下面要考。）
其实这是一篇正经的科普文章。
一些约定
- 随机过程：对一个参数集随机的一组变量集合，参数集通常是时间 \(T\)，若 \(\forall t\in T\)，\(X_t\) 为随机变量，那么 \(\{X_t|t\in T\}\) 就是一个随机过程。
- 条件概率：\(P(A|B)\)，即 \(A\) 事件在 \(B\) 事件条件下发生的概率。
- 条件期望：\(E(A|B)\)，类比条件概率，即 \(A\) 事件在 \(B\) 事件条件下的期望。
- 几乎一定：事件 \(A\) 几乎一定发生，当且仅当 \(P(A)=1\)。\(A\) 不发生的情况集合可能非空，但它们的概率为 \(0\)。样本空间有限时，“几乎一定”和“一定”通常没有区别；但是当样本空间无限时，就有区别了。比如 \([0,1]\) 中均匀随机一个实数 \(x\)，则 \(P(x>1)=1\)，可以说选出的 \(x\) 几乎一定大于 \(0\)，但理论上确实可以存在 \(x=0\) 的样本。
离散时间鞅
一个离散时间鞅为一个以时间为参数集合的随机过程，即随机过程 \(\{X_0,X_1,\cdots \}\)，满足对于任意时刻 \(n\in \mathbb{N}\)，均有：
- \(E(|X_n|)<∞\)。
- \(E(X_{n+1}-X_n|X_{0},X_{1},\cdots ,X_{n})=0\)。
第二个条件看起来不知所云，其实意思就是当 \(X_{0},X_{1},\cdots ,X_{n}\) 已经确定时，\(X_{n+1}\) 的期望等于 \(X_n\)。类似一个公平赌博游戏，若我们已经得到了前 \(n\) 场赌博后你所拥有的财产（观测值），那么要求第 \(n+1\) 场的观测值的期望等于第 \(n\) 场的观测值（不亏不赚），才能满足公平赌博游戏的定义（所以公平赌博游戏其实差不多就是鞅www）。
同时不难发现鞅的线性加减、增减常数都不影响其鞅的性质。
停时
关于随机过程 \(\{X_{0},X_{1},\cdots\}\) 的停时为一个非负的随机变量 \(T\)（可能为 \(∞\)，即操作无限进行），满足对任意时刻 \(n\)，你可以通过观测 \(X_0,X_1,\cdots,X_{n}\) 的取值得出 \(n\) 和 \(T\) 的大小关系/等量关系。即 \([n=T],[n<T],[n>T]\) 三个随机变量的取值仅与 \(X_{0},X_{1},\cdots ,X_{n}\) 有关。
对于随机过程 \(\{X_0,X_1,\cdots\}\)，对应带停时为 \(T\) 的随机过程 \(\{\overline {X_0},\overline {X_1},\cdots\}\) 的定义为：
即 \(\{\overline {X_{1}},\overline {X_{2}},\cdots \}\) 为将 \(\{X_0,X_1,\cdots \}\) 在 \(T\) 之后的项全部覆盖为 \(T\) 后的随机过程，可以看作在时刻 \(T\) 终止随机操作。（所以停时也可以理解为操作的停止时间。）
由于 \(\overline{X_n}\) 中 \(n\le T\) 时 \(\overline{X_n}=X_n\) 期望不变，而 \(n>T\) 时我们钦定它期望不变，所以满足鞅期望观测值不变的性质，所以 \(\{\overline{X_1},\overline{X_2},\cdots\}\) 也是一个鞅。
鞅的停时定理
设 \(T\) 为离散时间鞅 \(\{X_0,X_1,\cdots\}\) 的停时，且 \(T\) 几乎一定有限，当下面三个条件之一成立时，有 \(E(X_T)=E(X_0)\)
- \(T\) 几乎一定有界，即存在常数 \(K\)，\(P(T\le K)=1\)。
- \(E(|X_{i+1}-X_i|)\) 几乎一定有界，且 \(E(T)\) 有限，即存在常数 \(K\) 使得 \(P(E(|X_{i+1}-X_i|)\le K)=1\)
- \(\overline{X_i}\) 几乎一定有界，即存在常数 \(K\) 使得 \(P(|\overline{X_i}|\le K)=1\)
为了帮助理解，给出下面若干例子：
- 数轴上从 \(0\) 开始随机向右游走，每次走 \(1\) 或 \(2\) 的距离，走过一个常数 \(K\) 后停止。那么 \(T\) 一定有界，满足第一个条件。
- 从 \([0,1]\) 中随机选择实数，直到选出非 \(0\) 数为止。\(T\) 几乎一定有界，满足第一个条件。
- 数轴上从 \(0\) 开始随机左右游走，每次走 \(1\) 的距离，走到区间 \([-K,K]\)（\(K\) 为常数） 边界后停止。由于 \(\overline{X_n}\) 有界 \([-K,K]\)，满足第三个条件。
- 我们回到开头那个问题（还记得吗？）。你在读这篇文章，假设你每次随机向目前阅读位置的后面跳一个位置然后开始读，读完为止。那么很显然 \(\overline{X_n}\) 有界（文章长度），也满足第三个条件。
- 第二个条件是大多数题目所包含的（比如让你求停时的期望，每次操作带有的变化量有界等等）。
势能分析
其实前面这么一大堆定义、性质，统统不用记。
考虑经典模型：
假设现在有随机过程 \(\{X_0,X_1,\cdots \}\)，\(T\) 为其停时，给定初始状态 \(X_0\)，终止状态 \(\overline{X_T}\)，求 \(E(T)\)。
考虑构造势能函数 \(\varphi(X)\)，同时描述了时间和状态两个变量：
- \(E(\varphi(X_{n+1})-\varphi(X_{n})|X_{0},X_{1},\cdots,X_{n})=-1\)
- \(\varphi(X_{T})\) 为常数，且 \(\nexists i<T,\varphi(X_{i})=\varphi(X_T)\)
第一个限制保证了每个时刻，势能的变化量期望为 \(-1\)，那么 \(E(\varphi(X_0))-E(\varphi(X_n))=n\)；第二个限制保证了末状态势能唯一，也就是保证末状态为第一个满足终止条件的状态的需要。
构造 \(Y_i=\varphi(X_i)+i\)，根据定义，\(\{Y_0,Y_1,\cdots\}\) 为一个离散时间鞅。那么根据停时定理，可以得到 \(E(Y_T)=E(Y_0)\)，即 \(E(\varphi(X_T)+T)=E(\varphi(X_0))\)，即 \(E(T)=E(\varphi(X_0))-E(\varphi(X_T))\)，根据定义右边两项都是常数值，于是就能方便地求出 \(E(T)\)。
如何准确地构造势能函数，一般构造关于题面中状态有关量为自变量的函数，然后根据第一条限制解函数方程/递推。
你可能在高中物理课听说过势能是相对的，这允许我们对于一些常数 \(C\)，钦定 \(f(C)\) 的值。
CF1025G Company Acquisitions
定义整个局面 \(X\) 的势能函数为 \(\varphi(X)\)，由于我们只关心每个点跟在屁股后面的点的个数，定义单个点 \(u\) 的势能为 \(f(c_u)\)，\(c_u\) 为局面 \(X\) 下跟在 \(u\) 后的点的个数，\(f\) 为关于 \(c\) 的函数，令 \(\varphi(X)=\sum\limits_{u}f(c_u)\)。
则 \(X\to X'\) 的势能变化量只和每次随机选出来的两个点 \(u,v\) 的 \(c\) 有关，令 \(c_u=x,c_v=y\)：
我们令 \(f(0)=0\)：
要求对任意 \(x,y\) 均成立，那么一个简单的想法是直接拆两半：
结合 \(f(0)=0\) 得到：
那么答案就是 \(\left(\sum\limits_{u}f(c_u)\right)- f(n)\)，复杂度 \(O(n)\)。
CF1479E School Clubs
我们只关心每个组内的人数，所以依旧令局面 \(X\) 的势能值 \(\varphi(X)=\sum\limits_{i=1}^{m}f(a_i)\) 为各个组势能之和，一组的势能定义为其人数 \(a_i\) 的 \(f\) 值。
每次操作，将随机发电的那个人所在的组拎出来，设为第 \(i\) 组：
- 这个人新开了一个组：\(\varphi(X')=\varphi(X)-f(a_i)+f(a_i-1)+f(1)\)。
- 这个人回到了原来的组：\(\varphi(X')=\varphi(X)\)。
- 这个人跑到了其他组，设为 \(j\) 组：\(\varphi(X')=\varphi(X)-f(a_i)-f(a_j)+f(a_i-1)+f(a_j+1)\)
然后就是一些 Dirty Work 了：
不妨设 \(f(1)=-2\)：
然后 \(O(n)\) 递推 \(f\) 的值即可。这是能过的。