概率和期望
对于随机变量 \(X\)，设其第 \(i\) 种取值为 \(x_i\)，出现的概率是 \(P(X=x_i)\)，则其期望 \(E(x)\) 定义为：
\[
E(X)=\sum_{i=1}{x_iP(X=x_i)}
\]
数学期望反映变量平均取值的大小。
性质
线性性
不需要两变量无关：
\[
\begin{align*}
&E(X+Y)=E(X)+E(Y)\\
&E(aX)=aE(X)
\end{align*}
\]
证明
可加性：
\[
\begin{align*}
&E(X+Y)\\
=&\sum_{i}\sum_{j}(x_i+y_j)P(X=x_i,Y=y_j)\\
=&\sum_{i}\sum_{j}x_i P(X=x_i,Y=y_j)+\sum_{i}\sum_{j}y_j P(X=x_i,Y=y_j)\\
=&\sum_{i}x_i\sum_{j}P(X=x_i,Y=y_j)+\sum_{j}y_j\sum_{i}P(X=x_i,Y=y_i)\\
=&\sum_{i}x_i P(X=x_i)+\sum_{j}y_j P(Y=y_j)\\
=&E(X)+E(Y)
\end{align*}
\]
数乘性：
\[
\begin{align*}
&E(aX)\\
=&\sum_{x}{axP(X=x)}\\
=&a\sum_{x}{xP(X=x)}\\
=&aE(X)
\end{align*}
\]
可乘性
需要 \(x\) 和 \(y\) 相互独立：
\[
E(XY)=E(X)E(Y)
\]
全期望公式
\[
E(X)=\sum_{y_i}{E(X|Y=y_i)P(Y=y_i)}
\]
例题
题目大意
试卷上共有 \(n\) 道单选题，第 \(i\) 道单选题有 \(a_i\) 个选项，每个选项成为正确答案的概率都是相等的。
如果你将第 \(i\) 道题的正确答案填到了第 \(i+1\) 道题的位置上（特别的，你将第 \(n\) 道题的答案填到了第 \(1\) 道题的位置上），问做对题数量的期望是多少。
可以将每道题看作一个随机变量 \(X_i\)，做对了取值为 \(1\)，没做对为 \(0\)。根据期望的线性性，我们只需求出每道题作对的期望是多少就可以了。
我们将 \(a_1\) 的值复制到 \(a_{n+1}\) 的位置上，就无需考虑 \(n\rightarrow 1\) 的情况了。
考虑 \(a_i\) 和 \(a_{i+1}\) 的大小关系：
- 若 \(a_i\ge a_{i+1}\)，做对第 \(i+1\) 道题的概率为 \(\frac{1}{a_{i}}\)；
- 若 \(a_i< a_{i+1}\)，做对第 \(i+1\) 道题的概率为 \(\frac{1}{a_{i+1}}\)；
由期望的定义得到
\[
E(X_i)=1\times P(X_i)+0\times \big(1-P(X_i)\big)=P(X_i)
\]
又因为
\[
P(X_i=1)=\frac{1}{\max(a_i,a_{i+1})}
\]
所以答案为
\[
\sum_{i=1}^{n}{\frac{1}{\max(a_i,a_{i+1})}}
\]
题目大意
给定一个长度为 \(n\) 的字符串，由 a，b，? 组成。计算分数的规则如下：极长的连续 \(x\) 个 a 可以得到 \(x^2\) 分。对于 ? 的地方，有 \(\frac{1}{2}\) 的概率为 a ，另外 \(\frac{1}{2}\) 的概率为 b，求该字符串的期望分数。
我们将连续段产生的贡献统一下放到右端点处理。
考虑第 \(i\) 位的边际贡献。若 \([1,i-1]\) 中末尾的连续段长度为 \(x_{i-1}\)，则应对答案产生 \((x_{i-1}+1)^2-x_{i-1}^2=2x_{i-1}+1\) 的贡献。这个式子是线性的，可以直接使用期望的线性性进行计算。设 \([1,i-1]\) 段的末尾连续段长度的期望为 \(x_{i-1}\)，则第 \(i\) 位的贡献为：
\[
\begin{cases}
2x_{i-1}+1 ,&c_i=\text{'a'}\\
0 ,&c_i=\text{'b'}\\
\frac{2x_{i-1}+1}{2} ,&c_i=\text{'?'}
\end{cases}
\]
\(x\) 的转移：
\[
x_i=
\begin{cases}
x_{i-1}+1 ,&c_i=\text{'a'}\\
0 ,&c_i=\text{'b'}\\
\frac{x_{i-1}+1}{2} ,&c_i=\text{'?'}
\end{cases}
\]
代码
| #include<iostream>
using namespace std;
const int N = 3E5 + 10;
int n;
double Elen, ans;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
char c;
cin >> c;
if(c == 'o') {
ans += Elen * 2 + 1;
Elen = Elen + 1;
} else if(c == 'x') {
Elen = 0;
} else {
ans += (Elen * 2 + 1) / 2;
Elen = (Elen + 1) / 2;
}
}
printf("%.4lf\n", ans);
return 0;
}
|
题意
有一个长度为 \(n\) 的 01 串，第 \(i\) 个位置有 \(p_i\) 的概率为 1，\(1-p_i\) 的概率为 0。一串长度为 \(x\) 的极长的连续的 1 会产生 \(x^3\) 的价值。
问原串价值之和的期望是多少。
考虑长度为 \(i-1\) 的前缀，设其内部的价值之和为 \(f_{i-1}\)，其末尾连续 1 的长度为 \(x_{i-1}\)。考虑第 \(i\) 位的边际贡献：
\[
\begin{cases}
(x_{i-1}+1)^3-x_{i-1}^3,&a_i=1\\
0,&a_i=0
\end{cases}
\]
将第一种情况展开：
\[
(x_{i-1}+1)^3-x_{i-1}^3=3x_{i-1}^2+3x_{i-1}+1
\]
我们只要知道了 \(E(x_{i-1}^2)\) 和 \(E(x_{i-1})\)，就可以立刻求出该位产生贡献的期望。
如果我们只记录 \(E(x_{i-1})\)，则无法求出 \(E(x_{i-1}^2)\)，因为乘法要求两个变量无关。但我们可以同时记录 \(E(x_{i-1}^2)\)：
\[
x_i^2=
\begin{cases}
(x_{i-1}+1)^2,&a_i=1\\
0,&a_i=0
\end{cases}
\]
展开第一种情况：
\[
x_i^2=x_{i-1}^2+2x_{i-1}+1
\]
因此
\[
E(x_i^2)=\Big(E(x_{i-1}^2)+2E(x_{i-1})+1\Big)p_i
\]
这说明，我们可以通过 \(E(x_{i-1})\) 和 \(E(x_{i-1}^2)\) 直接递推出 \(E(x_{i}^2)\)。开三个变量，分别记录 \(f_i\)，\(E(x_i)\)，\(E(x_i^2)\) 即可。
代码
| #include<iostream>
#include<iomanip>
#define ld long double
using namespace std;
const int N = 1e5 + 10;
int n;
ld x1, x2, f;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
ld p;
cin >> p;
f = f + p * (3 * x2 + 3 * x1 + 1);
x2 = p * (x2 + 2 * x1 + 1);
x1 = p * (x1 + 1);
}
cout << fixed << setprecision(1) << f << endl;
return 0;
}
|
题意
给定一个 \(n\) 个点 \(m\) 条边的无向连通图。初始你位于 \(1\) 号节点，每一步你会等概率的走向当前节点连接的任意一条边，同时获得等于这条边编号的分数。当你走到 \(n\) 号节点，游戏立即结束。
问应该如何给边编号，使得游戏结束时的期望得分最小。
\(n\le 500,\ m\le \frac{n(n-1)}{2}\)
我们只需要知道游戏结束之前，每条边期望被走过的次数，然后将所有边按照这个期望降序排序，依次赋予 \([1,m]\) 的编号，即可最小化期望得分。
记 \(g(u,v)\) 表示在游戏结束之前走过 \(u\rightarrow v\) 的单向边的期望次数。那么边 \((u,v)\) 被走过的期望次数就是 \(g(u,v)+g(v,u)\)。
考虑 \(g(u,v)\) 之间的转移。显然有：
\[
\sum_{v}{g(u,v)}-\sum_{v}{g(v,u)}=
\begin{cases}
0,&u\ne 1\text{ and } u\ne n\\
1,&u=1\\
-1,&u=n\\
\end{cases}
\]
然而，如果我们直接依照这个式子，以所有 \(g(u,v)\) 为未知数列出一个线性方程组，其系数矩阵不一定满秩。比如，考虑一个最简单的情况：\(n=2\)，其对应的方程组为：
\[
\begin{cases}
g(1,2)-g(2,1)=1\\
g(2,1)-g(1,2)=-1\\
\end{cases}
\]
有无穷解。
事实上，我们还没有利用“等概率前往任意一条边”这个条件。根据这个条件，可以推导出：从一个点出发前往每条边的期望次数也是均匀的，即 \(\forall u,\ \forall v_1,v_2\in to[u], \ g(u,v_1)=g(u,v_2)\)。
证明
设事件 \(A_i\) 表示一共经过了 \(u\) 节点 \(i\) 次；变量 \(B\) 表示从 \(u\) 走到 \(v\) 的次数；\(Y_j\in\{0,1\}\) 表示第 \(j\) 次到达 \(u\) 节点时，是否前往了 \(v\) 节点。
\[
\begin{align*}
E(B)&=\sum_{i=0}^{\infty}{E(B\mid A_i)P(A_i)}\\
&=\sum_{i=0}^{\infty}{E\Big(\sum_{j=1}^{i}Y_j\mid A_i\Big)P(A_i)}\\
&=\sum_{i=0}^{\infty}{\Big(\sum_{j=1}^{i}E\big(Y_j\mid A_i\big)\Big)P(A_i)}
\end{align*}
\]
显然，第 \(j\) 次的选择和 \(A_i\) 无关。设变量 \(C\) 表示到达 \(u\) 节点的次数，上式等于：
\[
\begin{align*}
&\sum_{i=0}^{\infty}{\Big(\sum_{j=1}^{i}E(Y_j)\Big)P(A_i)}\\
=&\sum_{i=0}^{\infty}{\frac{i}{deg[u]}P(A_i)}\\
=&\frac{1}{deg[u]}\sum_{i=0}^{\infty}{iP(A_i)}\\
=&\frac{1}{deg[u]}E(C)\\
\end{align*}
\]
和 \(v\) 无关。
加入这个条件后，方程组变得异常复杂，方程的数量比未知数的数量多。然而我们注意到，既然 \(g(u,v)\) 只与 \(u\) 有关，不如从节点的角度考虑。记 \(f(u)\) 表示 \(u\) 节点期望被经过的次数（即 \(E(C)\)），容易写出转移式：
\[
f(u)=\sum_{v\in to[u]}{\frac{f(v)}{deg[v]}}
\]
从点的角度考虑还有一个好处：方程的数量为 \(O(n)\) 级别。我们只需要使用高斯消元即可 \(O(n^3)\) 求出所有 \(f(u)\)。这个方程每行只有第 \(i\) 列是 \(-1\)，其它位置均为非负，系数矩阵显然满秩。
求出 \(f(u)\) 之后，根据 \(g(u,v)=\frac{f(u)}{deg[u]}\) 即可求出每条边期望经过的次数。
代码
| #include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#define ld long double
using namespace std;
const int N = 510;
struct Edge {
int u, v;
} edg[N * N];
int n, m;
int deg[N];
ld w[N * N];
ld a[N][N];
// 矩阵必然满秩，因此消元得到的增广矩阵的系数部分必为单位矩阵，无需特判其它情况
void gs() {
for(int i = 1; i <= n - 1; i++) {
int mx = i;
for(int j = i + 1; j <= n - 1; j++) {
if(abs(a[j][i]) > abs(a[mx][i])) mx = j;
}
for(int j = 1; j <= n; j++) swap(a[i][j], a[mx][j]);
for(int j = n; j >= i; j--) a[i][j] /= a[i][i];
for(int j = 1; j <= n - 1; j++) {
if(j == i) continue;
for(int k = n; k >= i; k--) a[j][k] = a[j][k] - a[j][i] * a[i][k];
}
}
}
vector<int> adj[N];
ld ans;
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
edg[i] = {u, v};
adj[u].push_back(v);
adj[v].push_back(u);
++deg[u];
++deg[v];
}
for(int i = 1; i <= n - 1; i++) {
for(int &j : adj[i]) {
if(j != n) a[i][j] = 1.0l / deg[j];
}
a[i][i] = -1;
}
a[1][n] = -1;
gs();
for(int i = 1; i <= m; i++) {
int u = edg[i].u, v = edg[i].v;
w[i] = a[u][n] / deg[u] + a[v][n] / deg[v];
}
sort(w + 1, w + 1 + m);
for(int i = 1; i <= m; i++) {
ans += (m - i + 1) * w[i];
}
cout << fixed << setprecision(3) << ans << endl;
return 0;
}
|