鞅 & 停时定理

期望 & 概率

先复习一下期望和概率，设 $P(A)$ 表示 $A$ 时间发生的概率，容易发现 $P(A) \in [0,1]$，并且 $\sum P(A)=1$。（对于同一个事件的不同衍生）

设 $E(A)$ 表示 $A$ 事件发生的期望，设 $P_1(A),P_2(A),\dots,P_k(A)$ 表示 $A$ 这个事件所有衍生的概率，每个衍生有一个权值为 $val_i$，则 $E(A)= P_1(A)val_1+P_2(A)val_2 + \dots P_k(A)val_k$。

我们也可以把 $A$ 看做一个变量，此时 $E(A)$ 表示 $A$ 最后的带权平均值。

例如：$A$ 有 $0.3$ 的概率取 $5$，有 $0.7$ 的概率取 $10$，则 $E(A)=5 \times 0.3+10 \times 0.7=8.5$。

这时设 $x,y$ 为任意实数，则 $E(Ax+y)=xE(A)+y$，$B$ 为另外一个随机变量，则 $E(A+B)=E(A)+E(B)$。

上面这条性质叫做 期望的线性性。

如果随机变量 $X,Y$ 的期望存在，并且 $X,Y$ 相互独立，那么还有 $E(XY)=E(X)E(Y)$，这个可以用上面的 $\sum P(A)=1$​ 展开证明。

鞅

对于一组随机的过程，即一步一步执行的各个状态 $X_0,X_1,X_2,\dots,X_k$，也称作离散型随机变量，不离散的是什么呢，那需要用到积分，因为积分是研究面积，就是连续的变量取值范围之和，此处不展开讨论。

如果 $E(X_{k+1}|X_0,X_1,\dots,X_k)=X_k$，那么我们称 $X$ 这组随机变量为鞅。

上面这句话就是说如果我们根据 $X_0,X_1,\dots,X_k$ 这一些变量的取值，算出 $X_{k+1}$（下一个变量）的期望值恰好等于 $X_k$，那么这就是鞅。

假设我们抛硬币，正面获得 $1$ 的收益，反面获得 $-1$ 的收益，假设当前收益为 $a$，下一步收益的期望也是 $a$，于是抛硬币各个时间段我们的得分构成的一组离散型随机变量就被称作鞅。

同时这也被称作公平博弈游戏。

停时定理

因为 $E(X_{k+1}|X_0,X_1,\dots,X_k)=X_k$，采用数学归纳法我们可得 $E(X_t)=X_0$，这就被称作停时定理。

对于任何一个鞅都有上面的这种定理，可以理解成不论什么时间停止观测（抛硬币）的期望收获都等于自己最开始的代价。

势能函数

对于一组局面 $(A_0,A_1,A_2,\dots,A_k)$，设 $\phi(A_i)$ 表示 $A_i$ 这个局面的一个函数，这个函数本质上是对每个局面规定了一个键值，用于之后的探讨。

例如当前有 $5$ 堆石子，每堆石子的数量分别是 $1,2,3,4,5$，那么这个局面的 $\phi$ 就可以声明为 $f(1)+f(2)+f(3)+f(4)+f(5)$，值得注意的是，$\phi$ 不仅可以是一个值，还可以是另外的函数的取值之和，我们待会要做的就是解出来 $f$，进而算出 $\phi$ 值。

考虑构造一个势能函数，设 $A_t$ 是终止态，我们需要求出到达终止态的期望时间，也就是 $E(t)$。

构造一个 $\phi$ 函数使得 $E(\phi(A_{i+1})| \phi(A_0),\phi(A_1),\dots,\phi(A_i))=A_i-1$，那么我们可以发现：

• $E(\phi(A_i))$ 随着时间减少，可以理解为，随着时间势能会减少。

我们同时需要保证终止态的 $\phi$ 值是唯一的并且是常数，不然我们无法判断哪个是终止态，也就是 $\forall 0 \le i<t,\phi(A_i) \ne \phi(A_t)$。

再次构造序列 $X_i=\phi(A_i)+i$，那么我们发现 $E(X_{n+1} | X_0,X_1,\dots,X_n)=X_n$，即 $X$ 是一个鞅，那么就有 $E(X_t)=E(X_0)$，所以我们得到：
$$E(X_t)=E(\phi(A_t)+t)=E(\phi(A_t))+E(t)$$
所以：
$$E(t)=E(X_0)-E(\phi(A_t))=E(\phi(A_0))-E(\phi(A_t))$$
因为 $\phi(A_t)$ 和 $\phi(A_0)$ 是定值，所以 $E(\phi(A_0))=\phi(A_0),E(\phi(A_t))=\phi(A_t)$。

最后得到：
$$E(t)=\phi(A_0)-\phi(A_t)$$
于是我们只需要知道我们定义的 $\phi$ 函数初始局面的值和最终局面的值就可以算出来初始局面到最终局面的期望时间了。

注意：$\phi$ 函数不是随机变量，只有 $X$ 序列是一组随机变量，因为我们不知道 $A_i$ 和 $i$ 具体是多少。

应用

例题 1

CF1025G-Company Acquisitions

首先按照上面的形式，设 $\phi(A)$ 表示 $A$ 这个局面的势能函数，因为每次操作跟每个节点后接了多少节点有关，设 $i$ 号节点后接了 $a_i$ 个节点，设 $f(i)$ 表示后接 $i$ 个节点的势能函数，那么 $\phi(A)=\sum_{i=1}^n f(a_i)$，这里的 $a_i$ 是在 $A$ 局面下的值。

因为 $E(\phi(A’))=\phi(A)-1$，那么设两次操作的节点分别后接了 $x,y$ 个节点，那么：
$$f(x)+f(y)-1= \frac {1}{2}((f(x+1)+yf(0))+(f(y+1)+xf(0)))$$
因为 $f$ 和 $\phi$ 函数我们都可以自定义，所以设 $f(0)=0$，那么上式变为 $f(x)+f(y)-1=\frac 12(f(x+1)+f(y+1))$。

因为 $f(x)$ 和 $f(y)$ 相互独立，所以 $2f(x)-1= f(x+1)$，归纳一下就是 $f(x)=1-2^x(1 \le x)$​。

$\phi(P_0) = \sum_{i=1}^n f(d_i)$，$\phi(P_t) = f(n-1)$，答案就是 $\phi(P_0)-\phi(P_t)$。

所以这道题 $O(n \log n)$ 做即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include<bits/stdc++.h>
#define ll long long
#define N 505
#define mod 1000000007
using namespace std;
ll n,a[N],x,i,f[N],ans;
inline ll qmi(ll a,ll b,ll p){
	ll res = 1%p,t=a;
	while(b){
		if(b&1) res=res*t%p;
		t=t*t%p;
		b>>=1;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false); 
	cin>>n;
	for(i=1;i<=n;i++) cin>>x,a[max(x,0ll)]++;
	f[0]=0;
	for(i=1;i<=n;i++) f[i]=(qmi(2,i,mod)-1+mod)%mod;
	for(i=1;i<=n;i++) ans=(ans-f[a[i]]+mod)%mod;
	ans=((ans-(1-qmi(2,n-1,mod)))%mod+mod)%mod;
	cout<<ans<<endl;
	return 0;
}

例题 2

CF850F Rainbow Balls

设 $\phi(A)=\sum_{i=1}^n f(a_i)$，然后考虑执行一步之后 $\phi$ 的变化，据此推导出 $f$ 函数的值。

此处 $n$ 为颜色的数量，$a_i$ 为颜色为 $i$ 的球的数量，$m = \sum_{i=1}^n a_i$。

则 $\phi(A)-1 = E(\phi(A’))$，展开一下公式：
$$\sum_{i=1}^m f(a_i)-1= \frac 1{m(m-1)}\sum_{i=1}^m ((a_i(a_i-1) +(m-a_i)(m-a_i-1))f(a_i)+a_i(m-a_i)f(a_i-1)f(a_i+1))$$
化简之后就可以得到：
$$\sum \frac {a_i(m-a_i)}{m(m-1)} (f(a_i-1)+f(a_i+1)-2f(a_i))=-1$$
因为 $\sum \frac {-a_i}{m}=-1$，所以构造 $(f(a_i-1)+f(a_i+1)-2f(a_i))=\frac {-m+1}{m-a_i}$ 就可以满足上述条件。

设 $g(i)=f(i+1)-f(i)$，那么 $g(a_i)-g(a_i-1)=\frac {-m+1}{m-a_i}$，所以递推 $g$ 求出 $f$ 即可，最后输出 $\phi(P_0)-\phi(P_t)$ 即可。

据此不难写出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 100005
using namespace std;
ll n,a[N],m,i,begg,endd,f[N],g[N];
inline ll qmi(ll a,ll b,ll p){
	ll res = 1%p,t = a;
	while(b){
		if(b&1) res=res*t%p;
		t=t*t%p;
		b>>=1;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(i=1;i<=n;i++) cin>>a[i],m+=a[i];
	g[0]=(1+mod-m)*qmi(m,mod-2,mod)%mod;
	for(i=1;i<=1e5;i++){
		g[i]=(g[i-1]+(1+mod-m)*qmi(m-i,mod-2,mod))%mod;
		f[i]=(f[i-1]+g[i-1])%mod;
	}
	for(i=1;i<=n;i++) begg=(begg+f[a[i]])%mod;
	endd=(mod-m*(m-1)%mod)%mod;
	cout<<(begg-endd+mod)%mod<<endl;
	return 0;
}

例题 3

CF1479E School Clubs

依然是设 $\phi(A)=\sum_{i=1}^m f(a_i)$，然后考虑执行一步之后 $\phi$ 的变化，据此推导出 $f$ 函数的值。

这道题的公式推导较为复杂，这里就不赘述了，留作之后复习用。

代码如下，特别注意 $O(4 \times 10^8 \log)$ 是不能过的，要优化到 $O(4 \times 10^8)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include<bits/stdc++.h>
#define ll long long
#define N 1005
#define mod 998244353
using namespace std;
ll n,i,j,now,sum,a[N],begg,endd,now1,now2,now3,inv=1;
inline ll qmi(ll a,ll b){
	ll res = 1,t = a;
	while(b){
		if(b&1) res=res*t%mod;
		t=t*t%mod;
		b>>=1;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(i=1;i<=n;i++) cin>>a[i],sum+=a[i];
	sort(a+1,a+n+1);
	now1=0,now2=-2,now3=((3*sum-2)*now2%mod-(2*sum-1)*now1%mod)%mod;
	for(i=1,now=0;i<=n;i++){
		while(now<a[i]){
			now++;
			if(sum-now+1<sum) inv=inv*(sum-now+1)%mod;
			now1=now2,now2=now3,now3=((3*sum-2*(now+1))*now2-(2*sum-(now+1))*now1%mod*(sum-now)%mod)%mod;
		}
		begg=(begg+now1*qmi(inv,mod-2)%mod+mod)%mod;
	}
	while(now<sum){
		now++;
		if(sum-now+1<sum) inv=inv*(sum-now+1)%mod;
		now1=now2,now2=now3,now3=((3*sum-2*(now+1))*now2-(2*sum-(now+1))*now1%mod*(sum-now)%mod)%mod;
	}
	cout<<(begg-now1*qmi(inv,mod-2)%mod+2*mod)%mod<<endl;
	return 0;
}