0x38 概率与数学期望

在概率论中，我们把一个随机实验的某种可能结果称为“样本点”，把所有可能结果构成的集合称为“样本空间”。在一个给定的样本空间中，随机事件就是样本空间的子集，即由若干个样本点构成的集合，随机变量就是把样本点映射为实数的函数。随机变量分为离散型与连续型两种，我们主要讨论离散型随机变量，也就是取值有限或可数的随机变量。

定义

设样本空间为 $\Omega$ ，若对于 $\Omega$ 中的每一个随机事件 $A$ ，都存在实值函数 $P(A)$ ，满足：

1. $P(A)\geq 0$

2. $P(\Omega) = 1$

3. 对于若干个两两互斥事件 $A_{1}, A_{2}, \cdots$ 有 $\sum P(A_{i}) = P(\bigcup A_{i})$ ，其中 $\cup$ 表示并集。

则称 $P(A)$ 为随机事件 $A$ 发生的概率。通俗地讲，概率是对随机事件发生可能性的度量，是一个 $0 \sim 1$ 之间的实数。

定义

若随机变量 $X$ 的取值有 $x_{1}, x_{2}, \cdots$ ，一个随机事件可表示为 $X = X_{i}$ ，其概率为 $P(X = X_{i}) = p_{i}$ ，则称 $E(X) = \sum p_{i} x_{i}$ 为随机变量 $X$ 的数学期望。通俗地讲，数学期望是随机变量取值与概率的乘积之和。

例如在掷两枚骰子的点数实验中，样本空间是由36个样本点构成的集合，每个样本点可写作 $(a, b)$ ，其中 $1 \leq a, b \leq 6$ 。随机变量有多种，不妨以“掷出的点数之和 $X$ ”为例，则随机变量 $X$ 的取值为 $2 \sim 12$ 。随机事件可描述为“掷出 $X$ 点”，即由 $a + b = X$ 的样本点 $(a, b)$ 构成的子集。掷出8点的概率 $P(X = 8) = 5 / 36$ 。掷出的点数的数学期望为：

对于条件概率、方差以及各种常见的离散型随机变量的分布，读者在高中数学课本中应该已经学到，这里就不再赘述。

性质

数学期望是线性函数，满足 $E(aX + bY) = a * E(X) + b * E(Y)$ 。

该性质非常重要，是我们能够对数学期望进行递推求解的基本依据，请务必牢记。有了这条性质，在上面的例子中计算“掷两枚骰子的点数”的数学期望会非常容易。设

随机变量 $X$ 表示掷一枚骰子的点数，显然期望值 $E(X) = (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3.5$ 。掷两枚骰子的点数可表示为随机变量 $2X$ ，于是 $E(2X) = 2E(X) = 2*3.5 = 7$ 。

【例题】Rainbow的信号 TYVJ2020

Freda发明了传呼机之后，Rainbow进一步改进了传呼机发送信息所使用的信号。因为现在是数字信息时代，Rainbow发明的信号可以用 $N$ 个自然数 $A_{1}, A_{2}, \dots, A_{N}$ 表示。为了避免两个人的对话被大坏蛋VariantF偷听，Rainbow把对话分成 $A$ 、 $B$ 、 $C$ 三部分，分别用 $a$ 、 $b$ 、 $c$ 三个密码加密。现在Freda接到了Rainbow的信息，她的首要工作就是解密。Freda了解到，这三部分的密码计算方式如下：

在 $1 \sim N$ 这 $N$ 个数中，等概率地选取两个数 $l, r$ ，如果 $l > r$ ，则交换 $l, r$ 。把信号中的第 $l$ 个数到第 $r$ 个数取出来，构成一个数列 $P$ 。

$A$ 部分对话的密码是数列 $P$ 的 $\mathrm{XOR}$ 和的数学期望值。 $\mathrm{XOR}$ 和就是数列 $P$ 中所有数异或起来得到的数。

$B$ 部分对话的密码是数列 $P$ 的 and 和的期望，and 和的定义类似于 xor 和。

$C$ 部分对话的密码是数列 $P$ 的 or 和的期望，or 和的定义类似于 xor 和。

请你帮 Freda 计算这三个密码。

$1 \leq N \leq 10^{5}$ , $N$ 个自然数均不超过 $10^{9}$ 。

位运算是不进位的，各位之间互不影响。因此，我们可以把 $N$ 个自然数 $A_{1}, A_{2}, \dots, A_{N}$ 都分成31位，对每一位分别进行处理。设 $B$ 是一个01序列， $B_{i}$ 等于 $A_{i}$ 的第 $k$ 位。

按照题目中 $l, r$ 的选取方式，长度为 1 的区间（即 $l = r$ 时）被选出的概率为 $1 / N^2$ ，其他区间被选出的概率为 $2 / N^2$ 。我们先 $O(N)$ 检查序列 $B$ 中的每个数是否为 1，若是，则累加 $2^k * 1 / N^2$ 到答案中。于是，接下来我们只需统计 and 和、or 和或 xor 和为 1，并且长度 $\geq 2$ 的区间个数，即可进一步得到数学期望。

依次枚举右端点 $r$ ，设last[k] $(k = 0,1)$ 表示数字 $k$ 上一次出现的位置。

对于 and 和，当 $B[r] = 1$ 并且 $l \in [last[0] + 1, r - 1]$ 时， $B[l \sim r]$ 的 and 和为 1，否则为 0。所以，若 $B[r] = 1$ ，则可以累加 $2^k * ((r - 1) - (last[0] - 1) + 1) * 2 / N^2$ 到答案中。

对于 or 和，当 $B[r] = 1$ 时， $l$ 取任何值， $B[l \sim r]$ 的 or 和都是 1，此时可累加 $2^k * (r - 1) * 2 / N^2$ 到答案中。当 $B[r] = 0$ 时，若 $l \in [1, last[1]]$ ，则 $B[l \sim r]$ 的 or 和为 1，否则为 0。所以，若 $B[r] = 0$ ，则可以累加 $2^k * last[1] * 2 / N^2$ 到答案中。

对于 $\mathrm{xor}$ 和，试想，我们枚举 $l$ 并向左扫描，则遇到数字0时 $B[l \sim r]$ 的 $\mathrm{xor}$ 和不变，遇到数字1时 $B[l \sim r]$ 的 $\mathrm{xor}$ 和取反。如果我们以所有的数字1为分界，把序列 $B$ 分成几段，那么同一段中的位置作为 $l$ 时， $B[l \sim r]$ 的 $\mathrm{xor}$ 和也相等。来自相邻两段的两个位置分别作为 $l$ 时， $B[l \sim r]$ 的 $\mathrm{xor}$ 和恰好相反。

如下图所示，当 $l$ 取灰色位置时， $B[l \sim r]$ 的 $\mathrm{xor}$ 和为 1。当 $l$ 取白色位置时， $B[l \sim r]$ 的 $\mathrm{xor}$ 和为 0。

我们建立两个变量 $c_{1}, c_{2}$ , $c_{1}$ 记录从 $r - 1$ 倒着往前数, 第 $1,3,5,\dots$ 段的总长度 (图中白色部分的总长度), $c_{2}$ 记录第 $2,4,6,\dots$ 段的总长度 (图中灰色部分的总长度)。当 $B[r] = 0$ 时, $c_{2}$ 就是使得 $B[l \sim r]$ 的 $\mathrm{xor}$ 和为 1 的 $l$ 的数量, 可把 $2^{k} * c_{2} * 2 / N^{2}$ 累加到答案中。当 $B[r] = 1$ 时, $c_{1}$ 就是使得 $B[l \sim r]$ 的 $\mathrm{xor}$ 和为 1 的 $l$ 的数量, 可把 $2^{k} * c_{1} * 2 / N^{2}$ 累加到答案中。

在右端点 $r$ 增长为 $r + 1$ 时，令 $c_{1} = c_{1} + 1$ 。若 $B[r] = 1$ ，则还需交换 $c_{1}, c_{2}$ 。

整个算法的时间复杂度为 O(N \log \text{MAX_INT}) ，实现细节请参阅配套光盘中的程序。

【例题】绿豆蛙的归宿 TYVJ1933

给出一个有向无环图，起点为1，终点为 $N$ ，图中每条边都有一个长度。另外，数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。

一只绿豆蛙从起点出发，走向终点。到达每一个顶点时，若有 $K$ 条离开该点的道路，它会等概率地选择任意一条道路离开该点，即走向每条路的概率都是 $1 / K$ 。求它从起点走到终点所经过的路径的期望长度是多少。

$1 \leq N \leq 10^{5}, 1 \leq M \leq 2N$ 。四舍五入保留两位小数输出。

设 $F[x]$ 表示从节点 $x$ 走到终点所经过的路径的期望长度。若从 $x$ 出发有 $k$ 条边，分别到达 $y_{1}, y_{2}, \dots, y_{k}$ ，边长分别为 $z_{1}, z_{2}, \dots, z_{k}$ ，则根据数学期望的定义和性质，有：

显然 $F[N] = 0$ ，我们的目标是求出 $F[1]$ 。故我们从终点出发，在反图上（每条边方向取反的图上）执行拓扑排序，在拓扑排序的过程中顺便计算 $F[x]$ 即可。

整个算法的时间复杂度为 $O(N + M)$ 。

int ver[200002], edge[200002], next[200002], head[100002];  
int out[100002], deg[100002];  
int n, m, tot;  
double dis[100002];  
queue<int> q;

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, next[tot] = head[x], head[x] = tot;
}  
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(y, x, z); // 建反图
        deg[x]++;
        out[x]++;
    }
    q.push(n);
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = next[i]) {
            int y = ver[i];
            dis[y] += (dis[x] + edge[i]) / deg[y];
            out[y]--;
            if (out[y] == 0) q.push(y);
        }
    }
    printf("%.2f\n", dis[1]);
}

【例题】扑克牌 TYVJ2002

Zhq生日那天，Rainbow来找Zhq玩扑克牌。玩着玩着Rainbow觉得太没意思了，于是决定给Zhq一个考验。

Rainbow 把一副扑克牌（54 张）随机洗匀，倒扣着放成一摞。然后 Zhq 从上往下依次翻开每张牌，每翻开一张黑桃、红桃、梅花或者方块，就把它放到对应花色的堆里去。

Rainbow 想问问 Zhq, 得到 $A$ 张黑桃、 $B$ 张红桃、 $C$ 张梅花、 $D$ 张方块需要翻开的牌的张数的期望值 $E$ 是多少。

特殊地, 如果翻开的牌是大王或者小王, 那么 Zhq 可以把它作为某种花色的牌放入对应堆中。Zhq 会采用最优选择, 使得放入之后 $E$ 的值尽可能小。

因为Zhq和Rainbow还在玩扑克，所以这个程序就交给你来写了。

$0 \leq A, B, C, D \leq 15$ 。四舍五入保留三位小数输出。

本题是一道数学期望与动态规划结合的题目，可采用记忆化搜索来实现。对动态规划不熟悉的读者可在学习第0x50章“动态规划”的前三节后再尝试求解本题。

设 $F[a, b, c, d, x, y]$ 表示当前已经翻开了 $a$ 张黑桃、 $b$ 张红桃、 $c$ 张梅花、 $d$ 张方块，并且小王状态为 $x$ ，大王状态为 $y$ 时的期望值。具体来说， $x = 4$ 表示没有用过小王， $x = 0 \sim 3$ 表示用过小王，且把小王作为相应的花色（0代表黑桃，1代表红桃，2代表梅花，3代表方块）。大王的记录方法同理。

当前已经翻开的牌总数 $sum = (a + b + c + d + (x == 4) + (y == 4))$ 。到目前为止，还剩下 $54 - sum$ 张牌，其中有 $13 - a$ 张黑桃。故翻开一张黑桃的概率为 $(13 - a) / (54 - sum)$ 。翻开这张黑桃后，还需要翻开的牌的期望张数为 $F[a + 1, b, c, d, x, y]$ 。对于红桃、梅花、方块，情况类似。

特别地，当 $x = 4$ 时，有 $1 / (54 - sum)$ 的概率翻开小王。根据题意，应选择把小王看作某种花色，使期望值尽量小，即 $\min_{0\leq x'\leq 3}\{F[a,b,c,d,x',y]\}$ 。对于大王，情况类似。

综上所述，有： $F[a,b,c,d,x,y] =$

初值（边界）：若已经翻开的牌数达到了题目要求的数量，则期望值为0。例如已经翻开的黑桃张数为 $a + (x == 0) + (y == 0)$ ，其余同理。

目标： $F[0,0,0,0,4,4] = ?$

值得一提的是，在数学期望递推、数学期望动态规划中，我们通常把终止状态（翻开的牌数达到要求）作为初值，把起始状态（尚未翻开任何牌）作为目标，倒着进行计算。这是因为在很多情况下，起始状态是唯一的（0,0,0,0,4,4），而终止状态很多（只要各花色翻开的牌数都足够即可）。根据数学期望的定义，若我们正着计算，则还需求出从起始状态到达每个终止状态的概率，与 $F$ 值相乘求和才能得到答案，增加了难度，也容易出错。而如果倒着计算，因为起始状态 0,0,0,0,4,4 唯一，所以它的概率一定是 1，直接输出 $F[0,0,0,0,4,4]$ 即为所求。