定义
-
概率：某个随机事件出现的可能性大小。
事件 \(A\) 发生的概率记作 \(P(A)\)，其取值范围为 \([0,1]\)。
-
期望：若 \(X\) 是一个离散型的随机变量，可能的取值为 \(x_1,x_2,\dots,x_n\)，对应的概率分别为 \(p_1,p_2,\dots,p_n\)，那么它的期望值为 \(\sum_{i=1}^n p_ix_i\)。
随机变量 \(X\) 的期望记作 \(E(X)\)。
Practice 1
设随机变量 \(X\) 的取值范围为正整数，\(\forall 1\leq i<+\infty\), \(P(X=i)=2^{−i}\)。
-
求 \(E(x)\) 的值。
答案
设 \(S=E(x)=\sum_{i=1}^{\infty}\frac{i}{2^i}\)，有：
\[ \begin{align} 2S&=\sum_{i=1}^{+\infty}\frac{i}{2^{i-1}}\\ &=\sum_{i=0}^{+\infty}\frac{i+1}{2^i}\\ &=\sum_{i=0}^{+\infty}(\frac{i}{2^i}+\frac{1}{2^i})\\ &=\sum_{i=1}^{+\infty}\frac{i}{2^i}+\sum_{i=0}^{+\infty}\frac{1}{2^i}\\ &=S+\sum_{i=0}^{+\infty}\frac{1}{2^i} \end{align} \]又有：
\[ \begin{align} S&=2S-S\\ &=(S+\sum_{i=0}^{+\infty}\frac{1}{2^i})-S\\ &=\sum_{i=0}^{+\infty}\frac{1}{2^i}\\ \end{align} \]
\[ \begin{align} \frac{1}{2}S&=\sum_{i=0}^{+\infty}\frac{1}{2^i}\\ &=\sum_{i=0}^{+\infty}\frac{1}{2^{i+1}}\\ &=\sum_{i=1}^{+\infty}\frac{1}{2^i}\\ &=S-1 \end{align} \]我们成功地对 $S$ 完成了第一步的转化。接下来：
\[ \begin{align} \frac{1}{2}S&=S-1\\ S&=2S-2\\ S&=2 \end{align} \]根据上述式子，可以列出方程：解出答案 $E(x)=2$。 -
并且 \(\forall 1\leq i<+\infty\)，求 \(P(X\geq i)\)。
答案
设 \(S=P(X\geq i)=\sum_{j=1}^{+\infty}P(x=j)=\sum_{j=1}^{+\infty}\frac{1}{2^j}\)。
那么有：
\[ \begin{align} \frac{1}{2}S&=\sum_{j=i}^{+\infty}\frac{1}{2^{j+1}}\\ &=\sum_{j=i+1}^{+\infty}\frac{1}{2^{j}}\\ \end{align} \]
\[ \begin{align} \frac{1}{2}S&=\sum_{j=i+1}^{+\infty}\frac{1}{2^{j}}\\ &=\frac{1}{2^i} \end{align} \]根据子问题 $(1)$ 中的类似计算方法可得：
\[ \begin{align} \frac{1}{2}S&=\frac{1}{2^i}\\ S&=\frac{1}{2^{i-1}} \end{align} \]列出方程：
用 Tail Probability 求期望
有时候我们需要求解 \(E(X)\)，但是我们只知道 \(P(X\geq i)\) 的值，这时候就可以利用 \(\text{Tail Probability}\) 来求解 \(E(X)\)。
拿上面的问题 \((1)\) 举例：
\[\begin{align} E(X)&=\sum_{i=1}^{+\infty}i\times P(X=i)\\ &=\sum_{i=1}^{+\infty}\sum_{j=1}^iP(x=i)\\ &=\sum_{j=1}^{+\infty}\sum_{i=j}^{+\infty}P(X=i)\\ &=\sum_{j=1}^{+\infty}P(X\geq j) \end{align} \]此时，代入上述问题 \((2)\) 中的答案可得：
\[\begin{align} E(X)&=\sum_{j=1}^{+\infty}P(X\geq j)\\ &=\sum_{j=1}^{+\infty}\frac{1}{2^{j-1}}\\ &=2 \end{align} \]得到了相同的结果。
通过上述举例，我们容易发现： \(\text{Tail Probability}\) 本质是一种拆贡献的思想，在一些情况下可能有益于解题。
期望的线性性
对于两个随机变量：
-
\(E(X+Y)=E(X)+E(Y)\)
- \(X,Y\) 这两个随机变量不一定要独立。
-
\(E(aX)=aE(X)\)
- 同上，不要求 \(X,Y\) 独立。
-
\(E(XY)=E(X)E(Y)\)
- \(X,Y\) 必须要求独立，不合对方的取值相关。
上述的三条利用乘法分配律自证不难。
Practice 2
给出 \(n\) 个独立事件发生的概率 \(p_1,p_2,...,p_n\)。求至少有一个事件发生的概率。
下面给出两种解法：
解法1
利用简单容斥解决。用总概率减去一件事情也没发生的概率。
\[1-\prod_{i=1}^n (1-p_i) \]解法2
\[\sum_{i=1}^n(\prod_{j=1}^{i-1}p_j)\times p_i \]对每件事情算他作为编号最小的发生的事件的概率是多少，注意到这样不重不漏。
Practice 3
-
题目：CF280C。
-
题意：给出一颗 \(n\) 个节点的有根树（\(1\) 为根）。接下来会进行若干此操作，每次操作会从剩下的点中以相同的概率选择一个节点，并删去它的子树。操作直至树为空。求期望的操作次数。
\(1\leq n\leq 10^5\)
-
不妨进行拆贡献：设随机变量 \(X_i\) 表示 \(i\) 号点是否被操作（\(X_i=1\) 表示被选中，\(X_i=0\) 表示没被选中），那么有 \(answer=\sum E(X_i)\)。
考虑到 \(E(Xi)=P(X_i=1)\)，而 \(P(X_i=1)\) 当且仅当它在其所有祖先之前被选中。故 \(E(X_i)=P(X_i=1)=\frac{1}{depth_i}\)。
Practice 4
-
题意：给出一颗 \(n\) 个节点的树。接下来会进行若干次操作，每次会删除一个节点和所有与他相关的边，贡献为其所在连通块的大小。操作直至图为空。求期望的贡献和。
\(1\leq N \leq 10^5\)
-
进行拆贡献。考虑删除 \(u\) 点时如果 \(v\) 点还和 \(u\) 点处于同个连通块，那么 \(v\) 对 \(u\) 有 \(1\) 的贡献，此时满足 \(u\) 是 \(u\to v\) 路径上第一个被删除的点，概率为 \(\frac{1}{\text{dist}(i,j)+1}\)。
所以一种暴力的思路就是枚举 \(u,v\)，求贡献和。但是数据范围较大，可以统计每种长度的路径出现了多少次再求和，采用点分治+\(\text{FFT}\) 或者树上启发式合并+\(\text{FFT}\) 求解答案即可。
Practice 5
-
题目：CF1097D
-
题意：给定 \(n,k\)，一共会进行 \(k\) 次操作，每次操作会把 \(n\) 等概率的变成 \(n\) 的某个约数。
求操作 \(k\) 次后 \(n\) 的期望是多少，答案对 \(10^9+7\) 取。
\(1 \le n \le 10^{15},1 \le k \le 10^4\)
-
钦定 \(n=\prod_{i=1}^{c}p_i^{t_i}\)，\(X\) 为 \(n\) 经过 \(k\) 次操作后的随机变量，\(X_i\) 为 \(p_i^{t_i}\) 经过 \(k\) 次操作后的随机变量9满足 \(p_1,p_2,\dots,p_c\) 均为质数）。
容易发现，\(E(X)=\prod_{i=1}^cE(X_i)\)，也就是 \(E(X)\) 是一个积性函数。故而我们对 \(n\) 分解质因数后进行一遍 \(\text{DP}\) 即可。
具体的，假设当前是 \(n\) 的第 \(id\) 个质因子，且 \(f_{i,j}\) 为经过 \(i\) 次操作后，剩下的数为 \(p_{id}^j\) 的概率。转移为 \(f_{i,j}=\sum_{l=j}^{t_{id}}\frac{1}{l+1}f_{i-1,l}\)。最终的 \(E(X_{id})=\sum_{i=1}^{t_{id}}f_{k,i}\)。
- 当 \(k\) 很大的时候可以使用矩阵快速幂优化 \(\text{DP}\)。
-
代码
#include <bits/stdc++.h> #define FL(i, a, b) for(int i = (a); i <= (b); i++) #define FR(i, a, b) for(int i = (a); i >= (b); i--) using namespace std; typedef long long ll; const int N = 70, K = 1e4 + 10, p = 1e9 + 7; int k; ll t, n, ans = 1, f[K][N]; int qpow(int a, int b){ int ans = 1; for(; b; a = 1ll * a * a % p, b >>= 1) if(b & 1) ans = 1ll * ans * a % p; return ans; } int inv(int x){return qpow(x, p - 2);} ll F(int a, int b){ f[0][b] = 1; ll ret = 0, sum = 0; FL(i, 1, k){ sum = 0; FR(j, b, 0){ (sum += 1ll * f[i - 1][j] * inv(j + 1) % p) %= p; f[i][j] = sum; } } FL(i, 0, b) (ret += 1ll * f[k][i] * qpow(a, i) % p) %= p; f[0][b] = 0; return ret; } int main(){ scanf("%lld%d", &n, &k), t = n; FL(i, 2, sqrt(n)){ int c = 0; while(t % i == 0) t /= i, c++; if(c) ans = 1ll * ans * F(i, c) % p; } if(t > 1) ans = 1ll * ans * F(t % p, 1) % p; printf("%lld\n", ans); return 0; }
Practice 6
-
题目：AGC019F
-
题意：有 \(N+M\) 个问题，其中有 \(N\) 个问题的答案是
YES，\(M\) 个问题的答案是NO。当你回答一个问题之后，会知道这个问题的答案，求最优策略下期望对多少。答案对 \(998244353\) 取模。$ 1\leq N,M\leq500,000$
-
首先，不难得出选
YES答对的概率是 \(\frac{N}{N + M}\)，选NO答对的概率是 \(\frac{M}{N+M}\)。于是我们有如下结论：
假设 \(N > M\)，我们必定选
YES；相反 \(M > N\)，则必定选NO。由于
YES和NO没有本质之分，同时出于简化问题的考虑，不妨钦定 \(N \geq M\)。接着，易发现答案保底有 \(\max(N,M)\)，即 \(N>M\) 时带来的贡献。原因很简单：假设当前答案是
YES，答对了算进贡献；当前答案是NO，那么这一题答错了、但是 \(N\) 的值依旧没变，而 \(M\) 却减小了。如果按照这样下去（最坏情况），最后 \(M=0\) 之后你就能连续猜对 \(N\) 次。之后考虑 \(N=M\) 所带来的贡献。其实就是拿“期望出现的 \(N=M\) 的局面数”乘以 \(\frac{1}{2}\)（不管选
YES或NO都有 \(\frac{1}{2}\) 的概率答对）。具体的，我们对于前者，进行拆贡献。现在问题就转化为了求出现某个给定局面的概率，组合数求解即可。代码
#include <bits/stdc++.h> #define FL(i, a, b) for(int i = (a); i <= (b); i++) #define FR(i, a, b) for(int i = (a); i >= (b); i--) using namespace std; const int N = 1e6 + 10, p = 998244353; int n, m, s, ans, fac[N]; int qpow(int a, int b){ int ans = 1; while(b){ if(b & 1) ans = 1ll * ans * a % p; b >>= 1, a = 1ll * a * a % p; } return ans; } int inv(int x){return qpow(x, p - 2);} int C(int n, int m){ if(n < m || n < 0) return 0; if(!m) return 1; return 1ll * fac[n] * inv(fac[n - m]) % p * inv(fac[m]) % p; } int main(){ scanf("%d%d", &n, &m); if(m > n) swap(n, m); fac[0] = 1; FL(i, 1, n + m) fac[i] = 1ll * fac[i - 1] * i % p; FL(i, 1, m) (ans += 1ll * C(i * 2, i) * C(n - i + m - i, n - i) % p) %= p; printf("%d\n", (1ll * ans * inv(C(n + m, n)) % p * inv(2) + n) % p); return 0; }
求高阶矩
- 若我们关心的随机变量 \(X\) 可以拆成 \(\sum_{i=1}^n X_i\)，则二阶矩有：
三阶：
\[\begin{align} E(X^3)&=E((\sum_{i=1}^n X_i)^3)\\ &=E(\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n X_iX_jX_k)\\ &=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n E(X_iX_jX_k) \end{align} \]更高阶的以此类推。
Practice 7
-
题目：CF1187F
-
题意：有一个长度为 \(n\) 的序列 \(x\)。定义 \(B(x)\) 为 \(x\) 的颜色段数。
对于 \(\forall 1\leq i\leq n\)，\(x_i\) 将等概率为 \([l_i,r_i]\) 中的一个整数颜色。给出所有 \(l_i,r_i\)，求 \(E((B(x^2))^2)\)，即平方的期望。
-
考虑在每一段的开头算贡献：只要它和前面的数不同，它就是某一段的开头。
- 注意到上述贡献比实际的贡献少 \(1\)（开头那一段），但是并不影响我们做下去。
于是我们利用上述求二阶矩的方法，对于每一对开头 \((i,j)\) 算一下贡献。观察到大部分对的开头都是独立的，只有相邻的位置与同一个位置的不独立，故而分开考虑：
-
\(|i-j|>1\)
观察到这部分是独立的，对每个位置分开算。
-
\(|i-j|\leq 1\)
\(i=j\) 比较显然。对于 \(j=i+1\)，进行一个容斥（当前条件下，\(i,j\) 均为颜色段开头当且仅当 \(x_{i-1}\not=x_i\) 且 \(x_{i}\not=x_{j}\)）：贡献为 \(1-P(x_{i-1}=x_i)-P(x_{i}=x_{j})+P(x_{i-1}=x_i=x_{j})\)。
- 注意到上述贡献比实际的贡献少 \(1\)（开头那一段），但是并不影响我们做下去。
方差
- 方差的定义
根据定义，可推出：
\[Var(X)=E(X^2)-E(X)^2 \]即平方的期望减去期望的平方。
推导过程
\[\begin{align} Var(X)&=E((X-E(X))^2)\\ &=E((X-E(X))\times(X-E(X)))\\ &=E(X^2+E(X)^2-2\times X\times E(X))\\ &=E(X^2)+E(X)^2-E(2\times X\times E(X))\\ &=E(X^2)+E(X)^2-2\times E(X)^2\\ &=E(X^2)-E(X)^2 \end{align} \]Practice 8
-
题意：给定一个大小为 \(n\times m\) 的矩形，某一些格子上有物品，共有 \(k\) 个物品，现在等概率选一个子矩形，求子矩形内物品个数的方差。
-
由于 \(Var(X)=E(X^2)-E(X)^2\)，故考虑分别求等号后的两项。
\(E(X)^2\) 比较好算。根据期望的线性性，可以拆成 \(\sum_{i=1}^n\sum_{j=1}^m P((i,j)\text{ 被子矩形覆盖到的概率})\)，而他的概率就等于被覆盖到的方案数除以矩形的总数。后者的方案数易得（因为行和列是独立的），现在只关心前者——对于一个点 \((i,j)\)，它被覆盖到的方案数就是 \(i\times(n-i+1)\times j\times(m-j+1)\)。
求 \(E(X^2)\) 可以转化为：对于每一对点，统计包含它们的矩形的个数。\(k\) 较小的时候显然可以暴力求解，但在 \(k\) 大的时候还需要进一步的分析——我们不妨对两个点 \(x,y\) 的位置关系进行分类讨论：
-
\(x\) 在 \(y\) 的左上角（\(x\) 在 \(y\) 的右下角是等价的）
钦定 \(x,y\) 的坐标分别为 \((i,j),(k,t)\)，那么当前两个点都被矩形覆盖到的方案数是 \(i+(n-k+1)\times j+(m-t+1)\)。
易发现每个 \(x,y\) 的贡献值都独立，可用静态二维数点解决。
-
\(x\) 在 \(y\) 的右上角（\(x\) 在 \(y\) 的左下角）
钦定 \(x,y\) 的坐标分别为 \((i,j),(k,t)\)，那么当前两个点都被矩形覆盖到的方案数是 \(k+(n-i+1)\times j+(m-t+1)\)。
同上。
-
Practice 9
-
首先，必须先考虑一副牌是否是“胡”的，不然解决这道期望题就是无稽之谈。所以我们可以先把 \(7\) 个对子的特殊情况判掉，接下来用 \(\text{DP}\) 判断 \(1\) 个对子、\(4\) 个面子的情况。
用 \(f_{i,j,k,t}\) 表示考虑了前 \(i\) 种牌，是否已经有对子了（\(j=0\) 表示否，\(j=1\) 表示是），多余的像 \(i,i-1\) 这样的一组牌有 \(k\) 组，多余的第 \(i\) 种牌有 \(t\) 个的情况下，最大产生的面子数量。
接下来来回到这道题。设 \(X\) 表示最早产生胡牌的轮数的随机变量，\(p(x)\) 表示恰好 \(x\) 轮时第一次产生了胡牌的概率。
\[ E(X)=\sum_{x=0}^{4n-13} x \times p(x) \]\[ E(X)=\sum_{x=0}^{4n-13} \sum_{i=0}^{n-1} \times p(x) \]\[ E(X)=\sum_{i=0}^{4n-13} \sum_{x=i+1}^{4n-13} \times p(x) \]\[ E(X)=\sum_{i=0}^{4n-13} P(\text{x轮时还没有胡牌的概率}) \]\[ E(x)=\sum_{i=0}^{4n-13} \frac{\text{x轮时还没有胡牌的方案数}}{C_{4n-13}^i} \]所以我们的重中之重就是求出 \(x\) 轮还没有胡牌的方案数。
我们使用 \(\text{DP}\) 套 \(\text{DP}\) 解决此问题。我们把上述简易 \(\text{DP}\) 的状态和其对应的对子数量作为内层 \(\text{DP}\) 状态给压缩起来（注意 \(i\) 那维不要压进去，之后会把那一维单独地放入外层的状态里），我们发现实际有用的状态可能很少，故而用搜索找。那么我们外层的状态就显而易见了：\(dp_{i,j,k}\) 表示前 \(i\) 种牌，内层状态为 \(j\)，总共选了 \(k\) 张的方案数。
至于查询没有胡牌的方案数，只需要判断加求和就行了。