01.Probability-DP.md

1. 概率 DP 简介

概率 DP：一类使用动态规划方法来求解概率与期望的问题，也可以分别叫做「概率 DP」、「期望 DP」。由于概率和期望具有线性性质，使得可以在概率和期望之间建立一定的递推关系，从而通过动态规划的方式来解决一些概率问题。

概率 DP 和期望 DP 的难点主要有两点：

1. 状态转移方程的推导。
2. 概率论知识。

其中第 $1$ 点和一般动态规划并无太大差别，而第 $2$ 点涉及到对概率论基础知识的掌握。其中，「概率 PD」对应了概率论知识中的「全概率公式」，「期望 DP」则对应了「全期望公式」。

我们来看看「概率 DP」「期望 DP」中所涉及到的概率论基础知识。

2. 概率论知识

2.1 样本空间、事件和概率

基本事件：在概率论中，我们将一次随机实验中的某个可能结果称为「样本点」或者「基本事件」。

样本空间：所有可能的结果组成的集合，称为「样本空间」，标记为 $S$。

随机事件：样本空间 $S$ 的一个子集 $A$（$A \subseteq S$），称为「随机事件」。

概率：对于样本空间 $S$ 中的每一个随机事件 $A$，如果都存在一种时间到实数的映射函数 $P(A)$，满足：

1. $P(S)=1$。
2. $0\le P(A)\le 1$。
3. 对于两个互斥事件，$P(A \cup B) = P(A) + P(B)$。

则称 $P(A)$ 为随机事件 $A$ 的概率。

2.2 随机变量、数学期望

随机变量：对于样本空间 $S$ 中的任意事件 $i$，都有唯一的实数 $X_i$ 与之对应，则称 $X=X_i$ 为样本空间 $S$ 上的随机变量。

常见的随机变量主要有「离散型随机变量」与「连续型随机变量」。「概率 DP」主要涉及到离散型随机变量。

数学期望：如果随机变量 $X=X_i$ 的概率为 $P(X=X_i)=p_i$，则称 $E(x)=\sum p_i{x}_i$ 为随机变量 $X$ 的数学期望。

数学期望的一些性质：

1. 线性函数性质，满足：$E(aX + bY) = a \times E(X) + b \times E(Y)$。
2. 如果随机变量 $X$、$Y$ 相互独立，那么：$E(XY) = E(X)E(Y)$。

其中数学期望的线性函数性质是我们能够对数学期望进行地推求解的基本依据。

2.3 全概率公式、全期望公式

概率 DP 的理论基础主要是「全概率公式」。

全概率公式：设 $B_1,B_2,B_3,\dots ,B_n$ 是样本空间 $S$ 中互不相交的一系列事件，并且满足 $S={\cup }_{j=1}^n{B}_j$，那么对于任意事件 $A$，有： $P(A)=\sum _{j=1}^{n}P(A\text{ | }{B}_j)P(B_j)$

「概率 DP」中一般常见的状态转移方程式为：$dp[i] = \sum_{j = 1}^{n} p[i][j] \times dp[j]$。

• 其中 $dp[i]$ 对应全概率公式中的 $P(A)$，$p[i][j]$ 对应了 $P(B_j)$，$dp[j]$ 则对应了 $P(A\text{ | }{B}_j)$。

与概率 DP 类似，期望 DP 的理论基础主要是「全期望公式」。

全期望公式：设 $X$、$Y$ 为随机变量，$E(Y) = E(E(Y \text{ | } X)) = \sum_{j = 1}^n P(x_j) E(Y \text{ | } x_j)$。

「期望 DP」中一般常见的状态转移方程式为：$dp[i] = \sum_{j = 1}^{n} p[i][j] \times dp[j]$。

• 其中 $dp[i]$ 对应全概率公式中的 $E(Y)$，$p[i][j]$ 对应了 $P(x_j)$，$dp[j]$ 则对应了 $E(Y\text{ | }{x}_j)$。

3. 概率 DP 的应用

3.1

参考资料

• 【文章】概率动态规划简介 - 动态规划图文学: 树形、图上、概率 & 博弈动态 - LeetBook
• 【文章】期望动态规划简介 - 动态规划图文学: 树形、图上、概率 & 博弈动态 - LeetBook
• 【文章】浅析竞赛中一类数学期望问题的解决方法 - 汤可因
• 【文章】有关概率和期望问题的研究 - 鬲融
• 【文章】信息学竞赛中概率问题求解初探 - 梅诗珂