min-max反演

 设 $S$ 是一个集合, $max(S)$ $min(S)$ 分别表示集合的最大值和最小值,那么有
$$max(S) = \sum_{T \subseteq S}(-1)^{|T| + 1}min(T)\\min(S) = \sum_{T \subseteq S}(-1)^{|T| + 1}max(T)$$
拿第一个式子为例证明一下:
 
$\alpha = max(S)$ ,那么只有当 $T = \{\alpha\}$ 时, $min(T) = \alpha$ ,因此 $min(T) = \alpha$ 的项的和为 $\alpha$。而对于每个 $\beta \neq \alpha$ ,有 $T= \{\beta\} \cup T'$ $T' \subseteq S'$ $S'$ $S$ 中所有 $\geq \beta$ 的元素的集合)满足 $min(T) = \beta$ 。而由二项式定理得 $(1 + (-1))^n = C_n^0 - C_n^1 + C_n^2 - C_n^3 \cdots$ ,所以长度为奇数和偶数的 $\{\beta\} \cup T'$ 数量相等,因此所有 $min(T) = \beta$ 的项的和等于0。所以 $\sum_{T \subseteq S}(-1)^{|T|+ 1}min(T) = \alpha = max(S)$
 
这个式子在期望下也是成立的
$$E[max(S)] = \sum_{T \subseteq S}(-1)^{|T| + 1} E[min(T)]$$用期望的线性性证明即可:
$$E[max(S)] = E(\sum_{T \subseteq S}(-1)^{|T| + 1}min(T))=\sum_{T \subseteq S}(-1)^{|T| + 1}E[min(T)]$$


评论

此博客中的热门博文