概率与期望

猛地发现自己概率与期望这一部分还不怎么会

(准确来说,是只会2n硬核枚举)

所以我决定好好学一学


概率与期望

前置知识

数学期望:在概率论和统计学中,数学期望(mean)(或均值,亦简称期望)是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。它反映随机变量平均取值的大小。(来源:百度百科

全概率公式:公式表示若事件A1,A2,…,An构成一个完备事件组且都有正概率,则对任意一个事件B都有公式成立。

概率与期望

期望的线性性质:有限个随机变量之和的数学期望等于每个随机变量的数学期望之和。比如对于两个随机变量X,Y,E(X+Y)=EX+EY.

全期望知识:类似全概率公式,把所有情况不重复、不遗漏地分成若干类,每类计算数学期望,然后把这些数学期望按照每类的概率加权求和。

(来源:刘汝佳《算法竞赛 入门经典 训练指南》)

以上两种方法,可以帮助我们利用DP来求概率/期望。

 例题

我觉得可能通过做题会更好理解一点,(毕竟刚刚开始学的话看上面的前置知识看得怪难受的),那就让我们先做几道例题吧!

洛谷 P4316 绿豆蛙的归宿

题目描述

给出一个有向无环图,起点为1终点为N,每条边都有一个长度,并且从起点出发能够到达所有的点,所有的点也都能够到达终点。绿豆蛙从起点出发,走向终点。 到达每一个顶点时,如果有K条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 1/K 。 现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?

说明/提示

对于20%的数据 N<=100

对于40%的数据 N<=1000

对于60%的数据 N<=10000

对于100%的数据 N<=100000,M<=2*N

如果按我以前对概率与期望的理解,我大概会这么做:硬核模拟,然后把每次的长度与它的概率乘起来。(这样的复杂度劣得惊人)

但现在不一样了!我们可以用DP来完成这道题目。

我们设f[i]为从i到n点的期望长度,容易想到f[n]=0,而f[1]则是我们的答案。

我们的状态转移方程就是:f[v]=(f[u]+w)/de[v]

这样我们就可以逆推求值了。

你可能会想到一个问题:为什么我们要逆推,而不是直接顺推呢?

我试了一下,发现顺推是错的。

为什么呢?

我们首先这样从正面考虑:

每次我们走过的一段路径,对答案的贡献就是走这条路的概率乘上这条路的长度。

那么走过一段路径的概率是多少呢?就是这条路径上走每一条边的概率之积。

也就是说,如果我们走了一条边,那么它的概率会对走过这条边的以后的路径都产生一个影响。

因此我们逆推的时候,只用乘上走这条边的概率就可以了(可以理解为记上了它对以后路径概率的影响)

但是如果是顺推的话,我乘上走这条边的概率,那么其实没有对走过以后的路径的概率产生影响,而是对我们走过这条边以前的路径概率产生了影响。

(如果这个实在不能理解的话也可以自己手玩一下)

那么我们只需在拓扑排序的过程中顺便完成转移就可以了,时间复杂度O(n+m)。

概率与期望
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #define gc cl==cr&&(cr=(cl=bu)+fread(bu,1,1000000,stdin),cl==cr)?EOF:*cl++
 5 #define gs (ch<'0'||ch>'9') 
 6 using namespace std;
 7 const int N=1e5+111,M=2e5+111;
 8 int n,m,tot;
 9 int hd[N],in[N],de[N];  
10 double f[N];
11 struct edge {
12     int n,v,w;
13 }e[M];
14 queue<int>q;
15 char bu[1000011],*cr,*cl;
16 void r(int &x)
17 {
18     x=0;int f=1;char ch=gc;
19     while( gs ) {if(ch=='-') f=-1;ch=gc;}
20     while(!gs ) x=x*10+ch-'0',ch=gc;
21     x*=f;
22 }
23 void add(int u,int v,int w)
24 {
25     e[++tot]=(edge){hd[u],v,w};
26     hd[u]=tot;
27 }
28 int main()
29 {
30     r(n),r(m);
31     for(int i=1;i<=m;i++)
32     {
33         int u,v,w;
34         r(u),r(v),r(w); 
35         add(v,u,w);
36         de[u]++,in[u]++;
37     }
38     q.push(n);
39     while(!q.empty())
40     {
41         int tt=q.front();q.pop();
42         for(int i=hd[tt];i;i=e[i].n)
43         {
44             int v=e[i].v,w=e[i].w;
45             in[v]--;
46             f[v]+=((double)w+f[tt])/(double)de[v];
47             if(!in[v]) q.push(v); 
48         }
49     }
50     printf("%0.2lf",f[1]);
51     return 0;
52  } 
View Code

(未完待续...)

上一篇:CentOS 8 扩展LVM,更改xfs卷报错解决方法


下一篇:添加页眉Top of page和页脚End of Page