概率与期望 ·expectation

概率的定义

概率, 又称“或然率”、“几率”, 它是对一个随机事件的可能性的大小所作的数量方面的估计。

一个事件 A 出现的概率, 是 A 可能出现的情况与全部可能情况的比率。其计算公式为:

P(A)=m(A 可能出现的情况)/n(所有可能的情况)

独立事件:如果 A 和 B 独立,则 P(AB)=P(A)P(B)。

离散期望

定义

设 P(x) 是一个离散概率分布函数,自变量的取值范围为 。其期望被定义为:

性质

期望函数是线性函数(加性函数):

离散函数的期望即为其自变量的期望与自变量的概率之积的总和:

函数的期望不等于期望的函数。即

如果事件 x 和事件 y 相互独立,则

不论 x,y 是否独立, 恒成立。

小练习

Exercise 1

简单数学期望 - 掷骰子

突然发现,骰念 tou 而不是 shai……

问 6 面骰子掷出数字 6 的期望次数?

毫不犹豫:期望次数 6 次。

的确是这样,可是这样的过程未免太感性。我们设法以此构建一个数学模型:

E 表示掷到 6 的期望次数。根据期望的定义,不同的事件的概率与权值之积的和:

  • 如果掷一次就掷到了 6,那么你相当于掷了 1 次,而这件事发生的概率是 1/6.

  • 否则,相当于你又得掷 E 次,才能期望掷到 6。则你掷了 E+1 次,事件发生概率为 5/6.

  • 所以

  • 解方程,得 .

这个构建的数学模型带有递归的色彩,而在考虑期望值时,我们会假设期望值是已知的,并将其用于构建关系式。(事实上这有点像你假装知道 E 的值,然后你抽了风去构建一个和 E 有关等式,最后发现这个等式在 E 未知的情况下同样有效)

考虑一个升级版的问题:一个 n 面的骰子,求掷出每一个面的期望次数?

这时需要记录一些数据了。定义 E[i] 表示已经掷出 i 面,还需要的期望次数。

考虑这一次掷骰子:

  • 如果掷到了已经有的面,概率为 , 还需要的期望次数为 .
  • 如果掷到了没掷到过的面,概率为 , 还需要的期望次数为 .
  • 另外,这一次你掷了一次,也要算入一次。
  • 所以 . 变换一下,得到
  • 显然,这是一个可递推的式子,求解即可。
  • 边界条件 ,目标 .

这个大概是笔者冈刂学期望时写的部分。

Exercise 2

每次随机一个 [1,n] 的数,期望几次随机出全部的数

定义 表示已经随了 i 个出来,要随出全部的数的期望。显然 f[n]=0.

Exercise 2.5

LG4550 收集邮票

有 n 种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且买到的邮票究竟是 n 种邮票中的哪一种是等概率的,概率均为 1/n。但是由于凡凡也很喜欢邮票,所以皮皮购买第 k 张邮票需要支付 k 元钱。现在皮皮手中没有邮票,皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

概率题真的很仙。我们知道邮票的价格和购买的次数有关。于是定义 表示已有 i 种邮票,得到所有种类的邮票的期望购买次数。显然 f[n]=0.

那么定义 表示已有 i 种邮票,得到所有种类的邮票的期望购买价格。

每买一次增加一元钱,相当于之后的所有购买都加一元, 然后当前购买加一元。之后购买了 f 次,所有增加 f。

#include<cstdio>
using namespace std;
const int N=1e4+4;
int n;
double f[N],g[N];
int main(){
    scanf("%d",&n);
    for(int i=n-1;i>=0;i--){
        f[i]=f[i+1]+1.0*n/(n-i);
        g[i]=1.0*i/(n-i)*f[i]+g[i+1]+f[i+1]+1.0*n/(n-i);
    }
    printf("%.2lf\n",g[0]);
    return 0;
}

Exercise 3

一条长度为 n 的链,从一端随机游走到另一端的期望次数。

表示处在位置 i,随机游走到位置 n 的期望次数。f[n]=0。目标:f[0]。

在列方程的过程中,你发现位置 0 的方程略有差别

于是就有了这样一个手推的过程

于是你猜测

要证明这个也很简单,做一下数学归纳就好了。

对于 ,有 成立。

假设 的情况都成立,那么就有

得证。于是

非常巧合的结论。

Exercise 4

一个 n 个点的完全图,从 S 走到 T 的期望时间。

这个问题的特殊之处在于,它是完全图,这意味着任意点对间的期望时间其实是一样的!

于是从一个点出发,你有 的概览走到另一个点,有 的概率走到终点。方程就像这样

LG4316 绿豆蛙的归宿

线性期望题

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

设到达点 i 的概率为

对于入度为 0 的点 v, .

从当前点 v 出发,到达下一个点的概率是 p(v)*(1/v 的出度)

而走当前路径的期望即为路径的权值乘上概率。

根据期望的线性,最后将结果相加即可

利用拓扑排序

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;

int id[N],od[N];
struct qxx{int nex,t,v;};
qxx e[2*N];
int head[N],cnt;
void add_path(int f,int t,int v){e[++cnt]=(qxx){head[f],t,v},head[f]=cnt;}
queue<int> q;
double p[N],ans;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,a,b,c;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        add_path(a,b,c);
        ++od[a],++id[b];
    }
    for(int i=1;i<=n;i++){
        p[i]=0;
        if(!id[i])q.push(i),p[i]=1;
    }
    while(!q.empty()){
        int k=q.front();q.pop();
        double pk=p[k]/od[k];
        for(int i=head[k];i;i=e[i].nex){
            --id[e[i].t];
            p[e[i].t]+=pk;// 到达这个点的概率
            ans+=e[i].v*pk;// 路径期望累加
            if(id[e[i].t]==0)q.push(e[i].t);
        }
    }
    printf("%.2lf",ans);
    return 0;
}

NOIP2016 换教室

离散期望题

对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中,有 2n 节课程安排在 n 个时间段上。在第 个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室 上课,而另一节课程在教室 进行。

在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的 n 节安排好的课程。如果学生想更换第 i 节课程的教室,则需要提出申请。若申请通过,学生就可以在第 i 个时间段去教室 上课,否则仍然在教室 上课。

由于更换教室的需求太多,申请不一定能获得通过。通过计算,牛牛发现申请更换第 i 节课程的教室时,申请被通过的概率是一个已知的实数 ,并且对于不同课程的申请,被通过的概率是互相独立的。

学校规定,所有的申请只能在学期开始前一次性提交,并且每个人只能选择至多 m 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室,而不能根据某些课程的申请结果来决定其他课程是否申请;牛牛可以申请自己最希望更换教室的 m 门课程,也可以不用完这 m 个申请的机会,甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行,所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有 v 个教室,有 e 条道路。每条道路连接两间教室,并且是可以双向通行的。由于道路的长度和拥堵程度不同,通过不同的道路耗费的体力可能会有所不同。 当第 节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的路径前往下一节课的教室。

现在牛牛想知道,申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小,请你帮他求出这个最小值。

期望 +DP

注意,并不是每一个教室都要考虑换还是不换。只有申请换教室的才考虑成功和失败的概率,没有申请的就不考虑。

定义 到第 i 个时段,申请更换了 j 次,目前在 C(0) 还是 D(1) 教室。

考虑

考虑第 个教室没有申请,则到达这个教室的概率为 1

个教室没有申请

若第 个教室没有申请,那么走的路径将是 ,概率为 1。期望为 c_i

个教室申请

个教室申请换,则分两种情况:即考虑

  • 申请成功:概率为 ,则期望为 c_i
  • 申请失败:概率为 ,则期望为 c_i
  • 总期望: c_i c_i

的总期望

上种情况者之间取最小值,即为

考虑

考虑第 个教室申请

申请失败

个教室申请失败,概率为 k_i$$

  1. 个教室没有申请,到达第 个教室的概率为 1。期望为 k_i c_i

  2. 个教室申请,考虑 。如果申请成功:概率为 ,则期望为 c_i ;如果申请失败:概率为 ,则期望为 c_i

总期望:结合第 个教室申请失败的概率,期望为 k_i c_i k_i c_i

申请成功

个教室申请成功,概率为

  1. 个教室没有申请,到达第 个教室的概率为 1,期望为 $$k_i$dis[$d_i$,c_{i-1}]$

  2. 个教室申请,考虑 。如果申请成功:概率为 ,则期望为 c_i ;如果申请失败:概率为 ,则期望为 c_i

总期望:结合第 个教室申请成功的概率,期望为 $$k_i$k_{i-1}dis[$c_i$,d_{i-1}]+$k_i$(1-k_{i-1})dis[$c_i$,c_{i-1}]$

总期望

结合第 个教室没有申请的两个情况(即 4.2.1.1 和 4.2.2.1),总的期望为

结合第 个教室有申请的 2 种情况(即 4.2.1.2 和 4.2.2.2)总的期望为

上两者取最小值即为

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2003,V=302,M=302;
int n,m,v,e;
int c[N],d[N];
int dis[V][V];
double p[N];
double f[N][N][2];
//f[i,j,p] 到第 i 个时段,更换了 j 次,目前在 C(0) 还是 D(1) 教室
int main(){
    //freopen("p1850.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<=n;i++)scanf("%d",&d[i]);
    for(int i=1;i<=n;i++)scanf("%lf",&p[i]);

    for(int i=1;i<=v;i++)
        for(int j=1;j<i;j++)
            dis[i][j]=dis[j][i]=800000000;

    for(int i=1,x,y,z;i<=e;i++)
        scanf("%d%d%d",&x,&y,&z),dis[x][y]=dis[y][x]=min(dis[x][y],z);

    for(int pi=1;pi<=v;pi++)
        for(int i=1;i<=v;i++)
            for(int j=1;j<=v;j++)
                if(dis[i][j]>dis[i][pi]+dis[pi][j])
                    dis[i][j]=dis[i][pi]+dis[pi][j];

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            f[i][j][0]=f[i][j][1]=800000000;

    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=m&&j<=i;j++){
            f[i][j][0]=min(f[i-1][j][0]+dis[c[i]][c[i-1]],
                f[i-1][j][1]+p[i-1]*dis[c[i]][d[i-1]]
                            +(1-p[i-1])*dis[c[i]][c[i-1]]
            );
            if(j>0)f[i][j][1]=min(f[i-1][j-1][0]+(1-p[i])*dis[c[i]][c[i-1]]
                            +p[i]*dis[d[i]][c[i-1]],
                f[i-1][j-1][1]+p[i-1]*p[i]*dis[d[i]][d[i-1]]
                            +(1-p[i-1])*p[i]*dis[d[i]][c[i-1]]
                            +p[i-1]*(1-p[i])*dis[c[i]][d[i-1]]
                            +(1-p[i-1])*(1-p[i])*dis[c[i]][c[i-1]]
            );
        }
    }
    double ans=800000000;
    for(int i=0;i<=m;i++){
        ans=min(ans,f[n][i][0]);
        ans=min(ans,f[n][i][1]);
    }
    printf("%.2lf",ans);
    return 0;
}

参考文献

【期望、方差、协方差及相关系数的基本运算】

面试中的概率题 - 数学期望(1)


 上一篇
字典树 字典树
简介字典树,英文名Trie。顾名思义,就是一个像字典一样的树。先放一张图: 可以发现,这棵字典树用边来代表字母,而从根结点到树上某一结点的路径就代表了一个字符串。举个例子, 表示的就是字符串 caa。 结
2018.10.01
下一篇 
分块入门 分块入门
引言时隔很久过来填坑了。其实分块就是暴力,其本质仍是对维护信息的割裂与整合归一 线性分块在线性结构上维护信息,我们尝试用分块处理。这种分块将结构分割为连续的几段,在维护段内的信息再整合为要查询的信息。形式化地说,我们把长度为 的序
2018.10.01
  目录