概率/数学期望总结

概率：对随机事件发生可能性的度量。

期望：概率加权平均。

其实我觉得这东西挺抽象的，以前考试都是直接跳过。最近入了下门，感觉还是挺好理解的。

首先讲下它的定义：

$$E=\sum_{i=1}^np_ix_i$$

这个式子是什么意思呢？其中$p_i$表示$i$这个事件发生的概率，$x_i$表示事件的权值。你可以理解成一种加权的平均数。

举个例子：对于这个图

我们假设一个人从1点开始，每次随机选一个点往前走，每到一个点就把它的权值加上，我们要求走的期望权值。

我们可以很明显的看出来一共只有4种情况。

$1->2->4:14$
$1->2->5:11$
$1->3->6:19$
$1->3->7:20$

每种发生的几率都是$1 \over 4$，所以$E=16$。

但是这种方法需要找到每条路径，感觉非常麻烦。其实我们考虑每个点对期望的贡献，其实就是它的概率乘它的权值。所以也可以这么算

$$E=5 \times 1+6 \times {1 \over 2}+2 \times {1 \over 2}+7 \times {1 \over 4}+4 \times {1 \over 4}+8 \times {1 \over 4}+9 \times {1 \over 4}=16$$

这就是期望可以分解成多个子期望的加权和，权为子期望发生的概率，即

$$E(aA+bB+\cdots) = aE(A) + bE(B) + \cdots $$

看个例题Poj2096

Description

Ivan is fond of collecting. Unlike other people who collect post stamps, coins or other material stuff, he collects software bugs. When Ivan gets a new program, he classifies all possible bugs into n categories. Each day he discovers exactly one bug in the program and adds information about it and its category into a spreadsheet. When he finds bugs in all bug categories, he calls the program disgusting, publishes this spreadsheet on his home page, and forgets completely about the program.
Two companies, Macrosoft and Microhard are in tight competition. Microhard wants to decrease sales of one Macrosoft program. They hire Ivan to prove that the program in question is disgusting. However, Ivan has a complicated problem. This new program has s subcomponents, and finding bugs of all types in each subcomponent would take too long before the target could be reached. So Ivan and Microhard agreed to use a simpler criteria — Ivan should find at least one bug in each subsystem and at least one bug of each category.
Macrosoft knows about these plans and it wants to estimate the time that is required for Ivan to call its program disgusting. It’s important because the company releases a new version soon, so it can correct its plans and release it quicker. Nobody would be interested in Ivan’s opinion about the reliability of the obsolete version.
A bug found in the program can be of any category with equal probability. Similarly, the bug can be found in any given subsystem with equal probability. Any particular bug cannot belong to two different categories or happen simultaneously in two different subsystems. The number of bugs in the program is almost infinite, so the probability of finding a new bug of some category in some subsystem does not reduce after finding any number of bugs of that category in that subsystem.
Find an average time (in days of Ivan’s work) required to name the program disgusting.

Input

Input file contains two integer numbers, n and s (0 < n, s <= 1 000).

Output

Output the expectation of the Ivan’s working days needed to call the program disgusting, accurate to 4 digits after the decimal point.

Sample Input

1 2

Sample Output

3.0000

题意：

一个软件有s个子系统，会产生n种bug。

某人一天发现一个bug，这个bug属于某种bug，发生在某个子系统中。

求找到所有的n种bug，且每个子系统都找到bug，这样所要的天数的期望。

需要注意的是：bug的数量是无穷大的，所以发现一个bug，出现在某个子系统的概率是1/s，属于某种类型的概率是1/n。

题解：

设计状态$f[i][j]$表示已经找到i种bug，并存在于j个子系统中，要达到目标状态的天数的期望。

显然，$f[n][s]=0$，因为已经达到目标了。而$f[0][0]$就是我们要求的答案。

$f[i][j]$状态可以转化成以下四种：

$f[i][j]$发现一个bug属于已经找到的i种bug和j个子系统中
$f[i+1][j]$发现一个bug属于新的一种bug，但属于已经找到的j种子系统
$f[i][j+1]$发现一个bug属于已经找到的i种bug，但属于新的子系统
$f[i+1][j+1]$发现一个bug属于新的一种bug和新的一个子系统

以上四种的概率分别为：

$p1 = {i\times j \over n\times s}$
$p2 = {(n-i)\times j \over n\times s}$
$p3 = {i\times (s-j) \over n\times s}$
$p4 = {(n-i)\times (s-j) \over n\times s}$

我们算它的期望就是

$$f[i][j]={i\times j \over n\times s} \times f[i][j]+{(n-i)\times j \over n\times s} \times f[i+1][j]+{i\times (s-j) \over n\times s}\times f[i][j+1]+{(n-i)\times (s-j) \over n\times s} \times f[i+1][j+1]+1$$

移项

$$f[i][j]-{i\times j \over n\times s} \times f[i][j]={(n-i)\times j \over n\times s} \times f[i+1][j]+{i\times (s-j) \over n\times s}\times f[i][j+1]+{(n-i)\times (s-j) \over n\times s} \times f[i+1][j+1]+1$$

除过去

$$f[i][j]=[{(n-i)\times j \over n\times s} \times f[i+1][j]+{i\times (s-j) \over n\times s}\times f[i][j+1]+{(n-i)\times (s-j) \over n\times s} \times f[i+1][j+1]+1] \div (1-{i\times j \over n\times s})$$

上下同乘$n \times s$

$$f[i][j]=[(n-i)\times j \times f[i+1][j]+i\times (s-j)\times f[i][j+1]+(n-i)\times (s-j) \times f[i+1][j+1]+n\times s] \div (n\times s-i\times j)$$

这就可以转移了

#include <cstdio>
using namespace std;
double f[1010][1010];
int n,s;
main()
{
    scanf("%d%d",&n,&s);
    f[n][s]=0;
    for (int i=n;i>=0;i--)
        for (int j=s;j>=0;j--)
            if (i!=n || j!=s)
                f[i][j]=(f[i+1][j]*(n-i)*j+f[i][j+1]*(s-j)*i+f[i+1][j+1]*(n-i)*(s-j)+n*s)/(n*s-i*j);
    printf("%.4lf\n",f[0][0]);
}

bzoj3450

Description

某一天WJMZBMR在打osu，但是他太弱逼了，有些地方完全靠运气:(
我们来简化一下这个游戏的规则
有n次点击要做，成功了就是o，失败了就是x，分数是按comb计算的，连续a个comb就有a*a分，comb就是极大的连续o。
比如ooxxxxooooxxx，分数就是22+44=4+16=20。
Sevenkplus闲的慌就看他打了一盘，有些地方跟运气无关要么是o要么是x，有些地方o或者x各有50%的可能性，用?号来表示。
比如oo?xx就是一个可能的输入。
那么WJMZBMR这场osu的期望得分是多少呢？
比如oo?xx的话，?是o的话就是oooxx => 9，是x的话就是ooxxx => 4
期望自然就是(4+9)/2 =6.5了

Input

第一行一个整数n，表示点击的个数
接下来一个字符串，每个字符都是ox？中的一个

Output

一行一个浮点数表示答案
四舍五入到小数点后4位
如果害怕精度跪建议用long double或者extended

Sample Input

4

????

Sample Output

4.1250

Hint

n<=300000

题解

这题的转移也是比较直接的。我们记下两个状态，$f[i]$表示到i的期望得分，$g[i]$表示到i的期望连续长度。

对于x，$g[i]=0,f[i]=f[i-1]$
对于o，因为$(l+1)^2=l^2+2l+1$，所以$g[i]=g[i-1]+1,f[i]=f[i-1]+2 \times g[i-1]+1$
对于?，两种都是$1 \over 2$的概率，所以$g[i]={g[i-1]+1 \over 2},f[i]=f[i-1]+{2 \times g[i-1]+1 \over 2}$

然后就很直接了

#include <cstdio>
#include <cstring>
#define N 300010
using namespace std;
double f[N],g[N];
int _;
char s[N];
main()
{
    scanf("%d",&_);
    scanf("%s",s+1);
    int len=strlen(s+1);
    for (int i=1;i<=len;i++)
        if (s[i]=='x')
            f[i]=f[i-1],g[i]=0;
        else if (s[i]=='o')
            f[i]=f[i-1]+2*g[i-1]+1,g[i]=g[i-1]+1;
        else
            f[i]=(double)f[i-1]+g[i-1]+0.5,g[i]=(g[i-1]+1)/2.0;
    printf("%0.4lf\n",f[len]);
}

luogu2473

题目描述

你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出k次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。

宝物一共有n种，系统每次抛出这n种宝物的概率都相同且相互独立。也就是说，即使前k-1 次系统都抛出宝物1（这种情况是有可能出现的，尽管概率非常小），第k次抛出各个宝物的概率依然均为1/n。

获取第 i 种宝物将得到Pi分，但并不是每种宝物都是可以随意获取的。第i种宝物有一个前提宝物集合Si。只有当Si中所有宝物都至少吃过一次，才能吃第i 种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会）。注意，Pi 可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。

假设你采取最优策略，平均情况你一共能在奖励关得到多少分值？

输入输出格式

输入格式：

第一行为两个正整数k 和n，即宝物的数量和种类。以下n行分别描述一种

宝物，其中第一个整数代表分值，随后的整数依次代表该宝物的各个前提宝物（各

宝物编号为1到n），以0结尾。

输出格式：

输出一个实数，保留六位小数，即在最优策略下平均情况的得分。

输入输出样例

输入样例#1：

1 2
1 0
2 0

输出样例#1：

1.500000

输入样例#2：

6 6
12 2 3 4 5 0
15 5 0
-2 2 4 5 0
-11 2 5 0
5 0
1 2 4 5 0

输出样例#2：

10.023470

说明

1 <= k <= 100, 1 <= n <= 15，分值为[-10^6,10^6]内的整数。

题解：

发现n的范围非常的和善：状压

用一维状压来表示一下已选过的状态来判断是否可以满足。用f[i][sat]来表示第i步状态为sat的期望。由于正推没有办法确定状态的最优解，所以倒推比较合适。

每种能转移的状态都是$1 \over n$的概率，非常好想的转移。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,k,need[110],x;
double val[110],f[110][1<<16];
main()
{
    scanf("%d%d",&k,&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lf%d",&val[i],&x);
        while(x)
            need[i]|=(1<<x-1),
            scanf("%d",&x);
    }
    for (int i=k;i;i--)
        for (int sat=0;sat<=(1<<n)-1;sat++)
        {
            for (int j=1;j<=n;j++)
                if ((sat&need[j])==need[j])
                    f[i][sat]+=max(f[i+1][sat],f[i+1][sat|(1<<(j-1))]+val[j]);
                else
                    f[i][sat]+=f[i+1][sat];
            f[i][sat]/=(double)n;
        }
    printf("%.6lf",f[1][0]);
}

cogs1498

【题目描述】

本题目有一定的数学背景。

题中要求计算一个随机变量的期望值。如果你之前没有听说过这些数学名词，下面给出了一些简单的定义。一个随机变量是一个可以取若干个值的变量，对于每个可能值，它都有一定概率取这个值。取到每个可能值的概率都是正的，并且它们的和是1.随机变量的数学期望是它所有可能值与其对应概率之积的乘积总和（对它有一些更为复杂，形式化的定义，但你现在不需要用到这些）。例如，一个标准的6面骰子投出后上面的值是一个随机变量，有6个可能值（1到6），取到每个可能值的概率都是1/6.那么它的数学期望就是1/6+2/6+…+6/6=3.5.

下面是题目内容。

我喜欢玩纸牌接龙。每次我都有p的概率赢，1-p的概率输。游戏程序会统计我获胜盘数的百分比。如果我一直玩下去，这个百分比就会在p*100%左右浮动。但我仍不满足。

这是我的计划。每天，我都会玩纸牌接龙。如果我赢了，我就高高兴兴地去睡觉。如果我输了，我就一直玩下去直到我这天获胜盘数的百分比严格大于p。这时，我就会宣布胜利，然后高高兴兴地去睡觉。你可以看到，每天我都可以宣布自己保持了获胜比例大于p*100%。我打败了数学规律！

如果你感觉这里好像有什么奇怪的东西，那你就对了。我不可能永远这么做，因为我每天玩的游戏盘数有限。我每天至多玩n盘游戏。那么，这个机智的计划在因为这一限制失败前，执行天数的数学期望是多少？值得注意的是，答案至少为1，因为我至少要玩一天才能发现计划失败了。

【输入格式】

输入包含多组数据。

输入文件的第一行是数据组数N。

接下来是N组数据。每组数据有一行，包含p（写成分数）和n。

【输出格式】

对于每组数据，输出一行”Case #x: y”，其中x是数据组数（从1开始），y是期望天数，向下取整。

【样例输入】

4

1/2 1

1/2 2

0/1 10

1/2 3

【样例输出】

Case #1: 2

Case #2: 2

Case #3: 1

Case #4: 2

【提示】

1<=N<=3000,0<=p< 1

p的分母不超过1000。

1<=n<=100。

答案允许有±1的误差。

题解

上节课刚学了等比数列，就用上了= =

我们首先发现每天晚上都是独立的，我们可以单独计算

$f[i][j]$表示进行了i局一共赢了j局，且枚举结束后获胜比例都不超过p的概率。

转移就是

$$f[i][j]=f[i-1][j] \times (1-p)+f[i-1][j-1] \times p {{j \over i}<=p}$$

可以滚动一下，缩成一维的。

那么这天晚上结束的概率$q_s=f[n][0]+f[n][1]+\cdots f[n][n]$

然后我们考虑是第几天结束

x=1时结束的概率为$q_s$
x=2时结束的概率为$(1-q_s)\times q_s$
x=3时结束的概率为$(1-q_s)^2 \times q_s$

然后就算下期望：

$$E=q_s+2\times (1-q_s)\times q_s+3\times (1-q_s)^2 \times q_s+\cdots $$

令

$$s={E \over q_s}=1+2\times (1-q_s)+3\times (1-q_s)^2+\cdots$$

$$(1-q_s) \times s=(1-q_s)+2\times (1-q_s)^2+3\times (1-q_s)^3+\cdots$$

上面两式作差可得

$$s-(1-q_s)\times s=1+(1-q_s)+(1-q_s)^2+\cdots$$

$$q_s\times s=E=1+(1-q_s)+(1-q_s)^2+(1-q_s)^3+\cdots$$

根据这个，我们就得到了

$$E={1\over q_s}$$

代码

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int T,p1,p2,n;
double Q,f[110];
main()
{
    freopen("expected.in","r",stdin);
    freopen("expected.out","w",stdout);
    scanf("%d",&T);
    for (int cs=1;cs<=T;cs++)
    {
        scanf("%d/%d %d",&p1,&p2,&n);
        double p=(double)p1/p2;
        memset(f,0,sizeof f);
        f[0]=1.0;
        for (int i=1;i<=n;i++)
            for (int j=i*p1/p2;j>=0;j--)
            {
                f[j]*=(1.0-p);
                if (j) f[j]+=f[j-1]*p;
            }
        Q=0.0;
        for (int j=0;j*p2<=n*p1;++j) Q+=f[j];
        int ans=floor(1.0/Q);
        printf("Case #%d: %d\n",cs,ans);
    }
}

下面的题目都是很诡异的，因为会出现概率式子里面调用自己的情况，这样的话就需要高斯消元来求解

题目描述

一个无向连通图，顶点从1编号到N，边从1编号到M。 小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。

输入输出格式

输入格式：

第一行是正整数N和M，分别表示该图的顶点数 和边数，接下来M行每行是整数u，v(1<=u,v<=N)，表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N<=10，100%的数据满足2<=N<=500且是一个无向简单连通图。

输出格式：

仅包含一个实数，表示最小的期望值，保留3位小数。

输入输出样例

输入样例#1：

3 3
2 3
1 2
1 3

输出样例#1：

3.333

说明

边(1,2)编号为1，边(1,3)编号2，边(2,3)编号为3。

题解

首先，这个题非常有毒。看这通过率：

这题的基本思路就是，我们计算出每条边走的概率，设的时候概率大就编号小，最后把概率乘上编号，加起来就是期望。

如何算边的概率呢？可以算出点的概率，然后

$$p(x,y)={p[x]\over d[x]}+{p[y] \over d[y]}$$

$p[i]$表示这个点经过的概率，$d[i]$表示这个点的度。

那点的概率该怎么求呢？

$$p[i]=\sum_{(i,j)\in G} {p[j]\over d[j]}$$

就是和他相邻点转移到他的概率。

但是我们发现这会产生环，无法简单的递推（它旁边的点的概率需要它自己的概率推出，它自己的概率需要旁边点的概率推出）

这该如何是好呢？其实可以用列方程的思想。

我们把所有的点的概率设成未知数，然后对每个概率都列出一个式子，最后对这个方程组求解。

对方程组求解的效率是$O(n^3)$，具体可以看这个总结。

我们可以看下这道题的列方程的过程

for (int i=1;i<n;i++)
{
    f[i][i]=1.0;
    for (int j=st[i];j;j=e[j].next)
        if (e[j].to!=n)
            f[i][e[j].to]=-1/d[e[j].to];
}
f[1][n]=1;

首先要明白我们填进去的数都是这一位的系数。所以$f[i][j]$就表示j这个点转移到i这个点的概率。这个概率再乘上未知数（这个点的概率）就求出了它对i这个点的概率的贡献。

这样的话$f[i][i]$所对的未知数就是i这个点的概率，也就是我们要解的答案。因为每个点的概率=所有转移过来点的概率和，所以其实高斯消元解的方程式这样的：

$$这个点的概率\times 1-\sum所有相邻的点转移过来的概率=0$$

而且因为一开始就在第一个点，第一个方程的结果要设成1

代码

#include <cstdio>
#include <algorithm>
#define N 600
using namespace std;
struct edge
{
    int to,next;
}e[N*N*2];
int st[N*N*2],n,m,tot,x,y,s[N*N*2],ed[N*N*2];
double d[N],f[N][N],ans[N],sum,E[N*N*2];
void add(int x,int y)
{
    e[++tot].to=y;
    e[tot].next=st[x];
    st[x]=tot;
}
const double eps=1e-7;
int dcmp(double x)
{
    if (x<=eps&&x>=-eps) return 0;
    return (x>0)?1:-1;
}
void gauss()
{
    for (int i=1;i<n;i++)
    {
        int num=i;
        for (int j=i+1;j<n;j++)
            if (dcmp(f[j][i]-f[num][i])>0) num=j;
        if (num!=i)
            for (int j=1;j<n+1;j++)
                swap(f[i][j],f[num][j]);
        for (int j=i+1;j<n;j++)
            if (dcmp(f[j][i]))
            {
                double t=f[j][i]/f[i][i];
                for (int k=1;k<n+1;k++)
                    f[j][k]-=t*f[i][k];
            }
    }
    for (int i=n-1;i>=1;i--)
    {
        for (int j=i+1;j<n;j++)
            f[i][n]-=f[i][j]*ans[j];
        ans[i]=f[i][n]/f[i][i];
    }
}
main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
        d[x]+=1.0,d[y]+=1.0;
        s[i]=x,ed[i]=y;
    }
    for (int i=1;i<n;i++)
    {
        f[i][i]=1.0;
        for (int j=st[i];j;j=e[j].next)
            if (e[j].to!=n)
                f[i][e[j].to]=-1/d[e[j].to];
    }
    f[1][n]=1;
    gauss();
//    for (int i=1;i<n;i++)
//        printf("%lf ",ans[i]);
    for (int i=1;i<=m;i++)
        E[i]=ans[s[i]]/d[s[i]]+ans[ed[i]]/d[ed[i]];
    sort(E+1,E+m+1);
    for (int i=1;i<=m;i++)
        sum+=E[i]*(m-i+1.0);
    printf("%.3lf",sum);
}

bzoj3270

Description

有一天Petya和他的朋友Vasya在进行他们众多旅行中的一次旅行，他们决定去参观一座城堡博物馆。这座博物馆有着特别的样式。它包含由m条走廊连接的n间房间，并且满足可以从任何一间房间到任何一间别的房间。
两个人在博物馆里逛了一会儿后两人决定分头行动，去看各自感兴趣的艺术品。他们约定在下午六点到一间房间会合。然而他们忘记了一件重要的事：他们并没有选好在哪儿碰面。等时间到六点，他们开始在博物馆里到处乱跑来找到对方（他们没法给对方打电话因为电话漫游费是很贵的）
不过，尽管他们到处乱跑，但他们还没有看完足够的艺术品，因此他们每个人采取如下的行动方法：每一分钟做决定往哪里走，有Pi 的概率在这分钟内不去其他地方（即呆在房间不动），有1-Pi 的概率他会在相邻的房间中等可能的选择一间并沿着走廊过去。这里的i指的是当期所在房间的序号。在古代建造是一件花费非常大的事，因此每条走廊会连接两个不同的房间，并且任意两个房间至多被一条走廊连接。
两个男孩同时行动。由于走廊很暗，两人不可能在走廊碰面，不过他们可以从走廊的两个方向通行。（此外，两个男孩可以同时地穿过同一条走廊却不会相遇）两个男孩按照上述方法行动直到他们碰面为止。更进一步地说，当两个人在某个时刻选择前往同一间房间，那么他们就会在那个房间相遇。
两个男孩现在分别处在a，b两个房间，求两人在每间房间相遇的概率。

Input

第一行包含四个整数，n表示房间的个数;m表示走廊的数目;a,b (1 ≤ a, b ≤ n),表示两个男孩的初始位置。
之后m行每行包含两个整数，表示走廊所连接的两个房间。
之后n行每行一个至多精确到小数点后四位的实数 表示待在每间房间的概率。
题目保证每个房间都可以由其他任何房间通过走廊走到。

Output

输出一行包含n个由空格分隔的数字，注意最后一个数字后也有空格，第i个数字代表两个人在第i间房间碰面的概率（输出保留6位小数）
注意最后一个数字后面也有一个空格

Sample Input

2 1 1 2

1 2

0.5

0.5

Sample Output

0.500000 0.500000

HINT

对于100%的数据有 n <= 20，n-1 <= m <= n(n-1)/2

题解

这题题怎么想呢？其实基本思路和上面那个题是一样的，状态$f[i][j]$表示一个人在i，另一个人在j的概率，列出一个方程：

$$f$$