概率与数学期望笔记

概率论

样本点：一个随机试验的某种可能的结果。

样本空间 \(Ω\)：所有可能结果构成的集合

随机事件 \(A\)：在一个给定的样本空间中，样本空间的子集，即由多个样本点构成的集合。

随机变量 \(P(A)\)：把样本点映射为实数的函数，分为离散型、连续型。离散型随机变量的取值为有限或实数。

我们称 \(P(A)\) 为随机事件 \(A\) 发生的概率，概率是对随机事件发生可能性的一个度量方式，是 \([0,1]\) 之间的一个实数。需要满足以下条件：

1. \(P(A) \geq 0\)
2. \(P(Ω) = 1\)
3. 对于两两互斥的事件 \(A_1,A_2,...\) 有 \(\sum P(A_i)=P(\cup A_i)\)

数学期望

简而言之：它是概率和随机变量取值乘积之和。

若随机变量 \(X\) 的取值有 \(x_1,x_2,...\) ，一个随机事件可以表示为 \(X=X_i\) 其概率为 \(P(X=X_i)=p_i\)，则它的数学期望为 \(E(x)=\sum p_i \times x_i\)

例如投掷 \(2\) 枚骰子的实验，两个骰子为 \(x\) 和 \(y\)。

样本空间：共有 \(36\) 个样本点，每个样本点可以写作 \((x,y)\) \(1\leq x,y \leq 6\)

随机变量，取值范围为 \([2,12]\)，\(x+y=X\) 的样本点 \((x,y)\) 构成的子集。

两个骰子掷出的点数的数学期望为 \(7\)

数学期望的线性

满足 \(E(aX+bY)=a \times E(X) + b \times E(Y)\)

因此可以对数学期望进行递推求解

用随机变量 \(X\) 表示掷出一个骰子的点数，显然期望值为 \(E(X)= (1+2+3+4+5+6) \div 6=3.5\)，而 \(2\) 枚骰子的期望为 \(2X=7\)。

例题1 T313040 来到人生的米字路口。

设 \(f[x]\) 为从节点 \(x\) 走到终点所经过的路径的期望长度。

已知 \(f[N]=0\),求 \(f[1]\)。

注意图要从终点到起点求拓扑排序，即在反图上执行。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m,in[100009],res[100009];
double ans[100009];
vector<int> to[100009];
vector<ll> dis[100009];
queue<int> q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		to[v].push_back(u);
		dis[v].push_back(w);
		in[u]++,res[u]++;
	}
	for(int i=1;i<=n;i++){
		if(!in[i])  q.push(i);
	}
	while(!q.empty()){
		int fnt=q.front();
		q.pop();
		for(int i=0;i<to[fnt].size();i++){
			int y=to[fnt][i];
			ans[y]+=(ans[fnt]+dis[fnt][i])*1.0/in[y];
			res[y]--;
			if(res[y]==0)  q.push(y);
		}
	}
	cout<<fixed<<setprecision(2)<<ans[1]<<endl;
	return 0;
}

例题2 弥留之国的Alice。

DAG，有明确的起点和任意终点（并不唯一，小王和大王可以代替某花色）

状态 \(f[a,b,c,d,x,y]\) 来代表 \(4\) 种花色和大小王目前翻开“\(a\) 为黑桃，\(b\) 为红桃，\(c\) 为梅花，\(d\) 为方块，\(x\) 为小王，\(y\) 为大王”时的张数的期望。

当前已经翻开的牌数为 \(sum=a+b+c+d+(x\neq 4)+(y\neq 4)\)。当前没翻开的牌数是 \(54-sum\)，其中有 \(13-a\) 张红桃， \(13-b\) 张黑桃，以此类推。

然后，翻开 \(1\) 张黑桃的概率为 \(\frac{13-a}{54-sum}\)。翻开之后，还需要翻开的张数的期望值是 \(f[a+1,b,c,d,x,y]\)。红桃、梅花、方块同理。

考虑小王大王的情况：

当 \(x=4\) 时，有 \(\frac{1}{54-sum}\) 的概率翻开小王。可以把小王看作某种花色，选择期望值最小的，把小王用作某种花色 \(min_{0 \leq x' \leq 3}\) \(f[a,b,c,d,x',y]\)。大王以此类推。

整体来看，状态转移是四种颜色的期望加上大小王的期望。

\(f[a,b,c,d,x,y]= 1+\)

$\frac{13-a}{54-sum} \times f[a+1,b,c,d,x,y] + $

$\frac{13-b}{54-sum} \times f[a,b+1,c,d,x,y] + $

$\frac{13-c}{54-sum} \times f[a,b,c+1,d,x,y] + $

$\frac{13-d}{54-sum} \times f[a,b,c,d+1,x,y] + $

$\frac{1}{54-sum} \times min_{0 \leq x' \leq 3} fa,b,c,d,x',y + $

\(\frac{1}{54-sum} \times min_{0 \leq y' \leq 3}\) \(f[a,b,c,d,x,y'](y==4)\)

终点时，翻开牌数达到了要求，期望值为 \(0\)，黑桃的张数为 \((a+(x==0)+(y==0))=A\)

把在终点时，记为初始状态

把在起点时，记为目标状态：\(f[0,0,0,0,4,4]\)

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f;
int A,B,C,D;
double f[29][29][29][29][5][5];
double dp(int a,int b,int c,int d,int x,int y){
	if(f[a][b][c][d][x][y])  return f[a][b][c][d][x][y];
	int as=a+(x==0)+(y==0);
	int bs=b+(x==1)+(y==1);
	int cs=c+(x==2)+(y==2);
	int ds=d+(x==3)+(y==3);
	if(as>=A&&bs>=B&&cs>=C&&ds>=D)  return 0;
	int w=54-(as+bs+cs+ds);
	double v=0;
	if(a<13)  v+=(13.0-a)*1.0/w*(dp(a+1,b,c,d,x,y)+1);
	if(b<13)  v+=(13.0-b)*1.0/w*(dp(a,b+1,c,d,x,y)+1);
	if(c<13)  v+=(13.0-c)*1.0/w*(dp(a,b,c+1,d,x,y)+1);
	if(d<13)  v+=(13.0-d)*1.0/w*(dp(a,b,c,d+1,x,y)+1);
	if(x==4){
		double tnp=INF;
		for(int i=0;i<=3;i++){
			tnp=min(tnp,1.0/w*(dp(a,b,c,d,i,y)+1));
		}
		v+=tnp;
	}
	if(y==4){
		double tnp=INF;
		for(int i=0;i<=3;i++){
			tnp=min(tnp,1.0/w*(dp(a,b,c,d,x,i)+1));
		}
		v+=tnp;
	}
	return f[a][b][c][d][x][y]=v;
}
int main(){
	cin>>A>>B>>C>>D;
	if(max(0,A-13)+max(0,B-13)+max(0,C-13)+max(0,D-13)>2){
		cout<<"-1.000";
		return 0;
	}
	double ans=dp(0,0,0,0,4,4);
	cout<<fixed<<setprecision(3)<<ans;
	return 0;
}

例题3 T313075 密码破译。

把 \(N\) 个自然数 \(A_1,A_2,...,A_N\) 都视作 \(31\) 位长的二进制数，对每一位进行处理，设 \(B\) 序列是一个 \(01\) 序列， \(B_i\) 等于 \(A_i\) 的第 \(k\) 位。

根据 \(l,r\) 的选取方式，长度为 \(1\) 的区间的选择概率为 \(\frac{1}{N^2}\)，除此之外其他长的的区间的选出概率为 \(\frac{2}{N^2}\)。那可以依次检查序列 \(B\) 中的每一个数是否为 \(1\)，若是为 \(1\)，则累加 \(2^k \times \frac{1}{N^2}\) 到答案中。再统计，\(and,or,xor\) 的和为 \(1\) 时，且长度 \(\geq 2\) 的区间个数，计算数学期望，加入对应的答案。