鞅与停时定理学习笔记

· · 个人记录

鞅与停时定理

更好的阅读体验

离散时间鞅

定义离散时间鞅为一个时间离散的随机过程 \{X_0,X_1,\cdots\}，使得 \forall n\in \N，均满足：

根据这个，容易得到 E(X_n)=X_0。

停时定理

设 t 为鞅过程 \{X_0,X_1,\cdots\} 的停时，当下面三个条件之一成立时，有 E(X_t)=X_0：

名词解释：

势能函数

对于随机时间序列 \{A_0,A_1,\cdots\}，t 为其停时，终止状态为 A_t，求 E(t)。

构造势能函数 \Phi(A)，满足：

构造序列 X_i=\Phi(A_i)+i，则 E(X_{n+1}-X_n\mid X_0,X_1,\cdots,X_n)=0，即 \{X_0,X_1,\cdots\} 是鞅。

根据停时定理，我们可以得到 E(X_t)=E(X_0)，即 E(t)=E(\Phi(A_0))-\Phi(A_t)。

例题

CF1025G Company Acquisitions

设 f(x) 为跟随有 x 个未选中点的选中点的势能函数，整个局面的势能函数为 \Phi(A)，每个选中点的势能函数的和。

显然每次操作的势能变化量只和随出来的两个点有关，u,v 的儿子数设为 x,y。

为满足 E(\Phi(A_{n+1})-\Phi(A_n)\mid A_0,A_1,\cdots,A_n)=-1，有

f(x)+f(y)-1=\frac{1}{2}(f(x+1)+yf(0))+\frac{1}{2}(f(y+1)+xf(0))

因为我们要对于任意 x,y 成立，所以

f(x)-\frac{1}{2}=\frac{1}{2}f(x+1)+\frac{x}{2}f(0)

取 f(0)=0，则 f(x)=1-2^x。

设停时为 t，注意到 \Phi(A_t)=f(n-1)=1-2^{n-1} 为常数，所以 E(t)=\Phi(A_0)-\Phi(A_t)。

#include<cstdio>
int const mod=1e9+7;
int pow(int x,int y){
    int res=1;
    while(y){
        if(y&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return res;
}
int n,c[510],ans;
int main(){
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(~x)++c[x];
    }
    for(int i=1;i<=n;i++)ans=(ans+1-pow(2,c[i])+mod)%mod;
    ans=(ans+pow(2,n-1)-1)%mod;
    if(ans<0)ans+=mod;
    printf("%d\n",ans);
    return 0;
}

CF850F Rainbow Balls

设 $a_{n,i}$ 为 $n$ 次操作后，第 $i$ 个颜色球的个数。 设 $f(x)$ 为有 $x$ 个球的颜色的势能函数，整个局面的势能函数为 $\Phi(A)=\sum f(a_{i})$。 注意到 $E(\Phi(A_{n+1})\mid A_0,A_1,\cdots,A_n)=E(\Phi(A_{n+1})\mid A_n)$，就等于 $$ \sum\limits_i\frac{a_{n,i}(a_{n,i}-1)}{m(m-1)}\sum\limits_{k}f(a_{n,k})+\sum\limits_i\sum\limits_{j\ne i}\frac{a_{n,i}a_{n,j}}{m(m-1)}\left(f(a_{n,i}+1)+f(a_{n,j}-1)+\sum\limits_{k\ne i,k\ne j}f(a_{n,k})\right) $$ 为满足 $E(\Phi(A_{n+1})-\Phi(A_n)\mid A_0,A_1,\cdots,A_n)=-1$，有 $$ \sum\limits_{k}f(a_{n,k})-1=\sum\limits_i\frac{a_{n,i}(a_{n,i}-1)}{m(m-1)}\sum\limits_{k}f(a_{n,k})+\sum\limits_i\sum\limits_{j\ne i}\frac{a_{n,i}a_{n,j}}{m(m-1)}\left(f(a_{n,i}+1)+f(a_{n,j}-1)+\sum\limits_{k\ne i,k\ne j}f(a_{n,k})\right)\\ \sum\limits_{k}f(a_{n,k})-1=\sum\limits_i\frac{a_{n,i}(a_{n,i}-1)}{m(m-1)}\sum\limits_{k}f(a_{n,k})+\sum\limits_i\sum\limits_{j\ne i}\frac{a_{n,i}a_{n,j}}{m(m-1)}\left(f(a_{n,i}+1)+f(a_{n,j}-1)+\sum\limits_{k\ne i,k\ne j}f(a_{n,k})\right)\\ \sum\limits_{k}f(a_{n,k})-1=\sum\limits_i\left(\frac{a_{n,i}(m-a_{n,i})}{m(m-1)}f(a_{n,i}+1)+\frac{a_{n,i}(m-a_{n,i})}{m(m-1)}f(a_{n,i}-1)+(1-\frac{2a_{n,i}(m-a_{n,i})}{m(m-1)})f(a_{n,i})\right)\\ f(x)-\frac{x}{m}=\frac{x(m-x)}{m(m-1)}f(x+1)+\frac{x(m-x)}{m(m-1)}f(x-1)+\frac{2x^2-2mx-m+m^2}{m(m-1)}f(x)\\ f(x+1)=2f(x)-f(x-1)-\frac{m-1}{m-x} $$ 这东西不太好处理，差分一下 $g(x)=f(x)-f(x-1)$。 $$ f(x+1)-2f(x)+f(x-1)=-\frac{m-1}{m-x}\\ g(x+1)-g(x)=-\frac{m-1}{m-x}\\ g(x+1)=g(x)-\frac{m-1}{m-x}\\ g(x)=g(0)-\sum\limits_{i=0}^{x-1}\frac{m-1}{m-i}\\ f(x)=f(0)+\sum\limits_{i=1}^xg(i)\\ f(x)=f(0)+\sum\limits_{i=1}^x(g(0)-\sum\limits_{j=0}^{i-1}\frac{m-1}{m-j})\\ f(x)=f(0)+xg(0)-\sum\limits_{i=1}^x\sum\limits_{j=0}^{i-1}\frac{m-1}{m-j}\\ f(x)=f(0)+xg(0)-\sum\limits_{j=0}^{x-1}(x-j)\frac{m-1}{m-j}\\ f(x)=f(0)+xg(0)-(m-1)\sum\limits_{j=0}^{x-1}(\frac{x-m}{m-j}-1)\\ f(x)=f(0)+xg(0)+(m-1)(m-x)\sum\limits_{j=0}^{x-1}\frac{1}{m-j}-x(m-1)\\ $$ 取 $f(0)=0,g(0)=m-1$，则 $f(x)=(m-1)(m-x)\sum\limits_{i=0}^{x-1}\frac{1}{m-i}$。 设停时为 $t$，则 $\Phi(A_t)=f(m)+(n-1)f(0)=0$，为常数，所以 $E(t)=\Phi(A_0)-\Phi(A_t)$。 ```cpp #include<cstdio> int const mod=1e9+7; int n,a[2510],f[100010],m,ans; int pow(int x,int y){ int res=1; while(y){ if(y&1)res=1ll*res*x%mod; x=1ll*x*x%mod,y>>=1; } return res; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",a+i),m+=a[i]; f[0]=0; for(int i=1;i<=100000;i++) f[i]=(f[i-1]+pow(m-i+1,mod-2))%mod; for(int i=1;i<=100000;i++) f[i]=1ll*(m-1)*(m-i)%mod*f[i]%mod; for(int i=1;i<=n;i++)ans=(ans+f[a[i]])%mod; printf("%d\n",ans); return 0; } ``` ### [CF1349D Slime and Biscuits](https://www.luogu.com.cn/problem/CF1349D) 设 $a_{n,i}$ 为 $n$ 步后第 $i$ 个人的饼干数量。 设 $f(x)$ 为有 $x$ 个饼干的人的势能函数，整个局面的势能函数为 $\Phi(A)=\sum f(a_{_i})$。 注意到 $E(\Phi(A_{n+1})\mid A_0,A_1,\cdots,A_n)=E(\Phi(A_{n+1})\mid A_n)$。 $$ E(\Phi(A_{n+1})\mid A_n)=\sum\limits_i\sum\limits_{j\ne i}\frac{a_{n,i}}{m(n-1)}\left(f(a_{n,i}-1)+f(a_{n,j}+1)+\sum\limits_{k\ne i,k\ne j}f(a_{n,k})\right)\\ $$ 为满足 $E(\Phi(A_{n+1})-\Phi(A_n)\mid A_0,A_1,\cdots,A_n)=-1$，有 $$ \begin{aligned} \sum\limits_{k}f(a_{n,k})-1&=\sum\limits_i\sum\limits_{j\ne i}\frac{a_{n,i}}{m(n-1)}\left(f(a_{n,i}-1)+f(a_{n,j}+1)+\sum\limits_{k\ne i,k\ne j}f(a_{n,k})\right)\\ \sum\limits_{k}f(a_{n,k})-1&=\sum_i\left(\frac{a_{n,i}}{m}f(a_{n,i}-1)+\frac{m-a_{n,i}}{m(n-1)}f(a_{n,i}+1)+\frac{(m-a_{n,i})(n-2)}{m(n-1)}f(a_{n,i})\right)\\ f(x)-\frac{x}{m}&=\frac{x}{m}f(x-1)+\frac{m-x}{m(n-1)}f(x+1)+\frac{(m-x)(n-2)}{m(n-1)}f(x)\\ f(x+1)&=\left(\frac{m(n-1)}{m-x}-(n-2)\right)f(x)-\frac{(n-1)x}{m-x}f(x-1)-\frac{(n-1)x}{m-x} \end{aligned} $$ 将 $x=0$ 代入可得 $f(1)=f(0)$，所以取 $f(0)=f(1)=0$。 设停时为 $t$，则 $\Phi(A_t)=f(m)+(n-1)f(0)$，为常数，所以 $E(t)=\Phi(A_0)-\Phi(A_t)$。 ```cpp #include<cstdio> int const mod=998244353; int pow(int x,int y){ int res=1; while(y){ if(y&1)res=1ll*res*x%mod; x=1ll*x*x%mod,y>>=1; } return res; } int f[300010],n,m,a[100010],ans; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",a+i),m+=a[i]; for(int i=1;i<300000;i++){ f[i+1]=(1ll*m*(n-1)%mod*pow(m-i,mod-2)%mod-n+2ll+mod)%mod*f[i]%mod; f[i+1]=(f[i+1]-1ll*(n-1)*i%mod*pow(m-i,mod-2)%mod*(f[i-1]+1)%mod+mod)%mod; } for(int i=1;i<=n;i++)ans=(ans+f[a[i]])%mod; ans=(ans-f[m]+mod)%mod; printf("%d\n",ans); return 0; } ``` ### [CF1479E School Clubs](https://www.luogu.com.cn/problem/solution/CF1479E) 套路设出一个状态的势能函数 $\phi(A)$ 为每组的势能相加 $\sum f(a_i)$。 容易注意到 $f(0)=0$。 为满足$E(\Phi(A_{n+1})-\Phi(A_n)\mid A_0,A_1,\cdots,A_n)=-1$，有 $$ \phi(A_t)-1=\phi(A_{t+1})\\ \sum_i\frac {a_i}n(\frac 12(\phi(A_t)-f(a_i)+f(a_i-1)+f(1))+\frac{a_i}{2n}\phi(A_t)+\sum_{j\ne i}\frac {a_j}{2n}(\phi(A_t)-f(a_i)-f(a_j)+f(a_i-1)+f(a_j+1)))\\ -1=\sum_i\frac {a_i}{2n}(-f(a_i)+f(a_i-1)+f(1)+\sum_{j\ne i}\frac {a_j}{n}(-f(a_i)-f(a_j)+f(a_i-1)+f(a_j+1)))\\ -1=-\sum_i\frac {a_i}{2n}f(a_i)+\sum_i\frac {a_i}{2n}f(a_i-1)+\sum_i\frac {a_i}{2n}f(1)-\sum_i\frac {a_i}{2n}\sum_{j\ne i}\frac {a_j}{n}f(a_i)-\sum_i\frac {a_i}{2n}\sum_{j\ne i}\frac {a_j}{n}f(a_j)+\sum_i\frac {a_i}{2n}\sum_{j\ne i}\frac {a_j}{n}f(a_i-1)+\sum_i\frac {a_i}{2n}\sum_{j\ne i}\frac {a_j}{n}f(a_j+1)\\ $$ $$ -\sum_i\frac{a_i}n=\sum_i\frac {a_i}{2n}f(1)-\sum_i\frac {3na_i-2a^2_i}{2n^2}f(a_i)+\sum_i\frac {2na_i-a^2_i}{2n^2}f(a_i-1)+\sum_i\frac {na_i-a^2_i}{2n^2}f(a_i+1) \\ -\frac xn=\frac x{2n}f(1)-\frac{3nx-2x^2}{2n^2}f(x)+\frac{2nx-x^2}{2n^2}f(x-1)+\frac{nx-x^2}{2n^2}f(x+1)\\ $$ 设 $f(1)=-2$。 $$ 0=-\frac{3nx-2x^2}{2n^2}f(x)+\frac{2nx-x^2}{2n^2}f(x-1)+\frac{nx-x^2}{2n^2}f(x+1)\\ f(x+1)=\frac {2n^2}{nx-x^2}(\frac{3nx-2x^2}{2n^2}f(x)-\frac{2nx-x^2}{2n^2}f(x-1))\\ f(x+1)=\frac{3n-2x}{n-x}f(x)-\frac{2n-x}{n-x}f(x-1)\\ f(x+1)=\frac{3n-2x}{n-x}\frac{d_1}{d_2}-\frac{2n-x}{n-x}\frac{s_1}{s_2}\\ f(x+1)=\frac{(3n-2x)d_1}{(n-x)d_2}-\frac{(2n-x)s_1}{(n-x)s_2}\\ f(x+1)=\frac{(3n-2x)d_1s_2-(2n-x)s_1d_2}{(n-x)d_2s_2} $$ 容易发现此时的 $E(A_t)=f(n)$ 为常数，答案即为 $\sum f(a_i)-f(n)$。 线性算即可，可以过，记得开 C++17(64)。 ```cpp #include<cstdio> #include<algorithm> int const mod=998244353; int pow(int x,int y){ int res=1; while(y){ if(y&1) res=1ll*res*x%mod; x=1ll*x*x%mod,y>>=1; } return res; } int n,m,a[1010]; int main(){ scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%d",a+i),n+=a[i]; std::sort(a+1,a+m+1); int ans=0; int s1=0,d1=mod-2,s2=1,d2=1,p1,p2,j=1; while(j<=m&&a[j]==1)ans=(ans+mod-2)%mod,++j; for(int i=1;i<n;i++){ p2=1ll*(n-i)*d2%mod*s2%mod; p1=((3ll*n-2*i)*d1%mod*s2+(mod-1ll)*(2*n-i)%mod*s1%mod*d2)%mod; while(j<=m&&a[j]==i+1)ans=(ans+1ll*p1*pow(p2,mod-2))%mod,++j; s1=d1,s2=d2,d1=p1,d2=p2; } printf("%lld\n",(ans+(mod-1ll)*d1%mod*pow(d2,mod-2))%mod); return 0; } ``` CF 题解给出的做法是将下面的式子用多项式科技优化。 $$ g(x)=f(x+1)-f(x)\\ g(x)=\frac{2n-x}{n-x}g(x-1)\\ g(x)=g(0)\prod_{i=1}^x\frac{2n-i}{n-i}\\ f(x)=-2\sum_{i=0}^{x-1}\prod_{j=1}^i\frac{2n-j}{n-j} $$