鞅和停时定理
鞅
鞅最开始用来研究赌博策略问题，后来引入到数学中。
先考虑这样一个公平赌博局面，每一轮，你都可以下注 xxx 元，然后有 12\frac{1}{2}21 的概率你可以获得 2x2x2x 元，12\frac{1}{2}21 的概率输光。
此时我们提出一个赌博策略，这个策略每次下注多少由前面的输赢情况进行决定。
我们设一组独立随机变量 {Y1,Y2,...}\{Y_1,Y_2,...\}{Y1,Y2,...} 表示前面局面的输赢情况，Yi=1Y_i=1Yi=1 表示第 iii 局赢，Yi=−1Y_i=-1Yi=−1 表示第 iii 局输。
令第 iii 轮下注 bib_ibi 元，容易发现 bib_ibi 由 Y1,Y2,...,Yn−1Y_1,Y_2,...,Y_{n-1}Y1,Y2,...,Yn−1 的取值决定。
令 XiX_iXi 表示第 iii 轮结束后的的钱数，那么有：
Xn=X0+∑i=1biYiX_n=X_0+\sum_{i=1} b_iY_i
Xn=X0+i=1∑biYi
此时我们考虑前 nnn 轮已经结束，计算 Xn+1X_{n+1}Xn+1 ：
E[Xn+1∣{Y1,Y2,...,Yn}]=E[Xn+bn+1Yn+1∣{Y1,Y2,...,Yn}]E[X_{n+1}|\{Y_1,Y_2,...,Y_n\}]=E[X_n+b_{n+1}Y_{n+1}|\{Y_1,Y_2,...,Y_n\}]
E[Xn+1∣{Y1,Y2,...,Yn}]=E[Xn+bn+1Yn+1∣{Y1,Y2,...,Yn}]
此时由于 XnX_nXn 和 bib_ibi 显然已经为定值。
=Xn+bn+1E[Yn+1∣{Y1,Y2,...,Yn}]=Xn=X_n+b_{n+1}E[Y_{n+1}|\{Y_1,Y_2,...,Y_n\}]=X_n
=Xn+bn+1E[Yn+1∣{Y1,Y2,...,Yn}]=Xn
因为 YiY_iYi 间独立。
此时说明了 Xn+1=XnX_{n+1}=X_nXn+1=Xn，通俗解释就是在公平赌博情况下，不存在一种策略使得自己获利。
此时，设 {Yn},{Xn}\{Y_n\},\{X_n\}{Yn},{Xn} 为两个随机变量序列，且 XnX_nXn 可以由 Y1,Y2,...,YnY_1,Y_2,...,Y_nY1,Y2,...,Yn 唯一确定，并且满足：
E[Xn+1∣{Y1,Y2,...,Yn}]=XnE[X_{n+1}|\{Y_1,Y_2,...,Y_n\}]=X_n
E[Xn+1∣{Y1,Y2,...,Yn}]=Xn
则称 XXX 为 YYY 的鞅。
停时
注意到，刚才的研究是一个无限轮的赌博问题，赌徒无法通过调整策略获益，那么考虑赌徒可以自己控制某一轮开始就不赌了呢？这样看上去貌似可以获利（比如获利了马上退出）。
此时引入一个停时，是一个随机变量 TTT，可以通过 X1,X2,...,XnX_1,X_2,...,X_nX1,X2,...,Xn 的取值来决定 TTT 与 nnn 的大小关系，换句话说就是可以通过前面的结果推出是继续还是停止。
那么此时令这个停时的收益是 E[MT]E[M_T]E[MT]，在公平赌博局面中，MMM 是 XXX 的鞅。
我们想知道是否有：
E[MT]=E[M0]E[M_T]=E[M_0]
E[MT]=E[M0]
这若成立，说明赌徒无法通过调整自己的停止时间获得收益（也就是见好就收不会有收益）。
但是对于一般的情况，这不一定成立，但若满足以下三个条件之一，则必然成立：
P{T<∞}=1E[∣MT∣]<∞limn→∞E[∣Mn∣I{T>n}∣]=0P\{ T < \infty \}=1\\
E[|M_T|]<\infty\\
\lim_{n\to \infty} E[|M_n|I_{\{T>n\}}|]=0
P{T<∞}=1E[∣MT∣]<∞n→∞limE[∣Mn∣I{T>n}∣]=0
这是鞅停时定理。
证明先咕着，事实上 OI 中绝大多数题目都满足第二条。
但是最上面提到的公平赌博中的策略不一定满足鞅停时定理。
举个例子，一个经典的赌博策略是初始赌本为 111，赢了就跑，输了赌本翻倍，这样保证了跑的时候一定赢 111 元，连输的概率也不大，被很多赌徒视为必胜法则。
但事实上很明显因为输完就没了，开始赌本 X0X_0X0 必然有限，所以 P{T 再来个例子，初始赌本 111， 赢了赌本减 111，输了赌本加 111，输光为止。 这个策略的高妙之处在于，输会让接下来赢的多，赢会让接下来输的少，换句话说就是一输一赢，一赢一输都可以赚 111 元。 会发现这个策略上面三个条件都不满足。 是说明这个策略能赢吗，显然不是，只能说明鞅停时定理是充分条件而非必要条件。 一个赌徒，初始有若干元，每次赢一元与输一元的的概率都是 1/21/21/2，如果总共输 l1\mathcal l_1l1 元或者赢 l2\mathcal l_2l2 就结束，求赢 l2\mathcal l_2l2 的概率。 如果让赢的概率为 ppp 然后列方程可以得到更加通用的结果，但是这里只做一个小应用。 设 ZiZ_iZi 表示 iii 轮后的收益，由于 ZiZ_iZi 有界，所以满足鞅停时定理，设 ppp 为赢 l2\mathcal l_2l2 的概率。 E[ZT]=E[Z0]pl1+(1−p)l2=0p=l1l2+l2\mathbb E[Z_T]=\mathbb E[Z_0]\\ p\mathcal l_1+(1-p)\mathcal l_2=0\\ p=\frac{\mathcal l_1}{\mathcal l_2+\mathcal l_2 } E[ZT]=E[Z0]pl1+(1−p)l2=0p=l2+l2l1 求 E[T]E[T]E[T] 扯了这么多，来考虑一下和 OI 相关的内容。 OI 中的题一般是，给定一个结束条件，求期望步数。 套路是，对一个局面设一个势能函数 φ(X)\varphi(X)φ(X)，满足 φ(X)=0\varphi(X)=0φ(X)=0 则 XXX 是一个终止状态，并且满足 XXX 后继状态势能会减一。 由于 E[φ(Xn)]−E[φ(Xn+1)]=1E[\varphi(X_n)]-E[\varphi(X_{n+1})]=1E[φ(Xn)]−E[φ(Xn+1)]=1，所以 f(Xn)=φ(Xn)+nf(X_n)=\varphi(X_n)+nf(Xn)=φ(Xn)+n 是 XXX 的一个鞅。 如果满足条件，那么去用一下停时定理。 E[f(XT)]=E[f(X0)]E[φ(XT)]+E[T]=E[φ(X0)]E[f(X_T)]=E[f(X_0)]\\ E[\varphi(X_T)]+E[T]=E[\varphi(X_0)] E[f(XT)]=E[f(X0)]E[φ(XT)]+E[T]=E[φ(X0)] 上面的要求保证了 φ(XT)\varphi(X_T)φ(XT) 为定值，φ(X0)\varphi(X_0)φ(X0) 也为定值，因此直接相减即可。 本质 注意到这类问题有一个暴力 dp 就是设一个状态到结束的期望步数，转移是后继状态加一。 所以构造这个构造函数的过程本质就是在猜测 dp 的答案。 这样看来这个好像挺没用的，相当于一个顺推一个逆推。 套路 这个东西主要还是解决有多个局面，彼此之间不独立的问题。 这样设出每个子局面的势能，求和就是总势能。 然后要去满足差为 111 的条件，列出一次转移的变化值，然后一般可以把每个局面的东西独立开来，解出势能。 其实感觉这个东西和 SG 函数的套路比较类似，但是它是会互相影响的。 CF1025G *3200 注意到一个子局面只和其大小有关，并且最终状态唯一，直接设 f(n)f(n)f(n) 表示有 nnn 个 acquired 点的势能。 此时很多题解直接针对一组 a,ba,ba,b 进行分析，实际上这步是不显然的，因为前面的条件只要求后继状态的和的差，这样分析是保证了一组 a,ba,ba,b 的后继差都是 111，要求更严格，但是不一定解的出。 但事实上由于后面的推导中可以发现 a,ba,ba,b 的势能函数是独立的，所以一般是可以解出的，不过直接枚举所有 a,ba,ba,b 去列式肯定没问题。 f(a)+f(b)−1=af(0)+bf(0)+f(a+1)+f(b+1)2f(a)+f(b)-1=\frac{af(0)+bf(0)+f(a+1)+f(b+1)}{2} f(a)+f(b)−1=2af(0)+bf(0)+f(a+1)+f(b+1) 独立一下，把 −1-1−1 拆开分配给 a,ba,ba,b。 f(a)−12=af(0)+f(a+1)2f(a)-\frac{1}{2}=\frac{af(0)+f(a+1)}{2} f(a)−21=2af(0)+f(a+1) 此时 af(0)af(0)af(0) 很引荐，但是注意到这个势能函数是我们自己设的，与具体是啥局面没啥关系，解出来只要满足那个式子就行，所以 f(0)f(0)f(0) 是啥不重要，直接给个 f(0)=0f(0)=0f(0)=0，然后解一下，得到： f(n)=1−2nf(n)=1-2^n f(n)=1−2n CF1479E *3500 将整体考虑，直接列式，设 S=∑i=1mf(ai)S=\sum_{i=1}^m f(a_i)S=∑i=1mf(ai)： −1+∑i=1mf(ai)=∑i=1main×(f(ai−1)+f(1)+S−f(ai))+aiSn+∑j≠iajn(f(ai−1)+f(aj+1)+S−f(ai)−f(aj))2-1+\sum_{i=1}^m f(a_i)=\sum_{i=1}^m \frac{a_i}{n}\times \frac{(f(a_i-1)+f(1)+S-f(a_i))+\frac{a_iS}{n}+\sum_{j\ne i} \frac{a_j}{n} (f(a_i-1)+f(a_j+1)+S-f(a_i)-f(a_j))}{2} −1+i=1∑mf(ai)=i=1∑mnai×2(f(ai−1)+f(1)+S−f(ai))+naiS+∑j=inaj(f(ai−1)+f(aj+1)+S−f(ai)−f(aj)) 套路性的，把每个 f(ai)f(a_i)f(ai) 相关的单独拿出来。 −ain+f(ai)=ain×f(ai−1)+f(1)+aif(ai)n+n−ainf(ai−1)2+∑j≠iajn×f(ai)+ajnf(ai)+ainf(ai+1)+∑k≠i≠jaknf(ai)2=ai2n(f(1)+ainf(ai)+2n−ainf(ai−1))+n−ai2n(2n−ainf(ai)+ainf(ai+1))-\frac{a_i}{n}+f(a_i)=\\ \frac{a_i}{n}\times \frac{f(a_i-1)+f(1)+\frac{a_if(a_i)}{n}+\frac{n-a_i}{n}f(a_i-1)}{2}+\sum_{j\ne i} \frac{a_j}{n}\times \frac{f(a_i)+\frac{a_j}{n}f(a_i)+\frac{a_i}{n}f(a_i+1)+\sum_{k\ne i\ne j} \frac{a_k}{n}f(a_i)}{2}\\ =\frac{a_i}{2n}(f(1)+\frac{a_i}{n}f(a_i)+\frac{2n-a_i}{n}f(a_i-1))+\frac{n-a_i}{2n}(\frac{2n-a_i}{n}f(a_i)+\frac{a_i}{n}f(a_i+1))\\ −nai+f(ai)=nai×2f(ai−1)+f(1)+naif(ai)+nn−aif(ai−1)+j=i∑naj×2f(ai)+najf(ai)+naif(ai+1)+∑k=i=jnakf(ai)=2nai(f(1)+naif(ai)+n2n−aif(ai−1))+2nn−ai(n2n−aif(ai)+naif(ai+1)) 把 aia_iai 换成 xxx，然后移项得到： −xn=x2n2(nf(1)+(2x−3n)f(x)+(2n−x)f(x−1)+(n−x)f(x+1))−2n=nf(1)+(2x−3n)f(x)+(2n−x)f(x−1)+(n−x)f(x+1)-\frac{x}{n}=\frac{x}{2n^2}(nf(1)+(2x-3n)f(x)+(2n-x)f(x-1)+(n-x)f(x+1))\\ -2n=nf(1)+(2x-3n)f(x)+(2n-x)f(x-1)+(n-x)f(x+1) −nx=2n2x(nf(1)+(2x−3n)f(x)+(2n−x)f(x−1)+(n−x)f(x+1))−2n=nf(1)+(2x−3n)f(x)+(2n−x)f(x−1)+(n−x)f(x+1) 此时递推式从前面两个递推，因此 f(0),f(1)f(0),f(1)f(0),f(1) 可以随意设。 令 f(0)=0,f(1)=−2f(0)=0,f(1)=-2f(0)=0,f(1)=−2，这样得到： 0=(2x−3n)f(x)+(2n−x)f(x−1)+(n−x)f(x+1)0=(2x-3n)f(x)+(2n-x)f(x-1)+(n-x)f(x+1) 0=(2x−3n)f(x)+(2n−x)f(x−1)+(n−x)f(x+1) nnn 很大，无法线性求逆元，因此递推的时候维护分子分母即可，直到要查询的值的时候再求出逆元，复杂度 O(n+mlogn)O(n+m\log n)O(n+mlogn)。 CF850F *2800 其实大概都是一个套路。 设一个颜色势能为 f(ai)f(a_i)f(ai)，总球数为 sss，S=∑f(ai)S=\sum f(a_i)S=∑f(ai)。 −1+S=1s(s−1)(∑i≠jaiaj(f(ai+1)+f(aj−1)+S−f(ai)−f(aj))+∑ai(ai−1)S)−1=1s(s−1)(∑i≠jaiaj(f(ai+1)+f(aj−1)−f(ai)−f(aj)))−ais=1s(s−1)(s−ai)ai(f(ai+1)+f(ai−1)−2f(ai))−s+1s−ai=f(ai+1)+f(ai−1)−2f(ai)-1+S=\\ \frac{1}{s(s-1)}(\sum_{i\ne j} a_ia_j(f(a_i+1)+f(a_j-1)+S-f(a_i)-f(a_j))+\sum a_i(a_i-1) S)\\ -1=\frac{1}{s(s-1)}(\sum_{i\ne j} a_ia_j(f(a_i+1)+f(a_j-1)-f(a_i)-f(a_j)))\\ -\frac{a_i}{s}=\frac{1}{s(s-1)}(s-a_i)a_i(f(a_i+1)+f(a_i-1)-2f(a_i))\\ \frac{-s+1}{s-a_i}=f(a_i+1)+f(a_i-1)-2f(a_i) −1+S=s(s−1)1(i=j∑aiaj(f(ai+1)+f(aj−1)+S−f(ai)−f(aj))+∑ai(ai−1)S)−1=s(s−1)1(i=j∑aiaj(f(ai+1)+f(aj−1)−f(ai)−f(aj)))−sai=s(s−1)1(s−ai)ai(f(ai+1)+f(ai−1)−2f(ai))s−ai−s+1=f(ai+1)+f(ai−1)−2f(ai) 设 g(x)=f(x+1)−f(x)g(x)=f(x+1)-f(x)g(x)=f(x+1)−f(x) −s+1s−x=g(x)−g(x−1)\frac{-s+1}{s-x}=g(x)-g(x-1) s−x−s+1=g(x)−g(x−1) 容易发现这个东西本质上就是对左边的东西做两次前缀和，因此 f(ai)f(a_i)f(ai) 可以简单递推，但是注意到 ∑ai\sum a_i∑ai 很大，推一下式子。 令 f0=f1=0f_0=f_1=0f0=f1=0，cx=−s+1s−xc_x=\frac{-s+1}{s-x}cx=s−x−s+1 。 fs=∑j=1s−1cj(s−j1)=∑j=1s−1−s+1=(s−1)(1−s)f_s=\sum_{j=1}^{s-1} c_j\binom{s-j}{1}=\sum_{j=1}^{s-1} -s+1=(s-1)(1-s) fs=j=1∑s−1cj(1s−j)=j=1∑s−1−s+1=(s−1)(1−s)