概率
概述
- 概率即随机事件出现的可能性大小。
性质
-
概率满足贝叶斯公式，但这和 OI 没啥关系。
-
对于相互独立的事件，概率满足加法原理和乘法原理。
-
这里的加法原理指求多个事件至少发生一个的概率，乘法原理指某些事件同时发生的概率。
-
对于独立事件，可以表示为：\(P(B\mid A)=P(A),P(A\times B)=P(A)\times P(B)\)。其中 \(P(B\mid A)\) 表示 \(A\) 在 \(B\) 发生的条件下发生的条件概率，\(P(A\times B)\) 表示 \(A,B\) 同时发生的概率。
求解
-
对于实数：可以考虑模拟。有限样本空间可以全枚举，无限样本空间可以使用随机（请使用 mt19937）。
-
dp。利用加法和乘法原理，构造递推式递推。如果有环，那么可以使用高消。
-
对于事件等概率的情况或能转化为事件等概率的情况：转化为求各事件方案数，然后除以总方案数。
期望
概述
-
\(E=\sum\limits_iP_i\times (v_i\ or\ c_i)\)。根据求的是发生事件的价值或代价而不同。
-
更自然语言的定义：对于一个样本空间，如果我们把其中的事件赋上价值或代价，那么期望就是这个样本空间的平均价值/代价。
求解
-
按照定义式。有些时候会进一步地把概率转化成方案数，即所谓“黄金公式”，参看随机数生成器、T4 砍树。
-
同概率，利用递推性。举个例子，在有向无环图上求每个点到终点的期望距离（注意这是个逆向 dp！），则 \(E(now)=\dfrac{1}{sons}(E(son)+edge.len)\)（注意这是一个抽象模型，凡是可递推的都可以抽象成图。参看迷失游乐园）。
-
分步计算。相当于推式子，将之转化为第 \(i\) 次尝试的概率。则 \(E=\sum\limits_iP_i\times v_i\)，这里的 \(P_i,v_i\) 是第 \(i\) 次成功；然后定义 \(P_i',v_i'\) 为进行了第 \(i\) 次尝试，则有 \(E=\sum\limits_iP_i'\times v_i'\)。