概述

1.数学期望

（1）概念

如果X是在概率空间 $（\Omega ,F,P）$（Ω,F,P）中的随机变量，那么它的期望值 $E\left[X\right]$E[X]的定义是：
$expectation$expectation

也就是试验中每次可能的结果乘以其结果概率的总和。

换句话说，期望等于每个数出现的概率乘以每个数的值

（2）性质

• 线性 $linear$linear

• 期望具有线性关系: $E(ax1+bx2+...)=aE\left(x1\right)+bE\left(x2\right)+...$E(ax1+bx2+...)=aE(x1)+bE(x2)+...

• 在一般情况下，两个随机变量的积的期望值不等于这两个随机变量的期望值的积。

• 当 $E\left[XY\right]=E\left[x\right]E\left[y\right]$E[XY]=E[x]E[y]成立时，随机变量 $X$X和 $Y$Y的协方差为 $0$0，又称它们不相关。特别的，当两个随机变量独立时，它们协方差（若存在）为 $0$0。

• 也就是说，当X，Y，相对独立，则有：
  

• 期望值也可以通过方差计算公式来计算方差
  其中 $Var（X）$Var（X）指的是方差
  

• C是常数
  
  

2.全期望公式

所以

根据已经求出的期望推出其他状态的期望，也可以根据一些特点和结果相同的情况，求出其概率。
这就引出了我们的期望dp

3.期望dp

对于一些比较难找到递推关系的数学期望问题，可以利用期望的定义式，根据实际情况以概率或者方案数（也就是概率*总方案数）作为一种状态，而下标直接或间接对应了这个概率下的变量值，将问题变成比较一般的统计方案数问题或者利用全概率公式计算概率的递推问题

一般来说，概率DP找到正确的状态定义后，转移是比较容易想到的。但状态一定是“可数”的，把有范围的整数作为数组下标。事实上，将问题直接作为状态是最好的。如问“n人做X事的期望次数”，则设计状态为f[i]表示i个人做完事的期望。转移一般是递推，即从上一个状态转移得（填表）或转移向下一个状态（刷表）。

有时期望DP需以最终状态为初始状态转移，即逆推。如f[i]表示期望还要走f[i]步到达终点。这种状态的转移是刷表法，形如 $f\left[i\right]=\sum p[i\to j]f\left[j\right]+w[i\to j]$f[i]=∑p[i→j]f[j]+w[i→j]，其中p[ ]表示转移的概率，w[ ]表示转移对答案的贡献。一般来说，初始状态确定时可用顺推，终止状态确定时可用逆推。

规律

1.期望可以分解成多个子期望的加权和，权为子期望发生的概率，即
$E(aA+bB+\dots )=aE\left(A\right)+bE\left(B\right)+\dots +1$E(aA+bB+…)=aE(A)+bE(B)+…+1；
2.期望从后往前找，一般 $dp\left[n\right]=0,dp\left[0\right]$dp[n]=0,dp[0]是答案；
3.解决过程，找出各种情况乘上这种情况发生的概率，求和；
4.概率DP一定要初始化！

转移方程

几种常见设转移方程数组的方法

1. 设 $f\left[i\right]$f[i]表示的是由i状态变成 最终 状态的期望
2. 按照题意直接设
3. 把选择的东西加入数组，如 $f\left[i\right]\left[j\right]$f[i][j]表示第 $i$i 个物品选 $j$j 个的期望或 $f\left[i\right]\left[j\right]$f[i][j]表示有 $i$i个 $A$A物品， $j$j个 $B$B物品的期望

求转移方程
应优先考虑进行操作后当前状态会怎么样，而不是如何变成当前状态，即先考虑 逆向，如果逆向没有思路，则考虑 正向

全概率公式

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

假如事件A与B相互独立，那么：

一、期望DP例题

1.UVA11021 Tribles麻球繁衍

UVA11021 Tribles麻球繁衍
题意翻译
题目大意
一开始有k种生物，这种生物只能活1天，死的时候有 $p_i$pi​的概率产生ii只这种生物（也只能活一天），询问m天内所有生物都死的概率（包括m天前死亡的情况）
输入格式
第一行输入一个整数T，表示数据总数
每一组先输入三个整数n(1<=n<=1000),k(0<=k<=1000),m(0<=m<=1000)
然后输入n个整数，分别为 $p_0$p0​到 $p_{n-1}$pn−1​

对于每一组数据，先输出"Case #x: " 再输出答案，精度要求在1e-6以内

———————————————————————————————————

思路：每个麻球是互相独立的，设计状态f[i]表示一个麻球i天内死绝的概率，则n个麻球在i天内死亡的概率是 $f[i{]}^n$f[i]n 。转移时考虑这个麻球第一天繁衍多少个，它们在接下来的i−1天内死绝了。转移方程为 $f\left[i\right]={\sum }_{j=0}^{k-1}p\left[j\right]f[i-1{]}^j$f[i]=∑j=0k−1​p[j]f[i−1]j ,
即 $fi=p0+p1fi-1+p2\left(fi-1\right)2+p3\left(fi-1\right)3+...+pn-1\left(fi-1\right)n-1$fi​=p0​+p1​fi−1​+p2​(fi−1​)2+p3​(fi−1​)3+...+pn−1​(fi−1​)n−1

其中 $p_j(f_{i-1}{)}^j$pj​(fi−1​)j的意思是，又生了j个麻球，这些麻球在i-1天后死亡。

由于一开始有k只麻球，且各麻球死亡是独立的，所以答案为 $(f_m{)}^k$(fm​)k

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+7;
const ll mod=1e9+7;
ll t,n,k,cnt,m;
double p[N];
double f[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)
    {
        memset(f,0,sizeof f);
        memset(p,0,sizeof p);
        cnt++;
        cin>>n>>k>>m;
        for(int i=0;i<n;i++)
            cin>>p[i];
        f[1]=p[0];
        for(int i=2;i<=m;++i)
            for(int j=0;j<n;++j)
                f[i]+=pow(f[i-1],j)*p[j];
        printf("Case #%lld: %.7lf\n",cnt,pow(f[m],k));
    }
}

2.算概率（简单，数论）

算概率

说明：有 1 道题，做对的概率是 $\frac{1}{2}$21​ 在模 $10^9+7$109+7意义下为 500000004 ）。

$fi,j$fi,j表示前 i 道题做对 j道的概率转移时考虑第 j 道题是否做对，转移方程为：
$f_{i,j}=f_{i-1,j}\times (1-p_i)+f_{i-1,j-1}\times p_i$fi,j​=fi−1,j​×(1−pi​)+fi−1,j−1​×pi​
时间复杂度 $O\left(n^2\right)$O(n2)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e3+7;
const ll mod=1e9+7;
ll n,f[N][N],a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=f[0][0]=1;i<=n;i++)
    {
        f[i][0]=f[i-1][0]*(mod+1-a[i])%mod;
        for(int j=1;j<=i;j++)
            f[i][j]=(f[i-1][j]*(mod+1-a[i])+f[i-1][j-1]*a[i])%mod;
    }
    for(int i=0;i<=n;i++)
        cout<<f[n][i]<<" ";
    cout<<endl;
    return 0;
}

二、求数学期望例题

3.HDU 5159 Card(概率期望)

题目大意：

桌子上有x张牌，每张牌从1到x编号，编号为 i(1<=i<=x)的牌上面标记着分数i , 每次从这x张牌中随机抽出一张牌，然后放回，执行 $b$b次操作，记第j次取出的牌上面分数是 $Sj$Sj, 问b次操作后不同种类分数之和的期望是多少。

样例解释：

对于第一组数据所有牌型的组合为 $(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)$(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)
对于 $(1,1,1)$(1,1,1)这个组合，他只有一种数字，所以不同数字之和为1
而对于 $(1,2,1)$(1,2,1)有两种不同的数字，即1和2，所以不同数字之和是3。
所以对应组合的不同数字之和为 $1，3，3，3，3，3，3，2$1，3，3，3，3，3，3，2
所以期望为 $(1+3+3+3+3+3+3+2)/8=2.625$(1+3+3+3+3+3+3+2)/8=2.625

思路：

我们先考虑一下每一个数出现的概率，首先我们计算有这 x 个数出现b次的总数肯定就是 $x^b$xb，那么 $x-1$x−1个数出现b次的总数就是 $(x-1{)}^b：$(x−1)b：所以一个数出现的总数就是 $x^b-(x-1{)}^b$xb−(x−1)b，那么概率就是 $(x^b-(x-1{)}^b)/x^b$(xb−(x−1)b)/xb,期望等于什么呢，期望等于的应该是每个数出现的概率乘以每个数的值，又因为期望具有线性关系:即 $E(ax1+bx2+...)=aE\left(x1\right)+bE\left(x2\right)+...$E(ax1+bx2+...)=aE(x1)+bE(x2)+...

所以我们要求的期望就等于 $(x^b-(x-1{)}^b)/x^b\ast (1+2+3+...+x)$(xb−(x−1)b)/xb∗(1+2+3+...+x)化简得：

$(1-((x-1)/x{)}^b)\ast (x+1)\ast x/2$(1−((x−1)/x)b)∗(x+1)∗x/2（最终公式）可以求了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
 
int main()
{
    int T;
    double x, b;
    scanf("%d",&T);
    for(int cas=1; cas<=T; cas++)
    {
        scanf("%lf%lf",&x,&b);
        double sum = x*(x+1)/2;
        double tmp = 1-pow(1-1.0/x,b);
        printf("Case #%d: %.3lf\n",cas,sum*tmp);
    }
    return 0;
}

参考博客

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧