鞅的停时定理

· · 题解

鞅的停时定理

“鞅”，martingale 用来指一类随机过程，定义如下：

鞅是一种离散时间的随机过程 X_0,X_1,\cdots 满足：

  • E(X_t)<\infty,\forall t\geq0
  • E(X_{t+1}\mid X_0,\cdots X_t)=X_t

根据定义可以得到 E(X_t)=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)。

CF1479E School Clubs

题意

有 n 个学生和 m 个组，每个人在一个组里面，第 i 个组的人数为 a_i。

现在，每天有一个学生（n 个学生中随机的一个）会：

  1. 有一半的概率他会脱离这个组，并且成立一个新的组。
  2. 有一半的概率他会脱离这个组，并且进入一个已经成立的组。他进入第 i 个组的概率为 \frac {a_i} n，他可能会回到原来的组。

求第一次出现所有学生在同一个组的期望天数，对 998244353 取模。

n\leq 4\times10^8

思路

设 \phi(A) 为状态 A 的势能，构造使得 \phi(A_t)-1=\phi(A_{t+1})，设 f(x) 为学生数量为 x 的组的势能函数，则有：

\begin{aligned}\phi(A_t)-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)\\ \end{aligned}

因为我们需要的只是初始状态与停时的势能差，那么将势能具体设为什么都无所谓，所以为了消去常数项我们可以设 f(1)=-2，则：

\begin{aligned}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)\\ \end{aligned}

发现 \phi(A_t)=f(n) （表示局面为只有一个人数为 n 的组）是个常数（知道 f(0) 和 f(1) 可以被表示），那么可以用停时定理。

观察数据范围发现没法存下线性求逆元，也没法每次快速幂求。那怎么办呢？

官方题解的做法将 f 进行差分然后利用快速阶乘算法计算，即：

\begin{aligned}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} \end{aligned}

实际上我们可以直接对对于这个式子 f(x+1)=\frac{3n-2x}{n-x}f(x)-\frac{2n-x}{n-x}f(x-1) 线性递推。因为我们要求的是 E(\phi(A_t)) 和 \phi(A_0)=\sum_if(a_i)，所以我们只在算 m 个 f(a_i) 和 f(n) 的时候快速幂，递推的时候分别维护分子和分母即可。如果你拥有优秀的常数即可通过。

代码

#include<cstdio>
#include<algorithm>
inline int read(){
    int x=0,w=0;char c=getchar();
    while(!isdigit(c)) w|=c=='-',c=getchar();
    while(isdigit(c)) x=x*10+(c^48),c=getchar();
    return w?-x:x;
}
const int mod=998244353;
inline int pow(int a,int b){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod; return ans;}
int n,m,a[1010];
signed main(){
    m=read();
    for(int i=1;i<=m;i++) n+=a[i]=read();
    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)*(2ll*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;
}