概率与数学期望笔记-526互联

概率论

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

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

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

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

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

$P(A) \geq 0$
$P(Ω) = 1$
对于两两互斥的事件 $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[x]=\frac{1}{k}\displaystyle\sum_{i=1}^k(f[y_i]+z_i) \]

已知 $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$ 的区间个数，计算数学期望，加入对应的答案。