855学习记录之概率论随机变量（3）全期望公式与期望的上下界分析—— 炎泽汐$de$ Blog

文章目录[隐藏]

• 全期望公式
• 期望的上下界分析

公式

---

条件期望公式：

$$\mathbb{E}\left[X|A\right]=\sum _{x}x\cdot Pr(X=x|A)$$

全期望公式：

$$\mathbb{E}\left[X\right]=\sum _{i=1}^n\mathbb{E}\left[X|B_i\right]\cdot Pr\left(B_i\right)$$

证明：

$$Proof:\mathbb{E}\left[X\right]=\sum _{x}x\cdot Pr(X=x)=\sum _{x}x\cdot \sum _{i=1}^{n}Pr(X=x|B_i)\cdot Pr\left(B_i\right)$$

$$=\sum _{i=1}^{n}Pr\left(B_i\right)\sum _{x}x\cdot Pr(X=x|B_i)=\sum _{i=1}^n\mathbb{E}\left[X|B_i\right]\cdot Pr\left(B_i\right)$$

快排的期望分析

---

令时间复杂度$t\left(n\right)=\mathbb{E}\left(X_n\right)$，其中$X_n$是在$Qsort(A)$中对$n$个不同数的均匀随机排列$A$使用的比较次数。令事件$B_i$为序列$A\left[1\right]$是序列$A$中第$i$小的数字。

此时序列可以分为两个部分较小的集合的容量是$i-1$，较大的集合的容量是$n-i$且初值需要经过$n–1$次比较，故由全期望公式可得：

$$t\left(n\right)=\mathbb{E}\left(X_n\right)=\sum _{i=1}^n\mathbb{E}\left[X_n|B_i\right]\cdot Pr\left(B_i\right)$$

$$=\frac{1}{n}\sum _{i=1}^n\mathbb{E}[n-1+X_{i-1}+X_{j-i}]=n-1+\frac{2}{n}\sum _{i=0}^{n-1}t\left(i\right)$$

琴生不等式

---

期望的单调性

---

最大割的容量

---

对于一个无向图$G(V,E)$，最大割是指使得点集$S\subseteq V$满足$\{\{u,v\}\in E|u\in s\wedge v\ni s\}$成立的最大边集，它是一个$NP-hard$的问题。可以证明总存在一个最大割且容量$\left|S\right|>\left|E\right|/2$。