数学期望在算法中的应用

Macw07

2024-12-02 11:05:35

发布于：加拿大

74阅读

0回复

0点赞

数学期望在算法中的应用

数学期望是概率论和统计学中的一个核心概念，主要用于描述所有数据的平均值或者是中心趋势。在计算机算法竞赛中，期望算法属于一个中高等难度的算法，在程序设计中发挥着至关重要的作用。在近些年的 CSP/ USACO 等国际知名算法竞赛中，期望和期望动态规划等算法常常被作为考试题目。因此，本文将详细讲述数学期望在算法中的应用。

为了降低本文的阅读门槛，本文会提供诸多例子来帮助读者来理解期望的定义和期望的实际应用。在文章的最后，我也会向大家提供相关的算法练习题。

随机变量的基本概念

在了解期望之前，务必要了解一下 随机变量 Random Variable 的定义。

随机变量是一个函数，它将随机实验的每一个可能结果映射到一个数值。随机变量可以看作是随机现象的数学表达。

E.g. 1 投掷硬币

以投掷一枚硬币举例子：

有两个实验结果：正面 ( $\mathtt{H}$ )、反面 ( $\mathtt{T}$ )。
随机变量 $X$ ：定义为正面记作 $1$ ，反面记作 $0$ 。

E.g. 2 投掷骰子

在投掷骰子时：

有六个实验结果： $1, 2, 3, 4, 5, 6$ 。
随机变量 $Y$ ：定义为投掷出的点数的值。

数学期望的基本概念

教科书上对于 期望 Expectation 的定义如下：

数学期望，简称期望，是对随机变量取值的加权平均，其权重为对应取值的概率。

一个更直观的说法是：期望值代表了大量重复实验中，随机变量取值的平均水平，是对随机现象的一种 集中趋势 的描述。

E.g. 3 考试评分

假设一门考试有五道选择题，得分规则如下：

选择正确答案获得 $4$ 分。
选择错误答案扣除 $1$ 分。
未作答不增加也不扣除分数。

如果考生随机选择答案，每道题的概率为：

做对这道题的概率为： $\dfrac{1}{4}$ 。
做错这道题的概率为： $\dfrac{3}{4}$ 。

那么这场考试每道题的期望得分为：

$E(X) = 4\times \dfrac{1}{4} + (-1) \times \dfrac{3}{4} = 1- 0.75 = 0.25$

这意味着，随机作答的长期平均得分是每道题 $0.25$ 分。

E.g. 4 概率游戏 $\mathrm{I}$

有一个掷骰子的游戏，规则是如果投掷出点数 $6$ 得 $10$ 分，投掷出其余点数扣 $2$ 分。那么：

投掷出 $6$ 的概率是： $\dfrac{1}{6}$ 。
投掷出其他点数的概率是： $\dfrac{5}{6}$ 。

期望得分为：

$E(X) = 10\times\dfrac{1}{6} + (-2)\times \dfrac{5}{6} = \dfrac{10}{6} - \dfrac{10}{6} = 0$

因此从长远来看（假如一直玩这个游戏的话），这个游戏是公平的，没有任何的得分优势。

通过这两个例子应该就能够很容易地理解期望在数学中的定义和作用了。

期望的线性叠加和独立性

期望是可以叠加的，假设有两个事件（两个事件可以是相互独立的，也可以是相互依赖的），两个事件的期望分别为 $E(\Alpha)$ 和 $E(\Beta)$ ，那么这两个事件的整体期望 $E(\Alpha + \Beta)$ 可以直接被拆解成 $E(\Alpha) + E(\Beta)$ 。

这说明 期望的计算可以逐项分解并加权，无论这些随机变量是否独立。

E.g. 5 概率游戏 $\mathrm{II}$

有一个概率游戏，分为两轮：

第一轮：玩家投掷一个六面骰子，得分为骰子的点数。
第二轮：玩家掷两个六面骰子，得分为两个点数之和。

目标：要求计算玩家的总期望得分。

对于这种题目，我们就可以利用期望的线性叠加来完成。以下是一些变量的定义：

第一轮得分：随机变量 $X_1$ ，取值为 $1, 2, 3, 4, 5, 6$ 。
第二轮得分：随机变量 $X_2$ ，为两个骰子的点数之和，取值为 $2, 3, \cdots, 11, 12$ 。
总得分的随机变量 $S = X_1 + X_2$ 。

根据期望的线性叠加性质：

$E(S) = E(X_1) + E(X_2)$

我们可以分别计算两个随机变量的期望，并将结果相加就可以计算出整一个概率游戏的期望得分了。

经过计算（本文不再详细举例相同的期望得分计算过程，具体可以自己手动推导），两轮游戏的期望得分分别为：

第一轮： $E(X_1) = \dfrac{21}{6} = 3.5$ 。
第二轮： $E(X_2) = \dfrac{252}{36} = 7$ 。

那么总期望得分就是：

$E(S) = E(X_1) + E(X_2) = 3.5 + 7 = 10.5$

也就是说，如果玩家无限地玩这个游戏，平均下来每一轮的得分大约为 $10.5$ 。

期望的基本算法题

期望在计算机的应用也非常的广泛，这里提供几个实际的算法题目来帮助读者加深对期望的理解。

E.g. 6 随机交换序列

题目描述

给定一个长度为 $n$ 的序列，每个元素为 $a_1, a_2, \cdots, a_{-1}, a_{n}$ 。每一步操作为选择两个不同位置的 $i$ 和 $j$ ，满足 $1 \le i, j\le n, i \neq j$ ，并交换 $a_i$ 和 $a_j$ 的值。假设进行无限次随机交换操作后，求每一个位置上的最终数字的期望值。

解题思路

在进行了无限次随机交换次数后，序列将趋于均匀的随机排列。由于所有的排列的概率都是相同的，那么每个位置上的元素的期望值应为序列的平均值。

数学证明

设序列的总和为 $S = \Sigma_{i=1}^{n}a_i$ ，平均值为 $\mu = \dfrac{S}{n}$ 。在进行无限次随机交换后，每个位置上的元素均可能是任意一个 $a_i$ ，因此期望值均为 $\mu$ 。

C++ 代码实现

本题的 C++ 代码实现如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    int n; cin >> n;
    vector<long long> a(n);
    double sum = 0.0;
    for(auto &x: a){
        cin >> x;
        sum += x;
    }
    double average = sum / n;
    // 输出每个位置的期望值
    for(int i=0;i<n;i++){
        printf("%.6lf ", average);
    }
    return 0;
}

E.g. 7 彩票中奖期望

题目描述

你正参加一个彩票游戏，每张彩票有两个号码，分别是红球和篮球。红球的号码范围从 $1$ 到 $R$ 中选择，篮球的号码从 $1$ 到 $B$ 中选择。每张彩票的中奖条件是红球和篮球都正确。已知你购买了 $k$ 张不同的彩票，求中奖的期望次数。

解题思路

首先先求出每张彩票的中奖概率为 $\dfrac{1}{R} \times \dfrac{1}{B} = \dfrac{1}{RB}$ 。购买 $k$ 张独立的彩票，每张彩票的中奖次数都是独立的，因此总的中奖次数的期望就是 $k \times \dfrac{1}{RB}$ 。

C++ 代码实现

本题的 C++ 代码实现如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    long long R, B, k;
    cin >> R >> B >> k;
    double E = (double)k / (R * B);
    printf("%.6lf\n", E);
    return 0;
}

E.g. 8 期望步数达到目标

题目描述

在一个二维平面网格上，从起点 $(0, 0)$ 开始，目标是到达终点 $(n, m)$ 。每一步，你可以选择向右或者向上移动。向右移动的概率为 $p$ ，向上移动的概率为 $1 - p$ 。求从起点到达终点的期望步数。

解题思路

相比较前面几道题目，这道题的难度有所提升。这是一个典型的动态规划与期望相结合的问题。我们设置 $dp_{i, j}$ 表示从点 $(i, j)$ 到达终点的期望步数。

状态转移方程：

如果当前坐标是终点，即 $i = n$ 且 $j = m$ 时，则 $dp_{i, j} = 0$ ，表示期望走 $0$ 步就可以到达终点。
如果在边界移动（即 $i = n$ $i = n$ 或 $j = m$ $j = m$ 时），只能单向移动：
- $dp_{i, j} = 1 + dp_{i, j+1}$ （向右移动）
- $dp_{i, j} = 1 + dp_{i+1, j}$ （向上移动）
其他情况：
- $dp_{i, j} = 1 + p \times dp_{i, j+1} + (1 - p) \times dp_{i+1, j}$

计算顺序：从终点开始，逆序填充 $dp$ 表格。

C++ 代码实现

本题的 C++ 代码实现如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;

int main(){
    int n, m; double p;
    int dp[505][505];
    cin >> n >> m >> p;
    for(int i=n; i>=0; i--){
        for(int j=m; j>=0; j--){
            if(i == n && j == m){
                dp[i][j] = 0.0;
                continue;
            }
            if(i == n) dp[i][j] = 1.0 + dp[i][j+1];
            else if(j == m) dp[i][j] = 1.0 + dp[i+1][j];
            else dp[i][j] = 1.0 + p * dp[i][j+1] +
                (1.0 - p) * dp[i+1][j];
        }
    }
    printf("%.6lf\n", dp[0][0]);
    return 0;
}

E.g. 9 P1365 WJMZBMR打osu! / Easy

解题思路

这也是一道经典的期望动态规划的例题，与前面的题目都相同，我们先定义 $dp_i$ 表示以第 $i$ 个字符结尾的期望得分，用变量 $\mathtt{len}$ 来表示连续的 o 字符出现的个数（且需要包含 $str_i$ 的回合）。根据字符串的三种字符分类进行讨论：

当当前字符为 x 的时候：

说明本回合游戏失败，期望得分将不会增加，也不会减少（与 $dp_{i-1}$ 相同）。与此同时，需要将 $\mathtt{len}$ 归零，表示截至目前不存在连续的 o。
当当前的字符为 o 的时候：

说明本回合游戏胜利，期望得分应该就是截止上一轮游戏的期望得分 $dp_{i-1}$ 加上这轮游戏的期望得分 $(\mathtt{len} + 1)^2 - \mathtt{len}^2$ （撤销长度为 $\mathtt{len}$ 的连击得分，增加长度为 $\mathtt{len} + 1$ 的期望得分。化简可得： $dp_i = dp_{i-1} + 2\times \mathtt{len} + 1$ 。同时在更新完 $dp$ 数组后将 $\mathtt{len}$ 设置为 $\mathtt{len} + 1$ 。
当当前字符为 ? 的时候：

我们需要同时考虑胜利或者失败两种情况（(成功的期望 + 失败的期望) / 2）：

$dp_i = dp_{i-1} + \dfrac{((\mathtt{len} + 1)^2 - \mathtt{len}^2) + 0}{2} = dp_{i-1} + \mathtt{len} + 0.5$

与此同时需要把 $\mathtt{len}$ 更新为 $\dfrac{(\mathtt{len} + 1) + 0}{2} = \dfrac{\mathtt{len} + 1}{2}$ 。

接下来直接遍历就好了。

C++ 代码实现

本题的 C++ 代码实现如下：

#include <iostream>
#include <algorithm>
using namespace std;

constexpr int N = 3e5 + 5;
int n; char c;
long double len, dp[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> c;
        switch (c){
            case '?': 
                dp[i] = dp[i-1] + len + 0.5;
                len = (len + 1) / 2; break;
            case 'o': 
                dp[i] = dp[i-1] - len * len + (len + 1) * (len + 1); 
                len++; break;
            case 'x': dp[i] = dp[i-1]; len = 0; break;
        }
    }
    printf("%.4Lf\n", dp[n]);
    return 0;
}

该算法的时间复杂度为 $O(n)$ ，空间复杂度也是 $O(n)$ ，但考虑到每一个 $dp_i$ 永远只依赖自己上一个状态（ $dp_{i-1}$ ），因此可以进一步把代码的空间复杂度降低到 $O(1)$ 。

E.g. 10 P1850 [NOIP2016 提高组] 换教室

这道题是 NOIP 2016 年比赛的原题，可以看出期望动态规划确实是一项重点。

解题思路

相同地，我们在一开始也需要定义 $dp$ 状态。定义 $dp_{i, j, k}$ 表示走到了第 $i$ 点，申请了 $j$ 次换课，当前次 $\mathtt{换/不换}(1/0)$ 的期望。代码用 $map_{a, b}$ 来表示地图中 $a$ 和 $b$ 两点的最短路（由于数据范围和需要求解多源最短路径的需求，这里使用 Floyd 算法来计算最短路径）。

状态转移：

未换课 ( $dp_{i, j, 0}$ )：
- 情况 1：上一步也未换课：
  
  $dp_{i, j, 0} = dp_{i-1, j, 0} + \text{map}[c[i-1]][c[i]]$
- 情况 2：上一步换课：
  
  $dp_{i, j, 0} = dp_{i-1, j, 1} + \text{map}[c[i-1]][c[i]] \cdot (1 - k[i-1]) + \text{map}[d[i-1]][c[i]] \cdot k[i-1]$
换课 ( $dp_{i, j, 1}$ )：
- 情况 1：上一步未换课：
  
  $dp_{i, j, 1} = dp_{i-1, j-1, 0} + \text{map}[c[i-1]][d[i]] \cdot k[i] + \text{map}[c[i-1]][c[i]] \cdot (1 - k[i])$
- 情况 2：上一步换课：
  
  $dp_{i, j, 1} = dp_{i-1, j-1, 1} + \\ \text{map}[d[i-1]][d[i]] \cdot k[i-1] \cdot k[i] + \\ \text{map}[d[i-1]][c[i]] \cdot k[i-1] \cdot (1 - k[i]) + \\ \text{map}[c[i-1]][d[i]] \cdot (1 - k[i-1]) \cdot k[i] + \\ \text{map}[c[i-1]][c[i]] \cdot (1 - k[i-1]) \cdot (1 - k[i])$

C++ 代码实现

本题的 C++ 代码实现如下：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

constexpr int N = 2005;
constexpr int V = 305, E = 90000;
int n, m, v, e;
int c[N], d[N];
double k[N];
long long map[V][V];
// dp[i][j][k] 表示走到第 i 个点，申请了 j 次，
// 当前次 申请/不申请 (k) 的期望。
double dp[N][N][2];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> v >> e;
    for (int i=1; i<=n; i++) cin >> c[i];
    for (int i=1; i<=n; i++) cin >> d[i];
    for (int i=1; i<=n; i++) cin >> k[i];
    for (int i=1; i<=v; i++){
        for (int j=1; j<=v; j++){
            map[i][j] = 0x7f7f7f7f;
        }
        map[i][i] = map[i][0] = map[0][i] = 0;
    }
    for (int i=1; i<=e; i++){
        int a, b, w;
        cin >> a >> b >> w;
        map[a][b] = map[b][a] = min(map[a][b], 1LL * w);
    }
    for (int k=1; k<=v; k++){
        for (int i=1; i<=v; i++){
            for (int j=1; j<=v; j++){
                map[i][j] = min(map[i][k] + map[k][j], map[i][j]);
            }
        }
    }
    for (int i=0; i<=n; i++){
        for (int j=0; j<=m; j++){
            dp[i][j][0] = dp[i][j][1] = 1e9;
        }
    }
    dp[1][0][0] = dp[1][1][1] = 0;
    for (int i=2; i<=n; i++){
        dp[i][0][0] = dp[i-1][0][0] + map[c[i-1]][c[i]];
        for (int j=1; j<=min(i, m); j++){
            int C1 = c[i-1], C2 = d[i-1], C3 = c[i], C4 = d[i];
            dp[i][j][0] = min(dp[i][j][0], min(dp[i-1][j][0] + map[C1][C3], 
                dp[i-1][j][1] + map[C1][C3] * (1 - k[i-1]) + map[C2][C3] * k[i-1]));
            dp[i][j][1] = min(dp[i][j][1], 
                min(dp[i-1][j-1][0] + map[C1][C3] * (1 - k[i]) + map[C1][C4] * k[i],
                dp[i-1][j-1][1] + map[C2][C4] * k[i] * k[i-1] + 
                map[C2][C3] * k[i-1] * (1 - k[i]) +
                map[C1][C4] * (1 - k[i-1]) * k[i] + 
                map[C1][C3] * (1 - k[i-1]) * (1 - k[i])));
        }
    }
    double ans = 1e9;
    for (int i=0; i<=m; i++){
        ans = min(ans, dp[n][i][0]);
        ans = min(ans, dp[n][i][1]);
    }
    printf("%.2lf", ans);
    return 0;
}

E.g. 11 P1654 OSU!

与【E.g. 9 [P1365 WJMZBMR打osu! / Easy]】类似，稍作修改即可。

解题思路

要求解 $x^3$ 的期望，那么肯定需要维护 $x^2$ 和 $x$ 的期望才可以。

具体地：

$a[i]$ 表示以第 $i$ 个位置为终点， $x$ 的期望。
$b[i]$ 表示以第 $i$ 个位置为终点， $x^2$ 的期望。
$dp[i]$ 表示以第 $i$ 个位置为终点， $x^3$ 的期望。

递推公式：

$a[i] = (a[i-1] + 1) * p[i]$ $a [i] = (a [i - 1] + 1) * p [i]$
- $a[i-1]$ 是上一轮的 $x$ 的期望，加上当前位置的贡献 $1 \cdot p[i]$ 。
$b[i] = (b[i-1] + 2 \cdot a[i-1] + 1) \cdot p[i]$ $b [i] = (b [i - 1] + 2 \cdot a [i - 1] + 1) \cdot p [i]$
- 上一轮的 $x^2$ 的期望加上新的贡献，其中包含 $2 \cdot a[i-1] \cdot 1$ 和 $1^2$ 。
$dp[i] = dp[i-1] + (3 \cdot (a[i-1] + b[i-1]) + 1) \cdot p[i]$ $d p [i] = d p [i - 1] + (3 \cdot (a [i - 1] + b [i - 1]) + 1) \cdot p [i]$
- 最后将所有 $x^3$ 的期望累加到当前 $dp$ 状态。

C++ 代码实现

本题的 C++ 代码实现如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

constexpr int N = 3e5 + 5;
int n;
long double p[N], dp[N], a[N], b[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i=1; i<=n; i++) cin >> p[i];
    for (int i=1; i<=n; i++){
        a[i] = (a[i-1] + 1) * p[i];
        b[i] = (b[i-1] + 2 * a[i-1] + 1) * p[i];
        dp[i] = dp[i-1] + (3 * (a[i-1] + b[i-1]) + 1) * p[i];
    }
    printf("%.1Lf\n", dp[n]);
    return 0;
}