(1.) 条件概率
定义 (B) 条件下 (A) 事件发生的概率为 (P(A|B))。
有 : (P(A|B) = frac{P(A cap B)}{P(B)})。
全概率公式 :
定义 (B_{1..n}) 是 (Omega) 的一个划分 ， 则有 :
(P(A) = sum_{i=1}^{n}{P(A|B_{i})P(B_{i})})。
贝叶斯公式 :
(P(A|B) = frac{P(B|A)P(A)}{P{B}})。
(2.) 期望的线性性
-
(E(X + Y) = E(X) + E(Y))
-
(E(cX) = cE(X))。
-
(E(XY) = E(X)E(Y))
随机变量的方差 :
定义 : (V = E((X - E(x)) ^ 2))
性质 : (V = E(X ^ 2) - E(X)^2)
证明 : 根据期望的线性性 , (V = E(X) ^ 2 - 2E(X)E(X) + E(X ^ 2) = E(X ^ 2) - E(X) ^ 2)。
快速排序的时间复杂度 :
设对于长度为 (N) 的随机序列 ， 其期望比较次数为 (T(N))。
那么有 :
(T(N) = sum_{i=0}^{N - 1}{T(i)} + N - 1 = frac{2}{N} sum_{i=0}^{N-1}{T(i)} + N - 1)
(N cdot T(N) = 2 sum_{i=0}^{N-1}{T(i)} + N(N - 1))
((N - 1) cdot T(N - 1) = 2 sum_{i=0}^{N - 2}{T(i)} + (N - 1)(N - 2))
(N cdot T(N) - (N - 1) cdot T(N - 1) = 2T(N - 1) + 2(N - 1))
(N cdot T(N) = (N + 1)T(N - 1) + 2(N - 1))
(frac{T(N)}{N + 1} = frac{T(N - 1)}{N} + frac{2(N - 1)}{N(N + 1)})
(F(N) = frac{T(N)}{N + 1} = sum_{i = 0}^{N}{frac{2(i - 1)}{i(i + 1)}} leq sum_{i = 0}^{N}{frac{2}{i}} = 2 ln N)
(T(N) approx NlogN)
马尔可夫不等式 :
(P(x geq a) leq frac{E(x)}{a})。
根据马尔可夫不等式 ， 快速排序复杂度退化至 (O(N ^ 2)) 级别的概率为 (frac{logN}{N})。
切比雪夫不等式 :
(P(|x - E(x)| >= kmu) leq frac{1}{k ^ 2}) ((mu) 为均方差)。
[例题]
(2020) 年高考数学 (江苏卷附加题) 第 (25) 题。
题意 :
第一问 :
直接得到 (p_{1} = frac{1}{3} , q_{1} = frac{2}{3})
(p_{2} = frac{1}{3}p_{1} + frac{2}{9}q_{1} = frac{7}{27})
(q_{2} = frac{2}{3}p_{1} + frac{5}{9}q_{1} = frac{16}{27})
第二问 :
(p_{n} = frac{1}{3}p_{n - 1} + frac{2}{9}q_{n - 1})
(q_{n} = frac{2}{3}p_{n - 1} + frac{5}{9}q_{n - 1} + frac{2}{3}(1 - p_{n - 1} - q_{n - 1}) = -frac{1}{9}q_{n - 1} + frac{2}{3})
因此 (2p_{n} + q_{n} - 1 = frac{1}{3}(2p_{n - 1} + q_{n - 1} - 1))。
注意到 (2_p{n} + q_{n}) 就是 (E(X_{n})) , 直接解上述的递归式 ， 得到 (E(X_{n}) = 1 + frac{1}{3 ^ n})。
(BZOJ3270)
列出期望方程组 ， 高斯消元求解即可。
时间复杂度 : (O(N ^ 3))
(CF963E)
首先朴素的做法是直接高斯消元解期望方程组 ， 但这样的时间复杂度高达 (O(R ^ 6))。
考虑从上到下 ， 从左到右消元。 每次只对当前非 (0) 的位置减法 ， 这样的时间复杂度降至 (O(R ^ 4))。 为什么是这样呢？
如图 ， 假设当前处理的是某个绿色的元素 ， 它的方程中不会含有黄色的未知数。 只会含有 (O(R)) 个绿色的未知数和 (O(1)) 个初始与其相邻的黑色的未知数 ， 不难发现这个方程中系数非零的未知数只有 (O(R)) 个。
同样地 ，含有当前未知数的方程至多也只有 (O(R)) 个 ， 因此处理一个方程复杂度是 (O(R ^ 2)) 的 ， 因此总复杂度是 (O(R ^ 4)) 的。
(HDU4035)
列出方程 ， 注意到每个方程都可以写成一次函数的形式（根据其树上的父亲节点)。
时间复杂度 : (O(N))
(LOJ2263) ((2017)年中国国家队选拔)
首先根据期望的线性性， 对于每个位置计算其贡献。 显然 ， 每个位置的贡献和其左边和右边的第一个已经确定的事件有关。
根据贝叶斯公式 :
(P(X|L,R) = frac{P(L,R|x)P(x)}{P(L,R)} = frac{P(L|x)P(R|x)P(x)}{P(L,R)} = frac{P(L|x)P(R|x)P(x)}{P(R|L)P(L)} = frac{P(x|L)P(R|x)}{P(R|L)})。
注意到分母是个定值 ， 而分子可以通过简单的矩阵乘法维护。
那么用平衡树维护已经确定的位置集合， 线段树维护矩阵， 即可。
时间复杂度 : (O((N + M)logN))
(BZOJ 4318)
令随机变量 (Y_{i}) 表示到 (i) 为止的期望后缀长度 , (f(i)) 表示第 (i) 位为止得分期望。
加入第 (i) 位后 ， (f(i) - f(i - 1) = P_{i}(E(Y_{i - 1} + 1) ^ 3 - E(Y_{i - 1} ^ {3})))。
根据期望的线性性 ， 展开后维护 (Y_{i}) 的期望和 (Y_{i} ^ 2) 的期望即可。
时间复杂度 : (O(N))。
(LOJ2125)
首先最优策略一定是从大往小依次按。
设 (dp_{i}) 表示还剩 (i) 盏灯的期望次数 ， 将转移看做方程 ， 解方程即可。
时间复杂度 : (O(N))
(LOJ2547)
来自 (2018) 江苏省选。
首先考虑树的情况 ， 由期望的线性性 ， 考虑每条边的贡献 ， 显然 ， 如果一条边出现在了斯坦纳树中 ， 那么其分割成的两个联通块中都要有点在集合 (S) 中 ， 故其贡献为 : ((2 ^ {siz_{u}} - 1)(2 ^ {siz_{v}} - 1))。
接着 ，考虑仙人掌图的情况 ， 显然可以将割边和环的贡献分别计算 ， 割边的贡献和树上的情况是类似的。 只需在执行 (Tarjan) 算法的过程中顺带维护子树大小即可。
考虑环的贡献 ， 不妨称环上一个点被选中当且仅当其或其搜索树上的外向树中有节点在 (S) 集合中。 既然是求最小斯坦纳树， 那么必然是在环上去掉相邻且距离最远的一对被选中的点之间的所有边。
考虑动态规划 ，设 (dp_{l , r , k}) 表示第一个被选中的点为 (l) ， 最后一个点在 (r) ， 相邻的被选中的点距离最远为 (K) 的方案数。 分类讨论转移即可。 可以前缀和优化做到 (O(N ^ 3))。
(LOJ2542)
来自 (2018) 北大冬令营。
直接求解显然是不切实际的。
考虑要求的是 (E(Max(S)))。
根据 (Min - Max) 容斥和期望的线性性 ， 有 (E(Max(S)) = sum_{T subseteq S}{(-1)^{|T| + 1}E(Min(T))})。
也就是说 ， 要求的是 (x) 到达某个集合 (T) 中任意一个点的期望时间。
考虑动态规划 ， 记 (f_{u}) 表示点 (u) 的期望步数。 这个动态规划的转移非常经典 ， 只需要将方程写成 (y = kx + b) 的形式即可。
预处理完动态规划数组后 ， 用 (FMT) 高维前缀和计算答案 , 这道题就做完了。
时间复杂度 : (O(N2^N))