概率论
参考：https://zhuanlan.zhihu.com/p/330669300
简介
被期望坑过无数次了。痛定思痛，决定写一写。OI中期望常可以通过线性递推得到状态转移，所以也有很大一部分期望题因此被冠以 “期望/概率DP” 之称，属于广义的 “动态规划” 范畴。当然，OI中涉及的大多是离散概率，所以连续概率这里一贯不提。
定义
- 样本空间 \(\Omega\) 是在问题中可能发生的 所有结果。
- 每个 基本事件 \(\omega\in\Omega\) 有一个 概率 \(\Pr(\omega)\)。其中，明显的有 \(\displaystyle\sum_{\omega\in\Omega}Pr(\omega)=1\)，譬如掷一次骰子，每个面朝上的概率是 \(\cfrac{1}{6}\)。\(Pr\) 被称作 概率分布，通过它将概率值 \(1\) 分布在了各事件 \(\omega\) 之间。
- 一个 事件 \(A\) 则是 \(\Omega\) 的子集。我们可以通过组成事件 \(A\) 的基本事件概率之和定义 事件的概率 \(Pr(\omega\in A)=\displaystyle\sum_{\omega\in A}Pr(\omega)\)。
- 随机变量 \(S(\omega)\) 是在基本事件 \(\omega\) 上定义的 函数 （所以随机变量一定是被定义有一个值的！！）。譬如定义掷两次骰子得到的点数之和为 \(S(\omega)\)，那么我们就可以使之等于 \(2\sim12\)，并计算对应的概率为所有满足这一条件的基本事件概率之和。
注意：一般只涉及一个概率空间时，\((\omega)\) 通常会被省略。
有了这些定义，我们就可以研究同一概率空间内的两个随机变量 \(X、Y\) 了。首先，对于属于其对应取值范围的基本事件 \(x\in X,y\in Y\)，如果有它们的 联合分布 \(Pr(X=x\and Y=y)=Pr(X=x)\cdot Pr(Y=y)\)，那么它们就是 独立 的，互不影响。不然，它们的 条件概率 \(Pr(X=x|Y=y)\)（表示 \(Y=y\) 时 \(X=x\) 发生的概率）则被计算为 \(\cfrac {Pr(X=x\and Y=y)} {Pr(Y=y)}\)。
我们最早涉及到的概率论相关知识无疑是均值、中位数、众数。对于样本空间内取出的 一个事件 \(X\)（注意，这里讨论的概念都 被限制在样本内，这也是为什么说后文提到的期望是均值随样本趋于无穷的极限），它们在这里有了严谨的定义：
- 均值：\(\displaystyle\sum_{x\in X(\Omega)}x\cdot Pr(X=x)\) （\(Pr(X=x)\) 无疑等于 \(\cfrac1 {|X|}\)，每个概率都相等，那么提取这一项就是常见的和除以个数的形式了）
- 中位数：满足 \(Pr(X\le x)\ge \cfrac1{2} \and Pr(X\ge x)\ge\cfrac1 2\) 的集合 \(x\in X(\Omega)\)
- 众数：满足 \(Pr(X=x)\ge Pr(X=x'),\forall x'\in X(\Omega)\) 的集合 \(x\in X(\Omega)\)
而我们的大主角 —— 期望值 现在终于可以被定义了：对于 随机变量（谨记随机变量是函数，有着一个值！） 的 均值 有的特殊名称和记号，\(EX=\displaystyle\sum_{\omega\in \Omega}X(\omega)Pr(\omega)\)。（是的，期望本质就是均值，这也是为什么我们常常看到“期望是一种加权平均数”一说）
有了期望值，我们又能定义 方差：\(VX=E\big((X-EX)^2\big)\)。这可以度量 \(X\) 的分布的 “分散程度”。当然，方差开根后就得到了保持单位不变的 标准差：\(\sigma=\sqrt{VX}\)。
因为期望值相同的情况下，有的飘忽不定，有的稳如老狗，相信在初中没少做过 “选将” 决策：表现均值相同时，将发挥稳定的选手送上赛场无疑更优。
性质
下面简述一些关于同一概率空间定义的两个随机变量 \(X,Y\) 的期望的性质。
期望的 线性性：
- \(X+Y\) 也是该概率空间的随机变量，那么可以发现其和的平均值等于其平均值的和：\(E(X+Y)=\displaystyle\sum_{\omega\in \Omega}(X(\omega)+Y(\omega))Pr(\omega)=EX+EY\)。
- 对于常数 \(\alpha\) 有 \(E(\alpha X)=\alpha EX\)。
乘法法则：
- \(E(XY)=(EX)(EY)\)，如果 \(X\) 和 \(Y\) 独立。
正是其线性性与乘法法则的存在才使得其有了被递推得出答案的可能！
对于它们的应用，譬如对于一对由骰子得到的点数 \(S_1,S_2\)，我们如何应用以上性质？设有 \(S=S_1+S_2,P=S_1S_2\)，那么首先 \(ES_1=ES_2=\cfrac 7 2\)，（骰子掷出点数的期望是 \(ES_x=1\times\cfrac 1 6+...+6\times \cfrac 1 6=\cfrac 7 2\) 是一个经典结论）所以 \(ES=ES_1+ES_2=7\)。又有 \(S_1,S_2\) 独立， \(EP=\cfrac 7 2 \times \cfrac 7 2=\cfrac {49} 4\)，甚至有 \(E(S+P)=ES+EP=7+\cfrac{49} 4\)。掷两次骰子后求它们点数之和加上点数之积的期望？太酷啦！
例题
-
第 \(i\) 个选择题有 \(a_i\) 个选项，那么把正确答案填涂后错一位时期望答对几题？
每个选择题互相独立，总答对数的期望可以相加每个题答对的期望得到。而只有相邻题目答案相同时才有 \(X=1\)。对于第 \(i\) 题，它与前一题的答案搭配起来有 \(a_i\times a_{i-1}\) 种可能。而填错后仍正确只有 \(\min \{a_i,a_{i-1}\}\) 种可能。所以 \(O(n)\) 求和即可。
-
典，求DAG上从 \(1\) 到 \(n\) 节点的期望路径长度
考虑在反图上转移。很明显 \(f[u]=\sum (f[v]+w(u,v))\times \cfrac 1 {degree[v]}\)。
-
典，一瓶饮料上每个球星出现的概率相同。要求收集满 \(n\) 名球星期望买多少瓶饮料？
考虑倒推。\(f(i)\) 表示拥有 \(i\) 名球星，期望要买的饮料数。那么这时第 \(j\) 次买到新球星的概率是 \((\cfrac i n)^{j-1}\times\cfrac {n-i} n\)，\(E=1\times \cfrac{n-i}n+2\times \cfrac i n\times \cfrac{n-i} n+...+j\times(\cfrac i n)^{j-1}\times \cfrac{n-i} n+...\)。
\(f(i+1)=f(i)+E\\=f(i)+1-1\times\cfrac i n+...+j\times (\cfrac i n)^{j-1}-j\times (\cfrac i n)^j+...\\=f(i)+1+\cfrac i n+(\cfrac i n)^2+...\)。其后的无限等比数列求和等于 \(\cfrac n {n-i}\)。所以就得到 \(f(n)=\displaystyle\sum_{i=1}^n\cfrac n {n-i}\)。
拓展：看到的思维题
假设你不断扔一个等概率的六面骰子，直到扔出1,3,5，6停止。求骰子最后一次是6时扔的次数的期望。
\(S=\displaystyle\sum_{i=0}(\cfrac 1 3)^{i}=\cfrac 3 2\)
\(\displaystyle\sum_{i=1}i\times (\cfrac 1 3)^{i-1}=S+S\times \cfrac 1 3+S\times (\cfrac 1 3)^2+...=S\times \big(1+\cfrac 1 3+(\cfrac 1 3)^2+...\big)=S\times S=\cfrac 9 4\)