数学期望专题

一、数学期望

概念：简单地说，随机变量 X 的数学期望 E(X) 就是所有可能的值按照概率加权的和。

求解方法：按照定义求解。

计算出所有可能的值
计算出对应的概率
求出可能的加权和

求解工具

期望的线性性质：有限个随机变量之和的数学期望等于每个随机变量的数学期望之和。例如，对于两个随机变量 X 和 Y，E(X + Y) = E(X) + E(Y)。
全期望公式：类似于全概率公式，把所有情况不重复、不遗漏地分成若干类，每类计算数学期望，然后把这些数学期望按照每类地概率加权求和。

二、Practice

过河 Crossing Rivers

题目链接：过河 Crossing Rivers - 洛谷

过河的最小时间 $t_{min} = \frac{L}{v}$ ，最大时间 $t_{max} = \frac{3L}{v}$ ，由于过河的时间是连续的，所以过河时间的期望 $E(t) = \frac{2L}{v}$ （船正好在岸边时间最小，船刚走时间最大）。

最终的答案就是，陆地距离 + 过河期望时间。

#include <bits/stdc++.h> using namespace std; int n, D, p, L, v; double ans; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int main() { int t = 0; while (1) { n = read(), D = read(); if (!n && !D) break; ans = 1.0 * D; while (n--) { p = read(), L = read(), v = read(); ans += 2.0 * L / v - L; } printf("Case %d: %.3lf\n\n", ++t, ans); } return 0; }

优惠券 Coupons

题目链接：优惠券 Coupons

假设我们某个情况下，我们已经有了 k 种图案，在这个条件下，获得一个新图案需要 t_k 天，那我们要求的就是 $\sum_{k = 0}^{n - 1}E(t_k)$ 。由于已经有了 k 种图案，那么获得一个新图案的概率就是 $\frac{n - k}{n}$ ，那么期望天数 $E(t_k) = \frac{n}{n - k}$ ，最终答案就是 $\sum_{k = 0}^{n - 1}E(t_k) = \sum_{k = 0}^{n - 1}\frac{n}{n - k} = \sum_{i = 1}^{n} \frac{n}{i}$

要注意一下分数时候的输出格式。

~~另外就是这道题我刚开始给卡常了，有点ex。~~

#include <bits/stdc++.h> using namespace std; #define int long long int n, x, y; int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); } signed main() { while (scanf("%lld", &n) != EOF) { x = n, y = 1; for (int i = 2; i <= n; i++) { x = x * i + y * n, y *= i; int GCD = gcd(x, y); x /= GCD, y /= GCD; } if (x % y == 0) printf("%lld\n", x / y); else { int a = x / y; x %= y; int lena = log10(a) + 1, leny = log10(y) + 1; for (int i = 0; i <= lena; i++) printf(" "); printf("%lld\n%lld ", x, a); for (int i = 1; i <= leny; i++) printf("-"); puts(""); for (int i = 0; i <= lena; i++) printf(" "); printf("%lld\n", y); } } return 0; }

Bag of mice

题目链接：Bag of mice - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 和 Problem - 148D - Codeforces

假设当前有 x 个白鼠，y个黑鼠

x = 0 时，A 获胜的概率为 0。
y = 0 时，A 获胜的概率为 1。
A 拿白鼠直接获胜。
A 拿黑鼠

B 拿黑鼠，跑出来一只黑鼠，A 获胜的概率为 $\frac{y}{x+y}\frac{y-1}{x+y-1}\frac{x}{x+y-2}f(x-1,y-2)$ 。
B 拿白鼠，跑出来一只白鼠，A 获胜的概率为 $\frac{y}{x+y}\frac{y-1}{x+y-1}\frac{y-2}{x+y-2}f(x,y-3)$ 。

分别有 记忆化搜索 和 概率DP 两种写法。

记忆化搜索

#include <bits/stdc++.h> using namespace std; #define double long double int w, b; double vis[1005][1005]; double f(int x, int y) { if (x == 0) return 0.0; if (y == 0) return 1.0; if (vis[x][y] > 0) return vis[x][y]; vis[x][y] = 1.0 * x / (x + y); if (x >= 1 && y >= 2) vis[x][y] += 1.0 * x * y * (y - 1) / (x + y) / (x + y - 1) / (x + y - 2) * f(x - 1, y - 2); if (y >= 3) vis[x][y] += 1.0 * y * (y - 1) * (y - 2) / (x + y) / (x + y - 1) / (x + y - 2) * f(x, y - 3); return vis[x][y]; } int main() { scanf("%d%d", &w, &b); for (int i = 1; i <= w; i++) for (int j = 1; j <= b; j++) vis[i][j] = 0.0; printf("%.9Lf", f(w, b)); return 0; }

概率DP

#include <bits/stdc++.h> using namespace std; #define double long double int w, b; double f[1005][1005]; int main() { scanf("%d%d", &w, &b); for (int i = 1; i <= w; i++) f[i][0] = 1.0; for (int i = 0; i <= b; i++) f[0][i] = 0.0; for (int i = 1; i <= w; i++) { for (int j = 1; j <= b; j++) { f[i][j] = 1.0 * i / (i + j); if (i >= 1 && j >= 2) f[i][j] += 1.0 * i * j * (j - 1) / (i + j) / (i + j - 1) / (i + j - 2) * f[i - 1][j - 2]; if (j >= 3) f[i][j] += 1.0 * j * (j - 1) * (j - 2) / (i + j) / (i + j - 1) / (i + j - 2) * f[i][j - 3]; } } printf("%.9Lf", f[w][b]); return 0; }

P1654 OSU!

题目链接：P1654 OSU! - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

设 f_i 位前 i 位的期望分数， x_i 表示前 i 位末尾的连续的 1 的期望长度。可以得到

$x_i = \left\{\begin{matrix} 0, \hspace{1em}1 - p_i\\ x_{i - 1} + 1, \hspace{1em}p_i \end{matrix}\right.$ 所以 $x_i = (x_{i - 1} + 1)p_i$

第 i 位为 1 的概率为 p_i ，所以

$f_i = f_{i - 1} + ((x_{i - 1} + 1) ^3 - x_{i - 1}^3)p_i = f_{i - 1} + (3x_{i - 1}^2 + 3x_{i - 1} + 1)p_i$ 即 $f_i = f_{i - 1} + (3y_{i - 1} + 3x_{i - 1} + 1)p_i$

所以除了 x_i 以外，还需要记录前 i 位末尾的连续的 1 的期望长度的平方 y_i 。

$y_i = \left\{\begin{matrix} 0, \hspace{1em} 1 - p_i\\ (x_{i - 1} + 1)^2 = x_{i - 1}^2 + 2x_{i- 1} + 1 = y_{i - 1} + 2x_{i - 1} +1, \hspace{1em}p_i \end{matrix}\right.$ ，所以 $y_i = (y_{i - 1} + 2x_{i - 1} + 1)p_i$

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n; double f[N], x[N], y[N], d; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%lf", &d); x[i] = (x[i - 1] + 1) * d; y[i] = (y[i - 1] + 2 * x[i - 1] + 1) * d; f[i] = f[i - 1] + (3 * y[i - 1] + 3 * x[i - 1] + 1) * d; } printf("%.1lf", f[n]); return 0; }

P4550 收集邮票

题目链接：P4550 收集邮票 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

假设 num(i) 为拿到第 i 张邮票的期望次数，f(i) 为拿到 i 张邮票的期望次数。

当拿到 i - 1 张邮票时，有 $\frac{n - i + 1}{n}$ 的概率拿到一张新的邮票，所以在这个条件下拿到一张新的邮票的次数期望是 $\frac{n}{n - i + 1}$ ，所以 $num(i) = num(i-1) + \frac{n}{n - i + 1}$ 。

由于拿到第 i 张邮票的次数和每次的花费相互独立，拿到第 i 张邮票的花费 = 拿到第 i 张邮票的次数 x 每次的花费，拿到第 i 张邮票的次数的期望是 $\frac{n - i + 1}{n}$ ，每次的花费的期望是 num(i)，所以 $f(i) = f(i - 1) + \frac{n}{n - i + 1} \cdot num(i)$ 。

由于 num 和 f 都只与前一位有关系，所以可以对空间进行压缩，没必要用数组记录数据。

补充：对于随机变量 X, Y，如果 X 和 Y 相互独立，E(XY) = E(X) * E(Y)

#include <bits/stdc++.h> using namespace std; int n; double f, num; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { num += 1.0 * n / (n - i + 1); f += num * n / (n - i + 1); } printf("%.2lf", f); return 0; }

Sugar Sweet II

题目链接：2023ICPC区域赛杭州站H题

当的时候，无论 a[b[i]] 是否更新，即无论事件以什么顺序发生，a[i] 一定会被更新，则第 i 个孩子手上的糖的期望为 a[i] + w[i]。
当 $a[i] \ge a[b[i]] + w[b[i]]$ 的时候，无论 a[b[i]] 是否更新，即无论事件以什么顺序发生，a[i] 一定无法更新，则第 i 个孩子手上的糖的期望为 a[i]。
除去以上两种情况，a[i] 是否更新取决于 a[b[i]] 是否更新。对于这种情况，我们可以以 (b[i], i) 建一张有向图，记录一个 dis 表示该节点更新前有多少个节点需要更新，第一种情况的 dis 记为 1，第二种情况的 dis 记为 0，通过 dfs 遍历得到每一个节点的 dis。每一个节点可以更新的概率就是 $\frac{1}{dis!}$ ，因为只需要这 dis 个节点以这一种特定顺序排列就可以保证该节点被更新。期望就是 $\frac{1}{dis!} (a[i] + w[i]) + (1 - \frac{1}{dis!})a[i] = a[i] + \frac{w[i]}{dis!}$ ，最后要求乘法逆。

对于 $\frac{x}{y}\equiv ans(mod \hspace{0.5em}p)$ 即 $\frac{ans}{x} \cdot y \equiv 1 (mod \hspace{0.5em} p)$ 的乘法逆，根据费马小定理，当 a 和 p 互质的时候，有 $a^{p - 1} \equiv 1 (mod \hspace{0.5em} p)$ ，则 $\frac{ans}{x} = y ^{p - 2} \hspace{0.2em} \% \hspace{0.2em} p$ 即 $ans = x \cdot y ^{p - 2} \hspace{0.2em} \% \hspace{0.2em} p$ 。

#include <bits/stdc++.h> using namespace std; #define int long long const int N = 5e5 + 10, mod = 1e9 + 7; int a[N], b[N], w[N], fac[N], dis[N], head[N], num = 0; struct edge { int to, nxt; } e[N]; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } void addEdge(int u, int v) { e[++num] = (edge){v, head[u]}, head[u] = num; } int qpow(int x, int k) { int res = 1LL; while (k) { if (k & 1) res = res * x % mod; x = x * x % mod; k >>= 1; } return res; } void dfs(int u) { for (int i = head[u], v; i; i = e[i].nxt) { v = e[i].to; dis[v] = dis[u] + 1; dfs(v); } } signed main() { fac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod; int t = read(); while (t--) { int n = read(); for (int i = 1; i <= num; i++) e[i] = {0, 0}; num = 0; for (int i = 1; i <= n; i++) a[i] = read(), dis[i] = 0; for (int i = 1; i <= n; i++) b[i] = read(), head[i] = 0; for (int i = 1; i <= n; i++) w[i] = read(); for (int i = 1; i <= n; i++) { if (a[i] < a[b[i]]) dis[i] = 1; else if (a[i] >= a[b[i]] + w[b[i]]) dis[i] = 0; else addEdge(b[i], i); } for (int i = 1; i <= n; i++) if (dis[i] == 1) dfs(i); for (int i = 1; i <= n; i++) { if (dis[i] == 0) printf("%lld ", a[i]); else printf("%lld ", (a[i] + w[i] * qpow(fac[dis[i]], mod - 2) % mod) % mod); } puts(""); } return 0; }

今天的文章数学期望专题分享到此就结束了，感谢您的阅读。