一.基本概念

数学期望（简称期望），是试验中每次可能结果的概率乘以其结果的总和，它反映了随机变量平均取值的大小。

对于随机变量 \(X\)，它有 \(n\) 种可能的取值，取值为 \(x_i\) 的概率为 \(P(x_i)\)，那么它的数学期望 \(E(X)=\Sigma _{i=1}^{n} x_i P(x_i)\)。

举个例子：给定一个随机变量 \(X\)，它有六种可能的取值，分别是 \(1,2,3,4,5,6\)，且取每个值得概率是一样的，那么 \(E(X)=\frac{1}{6}×1+\frac{1}{6}×2+\frac{1}{6}×3+\frac{1}{6}×4+\frac{1}{6}×5+\frac{1}{6}×6=\frac{7}{2}\)。

数学期望可以用加权平均数来理解，可能取值就是初始数据，概率就是每个数的权，此时期望就是加权平均数。

二.性质

设 \(A,B,C\) 为常数， \(X,Y\) 为随机变量，那么有：

• \(E(C)=C\)；
• \(E(CX)=CE(X)\)；
• \(E(X+Y)=E(X)+E(Y)\)；
• \(X,Y\) 互相独立时， \(E(XY)=E(X)E(Y)\)；
• 结合上列性质，得出 \(X,Y\) 互相独立时 \(E(AX+BY)=AE(X)+BE(Y)\)。

三.例题讲解

Ybtoj【例题1】单选错位

P1297 [国家集训队]单选错位

分四种情况讨论：

• \(1.\) 每道题选项个数都相同：设每道题有 \(a\) 个选项，那么选对一道题的概率为 \(\frac{1}{a}\)，所以 \(E(ans)=\frac{n}{a}\)。

• \(2.\) 对于第 \(i\) 题，当 \(a_i<a_{i+1}\) 时，第 \(i+1\) 题的答案与第 \(i\) 题答案相同的概率为 \(\frac{1}{a_{i+1}}\)，即答对第 \(i+1\) 题的概率为 \(\frac{1}{a_{i+1}}\)，

• \(3.\) 当 \(a_i=a_{i+1}\) 时，同第 \(2\) 条。

• \(4.\) 当 \(a_i>a_{i+1}\)，第 \(i\) 题与第 \(i+1\) 题答案相同的概率为 \(\frac{1}{a_i}\)，即答对第 \(i+1\) 题的概率为 \(\frac{1}{a_i}\)。

综上所述，我们记答对第 \(i\) 题的概率为 \(P(i)\)，期望为 \(E(ans_i)\)。答对一道题，对总答案的贡献为 \(1\)，因此对于第 \(i\) 题，答对的期望 \(E(ans_i)=P(i)×1=P(i)\)。所以，\(E(Ans)=E(\sum ^{n}_{i=1} ans_i)=\sum ^{n}_{i=1}E(ans_i)=\sum ^{n}_{i=1}P(i)\)。

核心代码：

a[n + 1] = a[1];
double ans = 0;
for (int i = 1; i <= n; i ++) {
	ans += 1.0 / max (a[i], a[i + 1]);
}

Ybtoj【例题2】期望分数

P1365 WJMZBMR打osu! / Easy

先思考一下，在连续 \(a\) 个 \(o\) 后面再加一个 \(o\)，会对答案产生多少贡献？

显然，会多贡献 \((a+1)^2-a^2=a^2+1+2a-a^2=2a+1\)。

当处理到第 \(i\) 位时，我们可以知道以第 \(i\) 位为结尾的连续 \(o\) 的期望长度，根据 连续 \(o\) 的期望长度，就可以轻松算出期望分数。

核心代码：

for (int i = 1; i <= n; i++) {
    if (c[i] == 'o') {
        ans += len * 2 + 1;//一定是，累计贡献。
		len++;//同上。
    }

    else if (c[i] == 'x') {
        len = 0;//一定不是，期望长度归0。
    }

    else {
        ans += (len * 2 + 1) / 2;//有一半的概率不是o，所以要除以2。
        len = (len + 1) / 2;//同上。
    }
}

Ybtoj【例题3】路径长度

P4316 绿豆蛙的归宿

因为已知最终状态，那么逆推。

设有向边 \(x\to y\)，那么有 \(f_x=(\frac{1}{deg_x})\Sigma f_y + w_{x\to y}\)。

因为反向建边，所以我们要把 \(x,y\) 颠倒过来。

核心代码：

queue <int> q;
q.push (n);
while(!q.empty()) {
	int u = q.front();
	q.pop();
	for(int i=head[u]; i; i = e[i].from) {
		int v = e[i].to;
		f[v] += (f[u] + e[i].w) / dg[v];
		if(--in[v] == 0) {
			q.push (v);
		}
	}
}