526互联

概率期望学习笔记

发布时间 2023-09-07 21:36:23作者: OIer_xxx2022

概率和期望

  • 古典概型：
    • 试验只有有限个基本结果
    • 试验的每个结果出现的可能性是相同的

概率的二项式分布

\(P(X=k)=C_n^kP^k(1-p)^{n-k}\)

期望的可加性

  • 用期望的可加性计算时，注意：不考虑所有其他无关变量（不论是否有影响），只考虑当前变量！

\(E(x+y)=E(x)+E(y)\)

  • 期望的套路题

  • 随机游走模型

  • 期望+动态规划

  • 例：随机生成一个 1~n 的排列，求逆序对个数的期望

期望的线性性

\(P(a_1>a_2)+P(a_2>a_3)+.....+...=\)

\(\frac{n(n-1)}{4}\)

策略：

  • 转化成正常的题意（古典概型）
  • 算贡献，算贡献，算贡献！（线性性）

practice:

P1297[国家集训队]单选错位

  • 线性性

\(ans=\frac{\min({a_i,a_{i+1}})}{a_ia_{i+1}}\)

累加即可

CF1096F

  • 线性性

逆序对分为四种：

  • 给定的数之间的逆序对。

  • 不确定的数之间的逆序对。

  • 给定的数在不确定的数左边的逆序对。

  • 给定的数在不确定的数右边的逆序对。

分类讨论即可

P3802

  • 显然在第七次就触发的概率为\(7! *a_1/N*a_2/(N-1)*a_3/(N-2)...a_7/(N-6)\)

CF280C

  • \[ans=\sum \limits_{i=1}^n {\frac{1}{dep_i}} \]

AGC049A

  • 记\(f_i\)为有多少点能到达i,则本题与上题类似，

\[ans=\sum \limits_{i=1}^n {\frac{1}{f_i}} \]

P5589

  • 答案显然是

\[\sum \limits_{i=1}^n {\frac{1}{f_i}} \]

本题\(n\)的范围是\(10^9\),所以显然不能枚举，但我们可以枚举删除的数，显然此时这个数只需枚举至\(\sqrt n\)即可，再开一个map辅助记录就能做到\(O(\sqrt n)\)的复杂度。

P2221

大佬的题解

  • 几何分布

抛硬币，p 的概率正面，一直抛直到得到正面停止。问期望次数？

\(P(x=k)=(1-p)^{k-1 }p\)

  • 几何分布期望满足一个方程式，（我也不知道这叫啥名字，不过)这其实是“期望步数”这个平均概念的经验性应用。

\(F=1+p*0+(1-p)F\)

\(F=\frac{1}{p}\)

P4316

  • 1

CF24D

P3232

  • 转化为求每条边的期望经过步数

CF802L

  • 先推柿子，再将它转化为一次函数，再进行递推

令\(f_u=a_uf_fa+b_u\)，再代入。解出

\[k_x=\frac{1}{deg_x-\sum \limits_{y \in {son_x}}{k_y}} \]

\[b_x=\frac{\sum \limits_{y \in son_x}{(b_y+dis_x,y)}+dis_{f_{ax}},x}{deg_x-\sum \limits_{y \in son_x}k_y } \]

本题其实还可以利用期望的线性性，设 \(f_u\) 为 \(u\)走到父亲的期望，再进行递推即可，方程为：

\(f_u=w_u+\sum \limits_{v \in son_u}{(w_v+f_v)}\)

多次查询？

多组查询树上两点之间游走的期望和。

令\(g_u\)为父亲到达\(u\)的期望步数，则两点间期望为一段\(f\)的和加\(g\)的和

\(g_u=g_{fa}+f_{fa}-f_u\)

P6835

  • 与上题类似

\[f_i=\frac{1+\sum \limits_{i \to j}{f_i+s_{i-1}-s_{j-1}+1}}{d_i} \]

code

期望和dp

CF518D

  • 设\(f_{t,i}\)为\(t\)秒后有\(i\)个人走上电梯的期望，转移方程为：

\(f_{t,i}=f_{t-1,i-1} \cdot p+(1-p)f_{t-1,i}\)

但需要注意，若上一秒有\(n\)个人，则：

\(f_{t,i}=f_{t-1,i-1} \cdot p+f_{t-1,i}\)

若有\(0\)人

\(f_{t,i}=(1-p)f_{t-1,i}\)

特判即可

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int f=1,w=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')    f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		w=(w<<1)+(w<<3)+(c^48);
		c=getchar();
	}
	return f*w;
}
int n,t;
double p;
double f[2010][2010];
int main(){
	n=read();cin>>p;
	t=read();
	f[0][0]=1.0;
	for(int i=1;i<=t;i++){
		for(int j=0;j<=n;j++){
			if(j==0)	f[i][j]=(1-p)*f[i-1][j];
			else if(j==n){
				f[i][j]=f[i-1][j-1]*p+f[i-1][j];
			}else{
				f[i][j]=f[i-1][j-1]*p+(1-p)*f[i-1][j];
			}
		}
	}
	double ans=0;
	for(int i=0;i<=n;i++){
		ans+=f[t][i]*i;
	}
	printf("%.7f",ans);
	return 0;
}

P1850

  • 设计状态：用\(f_{i,j,k}\)来表示，\(i\)表示时间段，\(j\)表示已经用了\(j\)次机会，\(k\)表示换与不换

可得状态转移方程：

\(f_{i,j,0}=min{(f_{i-1,j,0}+dis1,f_{i-1,j,1}+k_{i-1} \times dis2+(1-k_{i-1})\times dis3)}\)

P1365

  • 显然这道题无法dp，我们可以考虑期望的线性性。

  • 如果无问号：

用\((X,L)\)表示，得分为\(X\)，当前combo长度为\(L\)

如果接上了 $E(X1)=E(X+2L+1) $

如果没接上 \(E(X1)=E(X)\)

如果有问号

$E(X1)=E(X)+E(L)+\frac{1}{2} $

\(E(L1)=\frac{E(L)+1}{2}\)

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
inline int read(){
	int f=1,w=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')    f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		w=(w<<1)+(w<<3)+(c^48);
		c=getchar();
	}
	return f*w;
}
int n;
char s[N];
double f[N];
double len;
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=1;i<=n;i++){
		if(s[i]=='o'){
			f[i]=f[i-1]+2*len+1;
			len++;
		}else if(s[i]=='x'){
			f[i]=f[i-1];
			len=0;
		}else if(s[i]=='?'){
			f[i]=f[i-1]+len+0.5;
			len=(len+1)/2;
		}
	}
	printf("%.4f",f[n]);
	return 0;
}

p4550

  • 与上题类似

P2473

  • \[f_{i,S}=\frac{1}{n}\sum \limits_{x=0}^{n-1}{\max({(f_{i+1,S})+a_x) \times [p_x \subset S]}+f_{i+1,S})} \]

倒叙转移即可。