期望与期望DP

wxhnlex · 2026-10-15 15:38:49 · 算法·理论

前景提要

由于初学期望与期望 DP 就没有怎么听懂，再加之今天模拟赛的 T2 考了一道纯血期望 DP。本来有望打出一个朴素做法的，但是因为对于期望的陌生，导致对数据不知如何处理，一度导致我十分懊悔。这里写一篇笔记，重新梳理一下期望与期望 DP。

前置知识

1. 定义

先对期望整体下一个定义。

通俗来讲，期望就是在随机事件集合内，每一种随机事件的贡献乘上其对应概率的和。

形象化的表示一下：

2. 线性性质

对期望有了一个基本的定义并了解了计算方法之后，我们可以得到以下性质。

3. 全期望公式

设 X 是一个离散型随机变量，当 X = x_i 时，随机变量 Y 可能包含多种情况 y_1, y_2, \dots, y_k，随机变量 Y 的条件数学期望为：

有一点类似于定义式，那么这个公式的含义是什么呢。

这个公式表现出了上面所提到的期望的线性性质，表示当一个随机变量 X = x_i 时，它所对应的期望，就是所有在 X = x_i 这一条件下，所有它的贡献（这里记作变量 Y）乘上触发这一贡献的概率的和。

常见期望模型

A

有 n 个随机变量 X_i，每个随机变量都是从 [1, m] 中随机一个整数，求 \max(X_i) 的期望。

不妨设 S = \max(x_i)_{i = 1}^{n}，那么我们由期望的定义式可以得到：

利用前缀和我们可以将 \operatorname{P} 展开得到 \operatorname{P}(S = i) = \operatorname{P}(S \le i) - \operatorname{P}(S \le i - 1)。然后我们又会发现 S \le i 等价于 (x_j)_{j = 1}^{n} \le i（PS. 通俗来讲就是所有的 x 均小于 i）。那么我们就可以得到：

PS. 关于 \left(\frac{i}{m}\right)^n 是如何得来的：

利用事件的独立性：n 个独立事件同时发生的概率等于各自概率的乘积。

\begin{aligned} \operatorname{P}(S \le i) &= \operatorname{P}(X_1 \le i) \times \dots \times \operatorname{P}(X_n \le i) \\ &= \frac{i}{m} \times \frac{i}{m} \times \dots \times \frac{i}{m} \ (\text{共 } n \text{ 个}) \\ &= \left(\frac{i}{m}\right)^n \end{aligned}

由此我们就可以得到：

B

证明概率为 p 的事件期望 \dfrac{1}{p} 次出现。

设随机变量 x 表示该事件将会在第 x 次出现。套公式我们可以得到：

那么我们就将问题转化为了求 \operatorname{P}(x \ge i)，它表示的是 x 在 i 次及以后发生的概率。那么我们很容易得到 x 在前 i - 1 次均不会出现的概率为 (1 - p)^{i - 1}。因此可以得到：

接着对其等比数列求和即可得到：

这时候就会有人来问啦。倒数第二步是怎么推过来的。

PS. 关于 \sum_{i = 0}^{\infty}(1 - p)^i 是如何推导而来的：

\begin{aligned} \operatorname{E}(X) &= \sum_{i = 1}^{\infty} i \times \left[\operatorname{P}(X \ge i) - \operatorname{P}(X \ge i + 1)\right] \\ &= 1 \times \left[\operatorname{P}(X \ge 1) - \operatorname{P}(X \ge 2)\right] + 2 \times \left[\operatorname{P}(X \ge 2) - \operatorname{P}(X \ge 3)\right] + \dots \\ &= \operatorname{P}(X \ge 1) + \left[2 \times \operatorname{P}(X \ge 2) - 1 \times \operatorname{P}(X \ge 2)\right] + \dots \\ &= \operatorname{P}(X \ge 1) + \operatorname{P}(X \ge 2) + \dots \\ &= \sum_{i = 1}^{\infty} \operatorname{P}(X \ge i) \end{aligned}

这一部分还是一个比较常用的 trick，可以下去自己再手推一遍。

C

C1

箱子里有 n 个球 1, 2, \dots, n，你要从里面拿 m 次球，拿了后放回，求取出的数字之和的期望。

不妨设 x_i 表示第 i 次取出来的值。那么数字之和的期望为：

依据期望的定义得到：

于是我们要求 \operatorname{P}(x = j) 的概率。显然不论 j 取何值，概率都是相等的，为 \dfrac{1}{n}，因此得到：

于是答案即为 \dfrac{(n + 1)m}{2}。

C2

箱子里有 n 个球 1, 2, \dots, n，你要从里面拿 m 次球，拿了后不放回，求取出的数字之和的期望。

我们设随机变量 x_i 表示：

设答案为 S，得到 S = \sum_{i = 1}^{n} x_i，于是我们要求：

展开 \operatorname{E}(x_i) 得到：

显然 \operatorname{P}(x_i = i) 表示 i 被取出的概率，而拿球后不放回，相当于在 n 个球中取 m 个，因此概率为 \dfrac{m}{n}，于是得到：

C3

箱子里有 n 个球 1, 2, \dots, n，你要从里面拿 m 次球，拿了后以 p_1 的概率放回，p_2 的概率放回两个和这个相同的球（相当于增加一个球），求取出的数字之和的期望。

我们仍然设一个随机变量 x_i，它表示 i 被拿出来的次数乘 i，即对答案的贡献。形式化地，我们设 y_i 表示 i 被拿了几次，那么 x_i = y_i \cdot i。假设数字之和为 S，那么：

然后我们考虑求 \operatorname{E}(y_i)。首先我们知道，每一个球是平等的，意味着概率是均等的，意味着它们被拿出来的次数的期望是一样的，即 \operatorname{E}(y_1) = \operatorname{E}(y_2) = \cdots = \operatorname{E}(y_n)。而我们知道，它们被拿出来的次数的和是 m（因为你只拿了 m 个球出来），而 \operatorname{E}(m) = m，即：

因此得到 \operatorname{E}(y_i) = \dfrac{m}{n}，带回上式得到 \operatorname{E}(S) = \dfrac{m(n + 1)}{2}。

D

D1

在一条 n 个点的链上游走，求从一端走到另一端的期望步数。

假设步数是 S，求 S 的期望，我们定义一个随机变量 x_i 表示从 i 出发随机游走，第一次到 i + 1 的步数。

我们手推一下期望的式子，发现：

就可以递推做了，但算出来就会发现 \operatorname{E}(S) = (n - 1)^2。

提示：

对于手推公式这个部分可以先感性理解一下，在初始位置一时向左/右走各有 \dfrac{1}{2} 的概率，所以当初始点位为 1 时，期望为 1，如果初始位置在 2 时，则可能向左走回一，也有可能向右走到 i + 1，以此类推。

D2

在一个 n 个点的完全图上游走，求从一个点走到另一个点的期望步数。

设期望步数为 \operatorname{E}，得到：

提示：

这个式子可以拆成两部分看待，对于左边这一部分，是从当前点直接走向终点的期望，而对于第二部分，则是先走到其他点，由于是完全图，我们不难发现从这个点再要走到终点的期望和起始点的期望是一致的，都为 \operatorname{E}。

解得 \operatorname{E} = n - 1。

D3

对每条边 (u \to v)，记录从 u 走到 v 的期望步数，S_u 表示 u 的儿子数（有根树）。

提示：

这里解释一下这个式子是如何推来的，首先第一部分 |S_u| + 1 表示从该点可以走到的点数，那么这一部分期望就是直接走到目标点的期望，第二部分就是走到除目标点外的其他相邻点的期望，对于每一个走到的相邻点其贡献是走到当前点的代价 (1)，从当前点走回上一个正确点位的期望 \operatorname{E}(v', u)，从上一个正确点位走到目标点的期望 \operatorname{E}(u, v)。

怎么算这个式子？把 v 当作 u 的父节点，那么 v' 一定是 u 的子节点，这就是一个树形 DP，算完到 root 后再从根到子节点算一下向下走的边的期望。

这题本来可以直接用 f[u] 表示从 u 走到 u 的父节点的期望步数来 DP，但上述方法更可拓展（多组询问）。

E

E1

每次随机一个 [1, n] 的整数，问期望几次能凑齐所有数。

设 f[i] 表示凑齐了 i 个数，期望几次凑齐所有数：

提示：

简单解释一下这个式子，当前已经凑齐了 i 个数字，那么就有 \dfrac{i}{n} 的概率凑出一个先前已经出现过的数字，同理就会有 \dfrac{n - i}{n} 的概率凑出一个新数字。

有一个有趣的问题，就是这个问题的答案为什么不是每个数第一次被凑出的时间的和的期望？如果这样算那么 \operatorname{E}(S) = n^2，但事实上凑出的时间相当于次数的前缀和，因此是不对的。

E2

随机一个长度为 n 的排列 p，求 \langle p_j \rangle_{j = 1}^{i} 中 p_i 是最大的数的概率。

由于每个数是均等的，因此它们成为最大值的概率也是一样的，于是答案为 \dfrac{1}{i}。

E3-1

随机一个长度为 n 的排列 p，求 \langle p_j \rangle_{j = 1}^{i} 中 p_i 是最大的数的个数（即前缀最大值的个数）的期望。

设随机变量 x_i：

则可以得到：

扩展：

这里扩展一下最后是如何得到 \dfrac{1}{i} 这个结论的。

\operatorname{P}(x_i = 1) = \dfrac{(i - 1)!}{i!} = \dfrac{1}{i}

因为 i 为前缀最大值，前缀的排列有 i! 种，而固定 i 作为最后一个值，则前面的数的排列有 (i - 1)! 种。

E3-2

随机一个长度为 n 的排列 p，求 \langle p_i \rangle_{j = 1}^{i} 中 p_i 是最大的数的个数（即前缀最大值的个数）的平方的期望。

首先要明确一点，就是平方的期望不等于期望的平方，即 \operatorname{E}(x^2) \neq \operatorname{E}^2(x)，因为 x 是随机变量不是常量。

PS. 这里相信有不少读者会有疑惑，所以详细解释一下。

解释：

引理：Jensen 不等式（凸性）

对于凸函数 f，有 \operatorname{E}[f(X)] \ge f[\operatorname{E}(X)]，当且仅当 X 为常数等号成立。

证明：

从方差的定义我们可以知道：

\operatorname{Var}(X) = \operatorname{E}\left[(X - \operatorname{E}[X])^2\right] \ge 0

展开这个方差公式我们可以得到：

\operatorname{Var}(X) = \operatorname{E}[X^2] - [\operatorname{E}[X]]^2 \ge 0

等号成立时，即 \operatorname{Var}(X) = 0，即 X 为常数。

证毕

于是我们按套路出牌，设随机变量 x_i：

于是我们得到：

PS. 关于这一步转化，利用多项式展开，先将括号内的平方展开，再利用期望的线性性质即可将求和提出括号。

由于 x_i \in \{0, 1\}，因此其实 x_i^2 \Leftrightarrow x_i，于是我们需要求 \operatorname{E}(x_i)，仔细理解一下，其实这就是 p_i = \max \langle p_j \rangle_{j = 1}^{i} 的概率！于是我们得到 \operatorname{E}(x_i) = \dfrac{1}{i}。

接下来考虑 \operatorname{E}(x_i x_j)，在此之前我们思考一下 x_i x_j 的取值，有：

那么一个有趣的问题是 p_i = \max \langle p_k \rangle_{k = 1}^{i} 与 p_j = \max \langle p_k \rangle_{j = 1}^{i} 两个事件是否相关？

答案是，它们不相关！不管它们是在何种情况下同时发生，要么 i < j，要么 i > j，其中一个总是覆盖另一个的范围，即比另一个的所有数都大，因此不会受到另一个的选择的影响，于是我们得到：

综上，我们得到：

E4

随机一个长度为 n 的排列 p，求 i 在 j 的后面的概率。

直观理解 i 和 j 是平等的，因此谁在前面的概率是相等的，答案即为：

E5

设有 n 堆石头，第 i 堆个数为 a_i，每次随机选一个石头然后把那一整堆都扔了，求第 1 堆石头期望第几次被扔。

设随机变量 x_i 表示第 i 堆石头是第几个被拿走的，显然我们有：

于是我们要求 \operatorname{E}(x_1)，根据期望的线性性转化为 \operatorname{E}([x_i < x_1])，由于艾弗森括号表达式是一个布尔表达式，因此这个期望等价于 \operatorname{P}(x_i < x_1)，于是得到：

而根据 E4 我们稍作拓展，其实 \dfrac{a_i}{\sum_{i = 1}^{n} a_i} 表示的就是第 i 堆石子被拿走的概率，因此 \operatorname{P}(x_i < x_1) 表示的就是第 i 堆石子比第 1 堆石子先被拿走的概率，显然为 \dfrac{a_i}{a_i + a_1}，于是得到：

E6

给定一个长度为 n 的 01 串，每个位置是 1 的概率是 p，定义 S 是每段连续的 1 的长度的平方之和，求 S 的期望。

令 x_i 表示 \langle s_j \rangle_{j = 1}^{i} 中所有为 1 的段的长度平方之和，因此 \operatorname{E}(S) = \operatorname{E}(x_n)。再令 y_i 表示 \langle s_j \rangle_{j = 1}^{i} 中最后一段 1 的长度。我们先求 x_i, y_i 的转移式。考虑第 i 位上的值。

于是我们考虑求 \operatorname{E}(x_i), \operatorname{E}(y_i)，于是我们简单地把概率套到上面的转移式就能得到：

E7

给定一棵树，将它的边随机一个顺序后依次插入，求 (u, v) 期望什么时候连通。

那么我们只需要考虑在插入边的序列中 (u, v) 路径上出现时间最晚的边的位置（位置即时间）的期望。

假设 (u, v) 路径长度为 k，总边数是 n - 1，那么枚举最后一条边的位置 i，那么首先我们考虑剩下 k - 1 条边的选法，然后是这 k 条边的顺序，然后是剩下的 n - k - 1 条边的顺序（总共 n - 1 条边），最后除以全排列即可。

E8

给 1, 2, \dots, n 这 n 个数，每次随机选择一个还在的数，删掉它的所有约数，求期望几次删完。

直接做的话，每一次删掉的数的个数不方便统计，不妨换一下思路，我们考虑这个问题：

给 1, 2, \dots, n 这 n 个数，初始时每个数都是白的，每次随机选择一个还在的数，如果它是黑的就删掉它，否则就把它的约数标黑再删掉它，求期望删掉几个白色的数。

仔细思考可以发现，这个问题与原问题是等价的，原因是删除黑色的点不影响白色点被选到的概率，这样转化的好处在于，我们每次只会删掉一个数，于是我们可以定义随机变量 x_i 表示：

（PS. 这里的第 i 个数是指删到第 i 个数时这个数的颜色。）

于是我们要求的是：

根据这个随机变量的定义，\operatorname{E}(x_i) \Leftrightarrow \operatorname{P}(x_i = 1)，于是我们要求 i 被删时是白色的概率，显然如果 i 是白色，那么 i 的所有倍数都没被删，且为白色，我们选到不是 i 的倍数时，对 i 的概率不影响，我们只需要考虑这 \left\lfloor \dfrac{n}{i} \right\rfloor 个数中 i 最先被选中的概率，显然为 \dfrac{1}{\left\lfloor \dfrac{n}{i} \right\rfloor}，于是得到：

期望 DP

期望 DP 主要用于求解期望、概率等题目，转移方程有时候比较灵活。

一般求概率是正推，求期望是逆推，通过题目可以体会到这点。

期望 DP 相较于其他 DP 有一个普遍的规律，那就是在做期望 DP 问题时，你能够明显感受到 DP 在这里面只起到一个工具作用，对于优化时间、优化空间等方面是没有明显作用的，同时期望 DP 的状态转移方程往往就是你通过题目条件推出的期望的一般式。

这里给出几个练习题，仿照背包九讲，这里命名为期望九题：期望九题。

PS. 这里题单中给出题目普遍难度较高，对于初学期望者慎入。

这里仅给出一道例题，让初学期望者感受一下期望出题的做题的基本模式，这里也是引用了一道经典老题。

经典例题

P4316 绿豆蛙的归宿

题目链接：P4316 绿豆蛙的归宿。

题目大意

给出一个 \operatorname{DAG}（有向无环图），对于每一个点，若它有 k 条出边，那么走每一条出边的概率是均等的，均为 \dfrac{1}{k}，求从起点到终点的路径长度期望。

做法分析

很典型的一个图上期望题，做法很自然，利用我们上面所讲到的期望的线性性质，可以发现总的路径期望，就是走过的每一条路径的期望距离和。

那么我们就自然而然地得出了一个状态 f[i] 表示从起点到 i 号点的期望距离，同时还可以得到 f[n] = 0。

对于有向无环图的处理，就用拓扑排序就好。

AC Code

PS. 多年前的代码，码风很差，请见谅。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
int e[M], ne[M], h[N], w[M], idx = 0;
int n, m, deg[N], dout[N];
double dist[N];
inline void add (int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
    deg[b] ++, dout[b] ++;
}
inline void topsort() {
    queue<int> q;
    q.push(n);
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            dist[j] += (dist[u] + w[i]) / deg[j];
            if (--dout[j] == 0) q.push(j);
        }
    }
}
int main() {
    memset(h, -1,sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        add (b, a, c);
    }
    topsort();
    printf("%.2lf", dist[1]);
}

复杂度分析

• 时间复杂度：拓扑排序为 O(n + m)，单次转移为 O(1)，总体为 O(n + m)。
• 空间复杂度：O(n + m)。

有后效性的 DP

从开始学习动态规划的时候，所有人应该都听过这三个词语状态、阶段、决策，这是构成动态规划的三要素，那么大多数有人应该也听过三个与之相关的词“子问题重叠性”、“无后效性”、“最优子结构性质”，这是能够完成动态规划所必须满足的三个性质。

那么如果不满足怎么办呢？这里着重介绍有后效性的动态规划。

何为有无后效性？

举个例子。

对于这张图片中是一个很经典的动态规划问题，题目是这样的：

从起始点 (1, 1) 开始每次只能向右/下走一格，不能重复走，求走到右下角的期望。

那么在这个问题中，假如我们已经走到了 (2, 3) 这个黑色点，我们只需要考虑如何从这个点走到终点即可，因为只能向下/右走同时又不能往回走，所以我们就不在乎过去是怎样走到当前这个点的，也就是过去对未来决策不会产生影响，这就是无后效性。

现在如果我稍微改动一下题面：

从起始点 (1, 1) 开始每次只能向上/下/左/右走一格，不能重复走，求走到右下角的期望。

我在这里扩展了能够走到的方向，这就导致了我站在当前这个点不能只考虑怎么走到终点，我还要考虑我接下来要走的点之前有没有走过，能不能走，这里就体现了过去的决策对未来产生了影响，这就是有后效性。

如何解决

以这个问题为例，我们可以很显然地发现，相邻两行之间的决策是无后效性的，而同一行内的决策是有后效性的。

这样说可能比较抽象，这里换一种比较形式化的说法。

一直走相邻两行

那么只有当我走完前 i 行后才能走到第 i + 1 行，并且 i + 1 行之后的所有都没有遍历，我们只能依赖前 i 行的信息更新当前状态，并且我们并不在乎是如何走到当前位置的，这有没有感觉有点像上面的第一个题目，这里就是无后效性的。

同一行而来

如果是从同一行转移过来，那么前面几行很有可能是走不满的，并且下面几行是可能走过的，我们不能确定可以向哪里走，这样前面的决策就影响到了当前的决策，这就是有后效性的。

现在已经确定了哪一种有后效性，哪一种没有，这样就可以分类处理了。

• 对于相邻行之间没有后效性，可以直接正常 DP 转移。
• 对于同一行之间的未知决策看作一个未知数，利用高斯消元直接解出来即可。

参考文献

• 期望经典问题入门：期望经典问题入门（本文对于原文的省略部分进行增加、批注与证明）。
• 有效性与无效性理解：有效性与无效性理解。

如有表述不当或是逻辑错误，欢迎批评指正。

全文完。