前置定义

$\Omega$ ：样本空间。

$P$ : 概率函数。

例：投掷骰子，

$\Omega = \{1,2,3,4,5,6\} , P(x) = \frac{1}{6} , \forall x \in \Omega$

显然的，如果一个样本空间是合法的，那么

\[\sum_{x\in \Omega} P(x) = 1 \]

$E$ ：事件。$E \subseteq \Omega $ 表示 $E$ 是样本空间的一个子集。

自然的，定义一个事件的概率为

\[P(E) = \sum_{x\in E} P(x) \]

和事件：记作 $A \cup B$ 或 $A + B$ ，当且仅当事件 $A$ 和事件 $B$ 至少一个发生时，事件 $A\cup B$ 发生。

积事件：记作 $A\cap B$ 或 $AB$ ，当且仅当事件 $A$ 和事件 $B$ 同时发生时，事件 $A\cap B$ 发生。

互斥事件：记作 $A\cap B=\varnothing$，事件 $A$ 和事件 $B$ 的交集为空，即不能同时发生。

对立事件： $A\cup B=S$ 且 $A\cap B=\varnothing$ ，整个样本空间仅有事件 $A$ 和事件 $B$ ，即每次实验必有一个且仅有一个发生

随机变量：在概率空间 $(\Omega,P)$ 下，映射 $X:\Omega \rightarrow \mathbb{R}$ 称作一个随机变量。

更透彻的了解随机变量？this

概率

性质

非负性：对于任意一个事件 $A$ ，$0\leq P(A) \leq 1$
规范性：对于必然事件 $A$ ，$P(A) = 1$ ，对于不可能事件，$P(A) = 0$
互斥事件可加性：对于 $n$ 个互斥的事件，$P(A_1 \cup A_2 \cup \dots\cup A_n) = P(A_1) + P(A_2) +\dots + P(A_n)$

对于不互斥的事件，运用容斥思想，这里仅给出两个事件的情况：

\[P(A\cup B) = P(A) + P(B) - P(A\cap B) \]
独立事件可乘性：对于 $n$ 个对立的事件，$P(A_1 \cap A_2 \cap \dots\cap A_n) = P(A_1) \times P(A_2) \times \dots \times P(A_n)$

古典概型

必修一讲的很详细/cy

条件概率

略微重量级。

定义：事件 $A$ 在 另外一个事件 $B$ 已经发生的条件下 发生的概率。用符号表示为 $P(A | B)$ , 读作“在 $B$ 的条件下 $A$ 的概率”。

两个事件同时发生的概率为 $P(AB)$ ，那么就有： $P(A|B) = \frac{P(AB)}{P(B)}$

感性理解：在 $B$ 的条件下 $A$ 发生的概率，和 $B$ 发生的概率，就是 $AB$ 同时发生的概率。

乘法公式

由上面公式推广可以得到 $P(AB) = P(A|B)P(B) = P(B|A)P(A)$

再推广一下：对于任何正整数 $n \ge2$ ，当 $P(A_1A_2\dots A_{n-1}) > 0$ 时，就有：

\[P(A_1A_2\dots A_n) = P(A_1)P(A_2|A_1)P(A_3|A_1A_2)\dots P(A_n|A_1A_2 \dots A_{n-1}) \]

全概率公式

如果事件组 $B_1,B_2,\dots B_n$ 满足

$B_1,B_2\dots B_n$ 两两互斥且 $P(B_i) > 0$
$B_1 \cup B_2 \cup \dots \cup B_n = \Omega$

则称事件组 $B_1,B_2 \dots B_n$ 是样本空间 $\Omega$ 的一个划分。A是其中的任一事件，则有

\[P(A) = \sum_{i=1}^{n} P(B_i) \times P(A|B_i) \]

这就是 全概率公式。

这玩意的意义就是对于直接计算 $P(A)$ 比较困难的情况下，将样本空间分成几部分，由此把 $A$ 再分成几个小事件，通过求小事件的概率，并运用加法原理，求出整个事件的概率。

贝叶斯公式

这玩意就是

\[P(A|B) = \frac{P(AB)}{P(B)} \]

也可以写成

\[P(A|B) = \frac{P(A)P(B|A)}{P(B)} \]

期望

这位才是重量级

随机变量的期望

万恶之源。
期望用 $E$ 来表示。

\[E(X) = \sum_{\omega \in \Omega}P(\omega)X(\omega) = \mu \]

$X(\omega)$ 就代表着这个随机变量映射后的数。

注：以下有的地方为了防止变量名重复，有时会省略 $X()$

性质

期望的线性关系：

对于两个随机变量 $X,Y$ ，我们有：

\[ E(\alpha X+\beta Y) = \alpha E(X) + \beta E(Y) \]

特别的，当 $\alpha = \beta = 1$ 时，则有

\[E(X+Y) = E(X) + E(Y) \]

证明：

根据定义来就行，设 $s$ 表示抽取一次事件。

\[E(A+B) = \sum_{s}X(A+B)P(s) \]

\[= \sum_sX(A)(s)P(s) + \sum_sX(B)(s)P(s) \]

\[= E(A) + E(B) \]

可以看出期望的线性关系跟这两个随机变量是否独立无关。

\[E(\sum_{i=1}^nc_iX_i) = \sum_{i=1}^nc_iE(X_i) \]

样本均值的期望

\[E(\bar X) = \frac{1}{n}(\sum_{i=1}^n E(X)) = \frac{1}{n} \cdot n \cdot \mu =\mu \]

比较显然。

期望的乘积

对于两个相互独立的随机变量 $X,Y$ ，则有

$E(XY) = E(X)E(Y)$

因为只有独立了 $P(XY) $ 才能 $= P(X)P(Y)$ ，前面的不用是因为前面是求和不是乘积。

期望的方差

方差用于表示数据的分散程度。定义式：

\[Var(x) = \sigma^2 = \sum(x-\mu)^2P(X) \]

性质

\[Var(bX) = \sum(bX-b\mu)^2P(X) = b^2Var(x) \]

我们可以知道， $P(X) = P(bX)$ ，概率是一样的，但是权值会放大 $b$ 倍，最后就是放大 $b^2$ 倍。

\[Var(x) =\sum(x-E(x))^2P(x) \]

这就是方差的另一种定义，其实就是把 $\mu$ 换成了 $E(X)$ 而已。

重点

\[Var(x) = E(X^2) - E(X)^2 \]

证明：

\[Var(x) = E((x-E(x))^2) \]

\[= E(X^2 - 2XE(X) + E(X)^2) \]

\[= E(X^2) - E(2XE(X)) + E(E(X)^2) \]

\[= E(X^2) - \sum 2XE(X)P(X) + \sum E(X)^2P(X) \]

$E(X)$ 视为常数，提前；又因为 $\sum P(X) = 1$ ，得到下式

\[= E(X^2) - 2E(X)^2 + E(X)^2 = E(X^2) - E(X)^2 \]

如果 $X,Y$ 是独立的随机变量，那么 $Var(X+Y) = Var(X) + Var(Y)$

证明：根据性质 $3$ 得：

\[Var(X+Y) = E(X+Y)^2) - E(X+Y)^2 \]

\[=E(X^2+2XY+Y^2) - (E(X)+E(Y))^2 \]

\[= E(X^2) + E(2XY) + E(Y^2) - E(X)^2 - E(Y)^2 - 2E(XY) \]

\[= E(X^2) -E(X)^2 + E(Y^2) - E(Y)^2 \]

\[= Var(X) + Var(Y) \]

此结论也可推广到 $n$ 个独立的随机变量。
5. 样本均值的方差

\[Var(\bar X) = Var(\frac{X_1+X_2+\dots +X_n}{n}) \]

根据性质 $1$ 和性质 $4$ 得：

\[Var(\bar X) = \frac{1}{n^2}(Var(X_1)+Var(X_2) +\dots + Var(X_n)) \]

\[= \frac{1}{n^2} \cdot n \cdot \sigma^2 = \frac{\sigma^2}{n} \]

应用

概率/期望 DP

概率期望用的最多的还是这里。

概率 DP

一般采用正推的形式，即一般是知道了起始态，向终止态枚举。

转移方程是跟概率挂钩的。

期望 DP

一般采用倒推的形式，即一般是知道了终止态，向起始态枚举。

期望 DP 的套路主要分为两类

当转移关系不成环时。这种情况我们可以把问题抽象成一个 DAG 。因为我们已经知道了终点也就是终止态，问题往往就是问起始态的期望。DAG 的反图还是 DAG ，我们利用这个性质建反图跑拓扑排序，即可求出起始态。
当转移关系成环时。这种情况就没有 DAG 那样好的性质了。我们设好状态，表示出状态与状态之间的转移关系，常数项放在右边，其余的放在左边，表示出系数。高斯消元求解即可。