「方差期望」学习记录

之前联考模拟赛一道题，感觉推式子很干（我又太菜不会推），但是最后很有意思（？）。记录一下。

题目大意

有 (n) 个物体，第 (i) 个出现的概率是 (p_i) 。记其第一次出现时间是 (t_i) 。求 (t_i) 方差的期望值。

分析

开始大力推式子。

[egin{aligned} sigma^2 &= dfrac{1}{n}sumlimits_{i=1}^n t_i^2+overline{t}^2-2t_ioverline{t} \ &= dfrac{1}{n}sumlimits_{i=1}^n t_i^2 + overline{t} (overline{t}-2t_i) \ &= dfrac{1}{n}sumlimits_{i=1}^n t_i^2 - overline{t}^2 \ &= dfrac{1}{n}sumlimits_{i=1}^n t_i^2 - left( dfrac{1}{n}sumlimits_{i=1}^n t_i ight)^2 end{aligned} ]

[operatorname{E}(sigma^2)= dfrac{n-1}{n^2}sumlimits_{i=1}^n operatorname{E}(t_i^2) -dfrac{1}{n^2}sumlimits_{i=1}^nsumlimits_{j=i+1}^n 2 operatorname{E}(t_it_j) ]

注意到 (t_i) 与 (t_j) 不是相互独立的。所以不能拆开算。

因为我们需要计算 (operatorname{E}(t_i^2)) 与 (operatorname{E}(t_it_j)) 。

[egin{aligned} operatorname{E}(t_i^2)=sumlimits_{ige 1} i^2(1-p_i)^{i-1} p_i end{aligned} ]

又因为 (i^2=1+3+5+...)

所以每个 (i) 会对 (1,3,5,7,...) 贡献 ((1-p_i)^{i-1}p_i) 。

逆向考虑，考虑每个位置有多少个 (i) 对其有贡献。

[egin{aligned} operatorname{E}(t_i^2) &= sumlimits_{jge0} (2j+1)sumlimits_{k=j+1}(1-p_k)^{k-1}p_k \ &=sumlimits_{jge0} (2j+1)(1-p_i)^j \ &=2 sumlimits_{jge0} j(1-p_i)^j+sumlimits_{jge0}(1-p_i)^j \ &=2 sumlimits_{jge0} j(1-p_i)^j+dfrac{1}{p_i} end{aligned} ]

不妨设 (s=sumlimits_{jge 0}j(1-p_i)^j) ，则

[s-(1-p_i)s=sumlimits_{jge1}(1-p_i)^j=dfrac{1}{p^i}-1 ]

解得 (s=dfrac{1}{p_i^2}-dfrac{1}{p_i}) ，故 (operatorname{E}(t_i^2)=dfrac{2-p_i}{p_i^2}) 。

接下来是 (2operatorname{E}(t_it_j)) 。

考虑 (2operatorname{E}(t_it_j)=operatorname{E}(t_i^2)+operatorname{E}(t_j^2)-operatorname{E}((t_i-t_j)^2)) 。

变相理解，记第 (i) 个物品和第 (j) 个物品出现时间差的平方的期望。不妨设 (f_{i,j}) 表示 (i) 比 (j) 前出现的概率。

所以 (operatorname{E}((t_i-t_j)^2)=f_{i,j}operatorname{E}(t_j^2)+f_{j,i}operatorname{E}(t_i^2)) ，

得

[egin{aligned} 2operatorname{E}(t_it_j) & =operatorname{E}(t_i^2)+operatorname{E}(t_j^2)-f_{i,j}operatorname{E}(t_j^2)-f_{j,i}operatorname{E}(t_i^2) \ &= (1-f_{i,j})operatorname{E}(t_j^2)+(1-f_{j,i})operatorname{E}(t_i^2) \ &= f_{j,i}operatorname{E}(t_j^2) + f_{i,j}operatorname{E}(t_i^2) end{aligned} ]

考虑 (f_{i,j}) 的转移

[f_{i,j}=sumlimits_{k ge 1} (1-p_i-p_j)^{k-1}p_i=dfrac{p_i}{p_i+p_j} ]

所以得

[2operatorname{E}(t_it_j)=dfrac{p_i}{p_i+p_j}operatorname{E}(t_i^2)+dfrac{p_j}{p_i+p_j}operatorname{E}(t_j^2) ]

其中 (p_i+p_j) 的逆元用类似前缀和一样的求法预处理。

复杂度 (mathcal{O}(n^2)) 。

(10^5) 做法要多点插值，暂鸽。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const ll N=5000+5;
const ll Mod=998244353;
ll n,sum,inv,a[N],p[N],E[N];
ll ans1,ans2,iv[N],pre[N][N],ipre[N][N];
ll qpow(ll x,ll k)
{	ll res=1;
	while(k)
	{	if(k&1)res=res*x%Mod;
		x=x*x%Mod;
		k>>=1;
	}
	return res;
}
ll f(ll x,ll y)
{	if(x>y)return ipre[y][x]*pre[y][x-1]%Mod*p[x]%Mod;
	return ipre[x][y]*pre[x][y-1]%Mod*p[x]%Mod;
}
int main()
{	freopen("card.in","r",stdin);
	freopen("card.out","w",stdout);
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)
	{	scanf("%lld",&a[i]);
		sum=(sum+a[i])%Mod;
	}
	inv=qpow(sum,Mod-2)%Mod;
	for(ll i=1;i<=n;i++)
	{	p[i]=a[i]*inv%Mod;
		iv[i]=qpow(p[i],Mod-2);
		E[i]=(2-p[i]+Mod)%Mod*iv[i]%Mod*iv[i]%Mod;
	}
	for(ll i=1;i<=n;i++)ans1=(ans1+iv[i])%Mod;
	ans1=ans1*qpow(n,Mod-2)%Mod;
	printf("%lld
",ans1);
	for(ll i=1;i<=n;i++)
	{	pre[i][i]=1;
		for(ll j=i+1;j<=n;j++)
			pre[i][j]=(p[i]+p[j])%Mod*pre[i][j-1]%Mod;
		ipre[i][n]=qpow(pre[i][n],Mod-2);
		for(ll j=n-1;j>=i;j--)
			ipre[i][j]=(p[i]+p[j+1]%Mod)*ipre[i][j+1]%Mod;
	}
	inv=qpow(n,Mod-2)%Mod;
	for(ll i=1;i<=n;i++)
	{	ans2=(ans2+(n-1)*inv%Mod*inv%Mod*E[i]%Mod)%Mod;
		for(ll j=i+1;j<=n;j++)
		{	ans2=(ans2-f(i,j)*E[i]%Mod*inv%Mod*inv%Mod+Mod)%Mod;
			ans2=(ans2-f(j,i)*E[j]%Mod*inv%Mod*inv%Mod+Mod)%Mod;
		}
	}
	printf("%lld
",ans2);
	return 0;
}