一.数学期望的概念

「学习笔记」期望问题 是学习期望概率dp的基础，建议学习后再来阅读该学习笔记。

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

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

---

二.数学期望的计算公式

对于随机变量 \(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)\)。

---

四.期望dp

求解达到某一目标的期望代价：因为最终的代价我们不知道，所以需要倒序求解。

设 \(f_{i,j}\) 为在 \((i,j)\) 这个状态实现目标的期望代价（相当于相距目标多少）。

当然我们也可以采用正序求解，只需要将状态的意义确定，符合要求，就可以求解。

---

五.例题讲解

Ybtoj【例题1】路径长度

P4316 绿豆蛙的归宿

因为已知最终状态，按照期望dp的想法，我们采用逆推。

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

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

在 \(DAG\) 上进行拓扑排序即可转移状态。

核心代码：

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);
		}
	}
}

Ybtoj【例题2】乘坐电梯

CF518D Ilya and Escalator

设 \(f_{i,j}\) 为在第 \(i\) 个人，第 \(j\) 秒时电梯上的期望人数。

那么，易得 \(f_{i,j}=(1-p)×f_{i, j - 1} + p×(f_{i-1,j-1}+1)\)。

最后输出 \(f_{n,t}\) 即可。

Ybtoj【例题3】期望收益

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【例题4】期望分数

P1654 OSU!

和上题相似，但是指数为 \(3\)。

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

计算出会多贡献 \((a+1)^3-a^3=a^3+3a^2+3a+1-a^3=3a^2+3a+1\)。

设 \(E(X_i)\) 为在第 \(i\) 位得的分数期望，我们思考一下 \(E(X_i)\) 和 \(E(X_{i+1})\) 的关系。

假设在 \(i\) 位置连续 \(1\) 串长度为 \(l\) 的概率为 \(p_{l}\)，在 \(i+1\) 位置是 \(1\) 的概率为 \(P\) ，那么对于每一个单独的 \(l\) 它都有 \(P\) 的概率对分数产生 \((3l^{2}+3l+1)\)的额外贡献。

我们把所有可能的 \(l\) 一起考虑，就可以得到这个式子：
\(E(X_{i+1})=E(X_i)+P×\Sigma_{l=0}^{i}p_l(3l^2+3l+1)\)。

然后我们将式子转化为：
\(E(X_{i+1})=E(X_i)+P×(3E(l_i^2)+3E(l_i)+1)\)

接下来维护 \(E(l)\) 和 \(E(l^2)\)。

于是我们可以这么算：
\(E(l_{i+1}=P×(E(l_i)+1)\)

\(E(l_{i+1}^2=P×(E(l_i^2)+2E(l_i)+1)\)。

然后我们递推，用三个变量存储即可。

核心代码：

for (int i = 1; i <= n; i ++) {
	ans += (3 * len2 + 3 * len1 + 1) * p[i];
	len2 = (len2 + 2 * len1 + 1) * p[i];		
	len1 = (len1 + 1) * p[i];
}
printf ("%.1lf", ans);