概率与期望

概率论

事件的运算及概率

• 包含：$A \subset B$，发生 $B$ 时必然发生 $A$，发生 $A$ 时不一定发生 $B$。

• 并（和）事件：$A \cup B = A + B$，$A$ 发生或 $B$ 发生或两者都发生。

• 交（积）事件：$A \cap B = AB$，$A$ 和 $B$ 同时发生。

• 差事件：$A - B = A\overline{B} = A - AB$，$A$ 发生但 $B$ 不发生，$\overline{B}$ 表示 $B$ 的对立事件。

• 互斥事件：$AB=\varnothing$，$A$ 和 $B$ 不能同时发生。

• 对立（逆）事件：$A+\overline{A}=S,\quad A\overline{A}=\varnothing$，$A$ 发生时 $\overline{A}$ 不发生，$\overline{A}$ 发生时，$A$ 不发生。

• 独立事件：$P(AB)=P(A)P(B)$

  $A$ 发生与否不影响 $B$ 的概率，反之亦然。

  • 若 $A,B$ 独立，则 $A,\overline{B}$、$\overline{A},B$、$\overline{A},\overline{B}$ 也相互独立。
  • 若 $A,B,C$ 相互独立，那么
    • $A,B,C$两两独立(但逆命题不成立)
    • $P(ABC)=P(A)P(B)P(C)$。

• 德摩根律：

  $$\overline{A\cup B}=\overline{A}\cap\overline{B}\\ \overline{A\cap B}=\overline{A}\cup\overline{B} $$

• 加法公式（容斥原理）：
  $P(A+B)=P(A)+P(B)-P(AB)$
  $P(A+B+C)=P(A)+P(B)+P(C)-P(AB)-P(AC)-P(BC)+P(ABC)$

• 减法公式：
  $P(A-B)=P(A)-P(AB)$

• 对立事件概率：
  $P(\overline{A})=1-P(A)$

条件概率与乘法公式

• 条件概率：在 $A$ 已发生下 $B$ 的概率。
  $P(B\mid A)=\dfrac{P(AB)}{P(A)}$

• 乘法公式：
  $P(AB)=P(A)P(B\mid A)=P(B)P(A\mid B)$

全概率公式与贝叶斯公式（包括在 NOI 大纲内但大概率 useless）

• 全概率公式（$\{B_i\}$ 为完备事件组）：

  $$P(A)=\sum_{i=1}^{n}P(B_i)P(A\mid B_i)$$

• 贝叶斯（逆概）公式：

  $$P(B_i\mid A)=\dfrac{P(B_i)P(A\mid B_i)}{P(A)}$$

离散型随机变量（一维）

离散型随机变量是指取值为可列（通常是有限或可数无限）集合中某些具体数值的随机变量。

分布列

随机变量 $X$ 可取值：

各取值对应的概率为：

分布函数

重要性质 离散型一维随机变量的分布函数可视为前缀和）：$P\{a\le X\le b\}=F(b)-F(a-1)$。

数学期望

若 $Y=g(X)$，则

性质：

• $E(c)=c,\quad E(ax+c)=aE(X)+c$。

• $E(X\pm Y)=E(X)\pm E(Y)$

• 若 $X,Y$ 独立，则 $E(XY)=E(X)E(Y)$。

方差

性质：

• $D(c)=0,\quad D(aX+b)=a^2D(X)$ 。
• $D(x\pm y)=D(x)+D(y)\pm 2\operatorname{Cov}(X,Y)$，其中
  $\operatorname{Cov}(X,Y)=E(XY)-E(X)E(Y)$为协方差。
• 若$X,Y$独立，则 $\operatorname{Cov}(X,Y)=0$，因此 $D(X\pm Y)=D(X)+D(Y)$。

常见分布

【0–1 分布（伯努利分布）】

进行一次独立试验，成功的概率为 $p$，失败的概率为 $1-p$。（即 $n=1$ 的二项分布）

【二项分布】

进行 $n$ 次独立试验，每次成功的概率为 $p$，失败的概率为 $1-p$。

【几何分布】

进行独立试验，直到第一次成功为止；成功的概率为 $p$，失败的概率为 $1-p$。

【超几何分布】

从 $N$ 个物体中抽取 $n$ 个物体，其中有 $K$ 个是成功的，$N-K$ 个是失败的。

概率与期望 DP

与组合数 DP 类似，只是在 DP 转移时结合概率或期望的计算。常见有后效性方程，需要移项或高斯消元处理。

【例题 1】Jerry's Protest（纯概率论应用）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a.begin(), a.end());
    // 赢 a[i]-a[j] 的概率
    unordered_map<int, double> p;
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            p[a[i]-a[j]] += 2.0/(n*(n-1));
    // 后手前两把总和的概率
    unordered_map<int, double> q;
    for(auto i : p)
        for(auto j : p)
            q[i.first+j.first] += i.second*j.second;
    double ans = 0;
    for(auto i : p)
        for(auto j : q)
            if(i.first>j.first) ans += i.second*j.second;   
    cout<<fixed<<setprecision(10)<<ans<<'\n';
}

【例题 2】ABC326E（普通期望 DP）

• 状态：$E(x)$ 为当前值为 $x$ 时后续期望工资。

• 初值：$E(n)=0$。因为此时无法掷出满足 $x<y$的 $y$。

• 目标：$E(0)$。

• 转移：$\displaystyle E(x)=\sum_{y=x+1}^{n}\frac{1}{n}\big(A_y+E(y)\big)$。

  $E(x)$ 需要从 $n$ 到 $0$ 进行计算，计算过程中对$A_y+E(y)$ 动态维护一个后缀和即可 $O(n)$解决。

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    using mint = atcoder::modint998244353;
    int n; cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<mint> E(n+1);
    mint suf = 0;
    for(int i=n;i>=0;i--){
        E[i] = suf;
        suf += (a[i]+E[i])/n;
    }
    cout<<E[0].val()<<'\n';
}

【例题 3】ABC360E（期望 DP 线性递推）

状态设计

• $E(x)$ 代表当进行了 $x$ 次交换后，黑球位置的期望值。

初始状态

• $E(0)=1$

所求结果

• $E(k)$

转移方程

$[1,N]$ 独立均匀地随机选择两个整数，总方案数 $N^2$。设黑球当前位置为 $p$，选择到的两个整数为 $i,j$。

• 其中 $i\ne p且 j\ne p$ 的方案数为 $(N-1)^2$；
  $i =p且 j=p$ 的方案数为 $1$。
  这两种情况都不会对黑球的位置产生影响 ，即：

  $$\frac{(N-1)^2+1}{N^2}\,E(x-1)\ \longrightarrow\ E(x). $$

• 而对于剩余的$N^2-\big((N-1)^2+1\big)=2N-2$种情况 ，黑球位置会被等概率交换到$[1,N]$ 中除 $E(x-1)$ 以外的其他位置

  因此：

  $$\frac{2N-2}{N^2}\cdot \frac{1}{N}\! \left(\sum_{i=1}^{N - 1} i - E(x-1)\right)\ \longrightarrow\ E(x). $$

将两部分相加并整理，得到

因为 $\sum_{i=1}^{N} i = \dfrac{N(N+1)}{2}$，继续化简：

最终递推式：

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    using mint = atcoder::modint998244353;
    int n, k; cin>>n>>k;
    vector<mint> E(k+1);
    E[0] = 1;
    for(int i=1;i<=k;i++) E[i] = ((n-2)*E[i-1]+n+1)/n;
    cout<<E[k].val()<<'\n';
}

【例题 4】ABC382E（概率 DP + 期望 DP + 移项消后效性）

概率部分：先求每个卡包爆出 $0,1,2,\dots,n$ 张稀有卡的概率（简单概率 DP）

• 状态设计：$P_{i,j}$ 表示拆到第 $i$ 张卡片，累计爆出 $j$ 张稀有卡的概率。
• 初始状态：$\displaystyle P_{0,0}=1$
• 状态转移：$\displaystyle P_{i,j}=p_i\,P_{i-1,j-1} + (1-p_i)\,P_{i-1,j}$
• 所求结果：$\displaystyle P_{n,*}$（第 $n$ 张拆完后的各个 $j$ 的概率分布）

然后处理问题所要求的期望部分，枚举每拆一个卡包获取到稀有卡的数量，简单期望 DP 处理：

期望部分：每拆一个卡包获得稀有卡的数量（简单期望 DP）

• 状态设计：$\displaystyle E_i$ 表示从 $i$ 张卡片开始拆包，直到至少有 $x$ 张卡片的期望步数。

• 初始状态：$\displaystyle E_x = 0$

• 原始转移式：

  $$E_i=\sum_{j=0}^{n} P_{n,j}\,\big(E_{\min(x,i+j)}+1\big) $$

注意：当 $j=0$ 时出现自依赖项，可移项消环。

• 移项后的等价式：

  $$\begin{aligned} E_i &= \sum_{j=1}^{n} P_{n,j}\,\big(E_{\min(x,i+j)}+1\big) + P_{n,0}\,(E_i+1) \\ (1-P_{n,0})\,E_i &= \sum_{j=1}^{n} P_{n,j}\,\big(E_{\min(x,i+j)}+1\big) + P_{n,0} \\ E_i &= \frac{\displaystyle \sum_{j=1}^{n} P_{n,j}\,\big(E_{\min(x,i+j)}+1\big) + P_{n,0}} {1-P_{n,0}} \; . \end{aligned} $$

• 所求结果：$\displaystyle E_0$

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int n,x;
    cin>>n>>x;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    vector<double> p(n);
    for(int i=0;i<n;i++) p[i] = a[i]/100.0;
    vector<vector<double>> P(n+1, vector<double>(n+1));
    P[0][0] = 1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(j!=n) P[i+1][j+1] += P[i][j]*p[i];
            P[i+1][j] += P[i][j]*(1-p[i]);
        }
    }
    vector<double> E(x+1);
    for(int i=x-1;i>=0;i--)
    {
        E[i] += P[n][0];
        for(int j=1;j<=n;j++) E[i] += P[n][j]*(E[min(x, i+j)]+1);
        E[i] /= (1-P[n][0]);
    }
    cout<<fixed<<setprecision(10)<<E[0]<<'\n';
}

【例题 5】ABC411E $E[\max]$（分布函数转化）

目标与记号

• 设 $P\{X=x\}$ 表示所有骰子掷出后最大值为 $x$ 的概率，则答案：

  $$\sum_{i} i \times P\{X=i\}.$$

  其中 $i$ 枚举所有可能出现的点数。

思路

考虑如何求 $P\{X=x\}$ 时，显然所有点数 $>x$ 值都不能出现，这很好解决。其次还需要剩下的点数中至少有一个点数为 $x$，解决这个限制比较困难。

考虑使用分布函数进行转化。设分布函数为：

由分布函数性质：

因而

计算 $F(x)$

注意到求 $F(x)=P\{X≤x\}$ 与求 $P\{X=x\}$ 的差别，相当于把“剩下的点数中至少有一个点数为 $x$”这个限制去除，这样问题就非常容易解决了。

我们维护一下每个骰子的点数 $≤x$ 的面的数量（记为 $c_i$），则有：

将所有骰子的点数进行从大到小的排序，计算完一个点数后就更新一下所有包含这个点数的骰子的 $c_i$，并且同步更新上式的值即可。

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using ll = long long;
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    using mint = atcoder::modint998244353;
    int n;
    cin>>n;
    vector<array<int, 6>> a(n);
    for(int i=0;i<n;i++)
        for(int j=0;j<6;j++)
            cin>>a[i][j];
    map<int, vector<int>> pos;
    for(int i=0;i<n;i++)
        for(int j=0;j<6;j++)
            pos[a[i][j]].push_back(i);
    vector<pair<int, vector<int>>> v(pos.rbegin(), pos.rend());
    mint prod = 1;
    vector<int> cnt(n, 6);
    map<int, mint> f;
    for(auto& [x, w] : v)
    {
        f[x] = prod;
        for(auto i : w)
        {
            prod /= mint(cnt[i])/6;
            cnt[i]--;
            prod *= mint(cnt[i])/6;
        }
    }
    reverse(v.begin(), v.end());
    mint ans = 0;
    for(size_t i=0;i<v.size();i++)
    {
        if(i==0) ans += v[i].first*f[v[i].first];
        else ans += v[i].first*(f[v[i].first]-f[v[i-1].first]);
    }
    cout<<ans.val()<<'\n';
}

【例题 6】ABC412F Socks 4（观察性质消后效性）

设

期望题目首先考虑期望 DP。注意到题目中仅有“高桥手中的袜子的颜色”这一个变量，因此可简单设计状态：
$E(x)$ 表示当高桥手中拥有颜色为 $x$ 的袜子时，还需要的期望抽取次数。

考虑如何进行状态转移：当高桥手中拥有颜色为 $x$ 的袜子时，他从抽屉柜中随机取出一只袜子，耗费一次抽取次数。接下来可能的情况有：

• 取出颜色为 $x$的袜子，此时操作终止，后续期望抽取次数为 $0$。
• 取出颜色不为 $x$的袜子（设颜色为 $y$），此操作的概率为 $\frac {A_y}S$。接下来他会选择能使未来期望抽袜次数最小化的那只袜子放回，后续期望抽取次数为$\min⁡(E(x),E(y))$。

因此可得状态转移方程：

这是一个自依赖且自依赖包括在 $\min$ 中的状态转移方程，乍一看似乎无法直接求解，然而我们可以感性理解一下：$A_i$越大，越容易一抽即中，因此 $E(i)$越小。故状态转移方程即可化为：

移项可得：

对 $A_i$ 排序（设按 $A$ 递增把颜色重新编号为 $1,2,\dots,N$），则上式化为前后缀可维护的形式：

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using ll = long long;
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    using mint = atcoder::modint998244353;
    int n, c;
    cin>>n>>c;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    mint sum = accumulate(a.begin()+1, a.end(), mint(0));
    a[c]++;
    vector<int> o(n+1);
    iota(o.begin()+1, o.end(), 1);
    sort(o.begin()+1, o.end(), [&](int i, int j) { return a[i]<a[j]; });
    vector<mint> E(n+1);
    mint pre=0, suf=0;
    for(int i=1;i<=n;i++) pre += a[o[i]];
    for(int i=n;i>=1;i--)
    {
        pre -= a[o[i]];
        E[i] = (sum+suf)/(sum-pre);
        suf += a[o[i]]*E[i];
        if(o[i]==c)
        {
            cout<<E[i].val()<<'\n';
            break;
        }
    }
}

vector<int> G[MAXN];

void dfs1(int u, int p) {
  f[u] = G[u].size();
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs1(v, u);
    f[u] += f[v];
  }
}

void dfs2(int u, int p) {
  if (u != root) g[u] = g[p] + f[p] - f[u];
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs2(v, u);
  }
}