基本公式

概率加法公式

$$P(A\cup B)=P(A)+P(B)-P(A\cap B)$$

概率并

$$P(A\cup B)\le P(A)+P(B)$$

全概率公式

设$B_1{B}_2\dots B_n$是样本空间$S$中互不相交的一系列事件，并且满足$S={\bigcup }_{k=1}^n{B}_k$，那么对于任意事件$A$
$$P(A)=\sum _{k=1}^{n}P(A|B_k)P(B_k)$$

马尔科夫不等式

假设$X\text{X}X$是只取非负值的随机变量，对于任意$\alpha >0$，有
$$P(X\text{X}X\ge \alpha )\le \frac{\mathbb{E}(X\text{X}X)}{\alpha }$$

切比雪夫不等式

对于任意随机变量$X\text{X}X$以及任意$\alpha >0$, 有
$$P(|X\text{X}X-\mathbb{E}(X\text{X}X)|\ge \alpha )\le \frac{var(X\text{X}X)}{{\alpha }^2}$$

二项分布

二项分布的概率函数满足
$$p(k)=\left(\begin{array}{r}n\\ k\end{array}\right)p^k(1-p{)}^{n-k}$$
期望
$$\mathbb{E}[X\text{X}X]={\mathbb{E}}_1[X\text{X}X]+\cdots +{\mathbb{E}}_n[X\text{X}X]=np$$
方差
$$var[X\text{X}X]=np(1-p)$$

几何分布

该分布源于投掷硬币$n$次，假设每一次有$p$概率正面朝上, 直到第$k$次出现正面的概率，概率函数为
$$p(k)=p(1-p{)}^{k-1}$$
通过递归方程计算期望
$$\mathbb{E}[X\text{X}X]=p+(1-p)(\mathbb{E}[X\text{X}X]+1)$$
期望
$$\mathbb{E}[X]=\frac{1}{p}$$
方差
$$var[X]=\frac{1-p}{p^2}$$

例题

ACW 217. 绿豆蛙的归宿

题目链接

题面

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

解析

不妨设从点$i$到终点的距离期望为$f_i$，从起点开始一步可达的点为$s_i$，距离为$d_i$，因此期望表达式为
$$f_s=\frac{1}{K}\sum _{i=1}^k{f}_{s_i}+d_i$$
使用记忆化递归算法求解

AC代码

#include <cstring>
#include <iostream>
#include <iomanip>
using namespace std;

const int N=100005;
const int M=200005;

int head[N], dout[N];
int n, m, E=0;
double f[N];
struct{int v, ne, w;}e[M];
inline void add(int a, int b, int c){
    e[E].v=b;
    e[E].ne=head[a];
    e[E].w=c;
    head[a]=E++;
}

double dp(int u){
    if(f[u]>=0) return f[u];
    if(u==n) return f[u]=0;
    f[u]=0;
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        f[u]+=(e[i].w+dp(v))/dout[u];
    }
    return f[u];
}

int main(){
    memset(dout, 0x00, sizeof dout);
    memset(head, -1, sizeof head);
    cin>>n>>m;
    for(int i=0; i<m; ++i){
        int a, b, c;
        cin>>a>>b>>c;
        add(a, b, c);
        dout[a]++; // 出度
    }
    memset(f, -1, sizeof f);
    cout<<fixed<<setprecision(2)<<dp(1)<<endl;
    return 0;
}

ACW 218. 扑克牌

题目链接

题面

Rainbow把一副扑克牌(54张)随机洗开，倒扣着放成一摞。然后Admin从上往下依次翻开每张牌，每翻开一张黑桃、红桃、梅花或者方块，就把它放到对应花色的堆里去。
Rainbow想问问Admin，得到$A$张黑桃、$B$张红桃、$C$张梅花、$D$张方块需要翻开的牌的张数的期望值$E$是多少？
特殊地，如果翻开的牌是大王或者小王，Admin将会把它作为某种花色的牌放入对应堆中,使得放入之后$E$的值尽可能小。

解析

关键是定义大小王的状态，不妨设$x$表示小王，$y$表示大王，则他们有5种状态，$0\sim 3$表示放到四种花色的牌堆中，$4$表示还未被翻出来.
定义状态$f[a][b][c][d][x][y]$表示红桃，黑桃，梅花，方片，小王，大王的状态，因此当前已经摆放的牌数为
$$S=a+b+c+d+(x!=4)+(y!=4)$$
剩余牌数量为$54-S$
所以可以绘制出以下状态转移表格

AC代码

#include <cstring>
#include <iostream>
#include <iomanip>

using namespace std;

const int N = 15;
const double INF = 1e20;

int A, B, C, D;
double f[N][N][N][N][5][5];

double dp(int a, int b, int c, int d, int x, int y)
{
    double &v = f[a][b][c][d][x][y];
    if (v >= 0) return v;
    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 v = 0;

    int sum = a + b + c + d + (x != 4) + (y != 4);
    sum = 54 - sum;
    if (sum <= 0) return v = INF;

    v = 1;
    if (a < 13) v += (13.0 - a) / sum * dp(a + 1, b, c, d, x, y);
    if (b < 13) v += (13.0 - b) / sum * dp(a, b + 1, c, d, x, y);
    if (c < 13) v += (13.0 - c) / sum * dp(a, b, c + 1, d, x, y);
    if (d < 13) v += (13.0 - d) / sum * dp(a, b, c, d + 1, x, y);
    if (x == 4)
    {
        double t = INF;
        for (int i = 0; i < 4; i ++ ) t = min(t, 1.0 / sum * dp(a, b, c, d, i, y));
        v += t;
    }
    if (y == 4)
    {
        double t = INF;
        for (int i = 0; i < 4; i ++ ) t = min(t, 1.0 / sum * dp(a, b, c, d, x, i));
        v += t;
    }
    return v;
}

int main()
{
    cin >> A >> B >> C >> D;
    memset(f, -1, sizeof f);
    double t = dp(0, 0, 0, 0, 4, 4);
    if (t > INF / 2) t = -1;
    cout<<fixed<<setprecision(3)<<t<<endl;
    return 0;
}

最后

以上就是无语小兔子最近收集整理的关于【ALGO】概率和期望基本公式例题的全部内容，更多相关【ALGO】概率和期望基本公式例题内容请搜索靠谱客的其他文章。