11 二阶矩方法和Lovasz局部引理-Toy模板网

这篇具有很好参考价值的文章主要介绍了11 二阶矩方法和Lovasz局部引理。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

11 二阶矩方法和Lovasz局部引理

11.1 The Second-Moment Method——二阶矩方法

11.1.1 二阶矩方法定理

首先写出二阶矩方法的定理：

若存在非负随机整数 $X$ ，则有：
$\leq \frac{Var[X]}{{(E[X])}^2}$

证明：
$\leq P(|X-E[X]| \geq E[X]) \leq \frac{Var[X]}{{(E[X])}^2}$

11.1.2 二阶矩方法的应用——随机图阈值

二阶矩方法可以应用在，对随机图中的阈值进行概率求解。

首先了解一下什么是随机图中的阈值：

假设有一个图模型被定义为 $G_{n, p}$ ，其中 $n$ 表示图的节点数量， $p$ 表示随机图的阈值。
$p$ 的阈值表示为一个函数 $f (n)$ ：在当 $p > f (n)$ 时，图 $G_{n, p}$ 会拥有图的一些性质；当 $p < f (n)$ 时，图 $G_{n, p}$ 不拥有这些性质。

在这里要补充一下（因为我是第一次实际用到这个知识）：

$o (n)$ 表示函数的上界，表示绝对不会到这个大小。
$\omega(n)$ 表示函数的下界，表示函数一定更大。

下文中说 $\rightarrow 0$ 就是这个原因，因为这并非表示 $o (1)$ ，而是一定比 $o (1)$ 更小。

接下来我们给出关于随机图的一条定理：

在图 $G_{n, p}$ 中，若在 $o(n^{-\frac{2}{3}})$ 且 $n$ 足够大的条件下。对于任意的 $\varepsilon > 0$ ，使得：
$P(|\text{顶点数大于4的团}| \geq 1) < \varepsilon$
若 $\omega(n^{-\frac{2}{3}})$ ，其余条件不变的情况下，有：
$P(|\text{顶点数大于4的团}| \geq 1) > 1 - \varepsilon$
也可以写作：
$P(|\text{顶点数大于4的团}| = 0) < \varepsilon$

证明1：定理中 $o(n^{-\frac{2}{3}})$ 的情况：

图中取出4个顶点一共有 $C_n^4$ 中情况。假设我们通过 $X_i$ 表示第 $i$ 种情况下，四个顶点组成的是否是团，可以表示为：
$X_i = \begin{cases} 1 & \text{if $C_i$ is a 4-clique} \\ 0 & \text{otherwise} \end{cases}$
根据第一点我们可以知道 $\sum_{i=1}^{C_n^4} X_i$ ，同时因为一个四顶点的团有6条边，可得：
$C_n^4 p^6 = O(n^4) \cdot o(n^{-4}) = o(1) \rightarrow 0 < \varepsilon$
又因为Markov Inequality有 $\geq 1) \leq E[X]$ ，可得：
$\geq 1) \leq E[X] < \varepsilon$

证明2：定理中 $\omega(n^{-\frac{2}{3}})$ 的情况：

对于定理中 $\omega(n^{-\frac{2}{3}})$ 的情况，为了证明 $\varepsilon$ ，我们需要用到二阶矩定理，可以将问题转化为证明 $\leq \frac{Var[X]}{{(E[X])}^2} < \varepsilon$ 。但是期望好求，方差不好求，所以我们要先引入一条定理：

定理：若 $Y_i, i \in [1, m]$ 表示0-1随机变量，且 $\sum_{i=1}^{m} Y_i$ ，可得
$\leq E[Y] + \sum_{1 \leq i, j \leq m; i \neq j} Cov(Y_i, Y_j)$
证明：

对于随机变量序列可以做如下转换：
$Var[\sum_{i=1}^{m} Y_i] = \sum_{i=1}^m Var[Y_i] + \sum_{1 \leq i, j \leq m; i \neq j} Cov(Y_i, Y_j)$

因为方差的性质可得：
$Var[Y_i] = E[Y_i^2] - {E[Y_i]}^2 \leq E[Y_i]$

代入第一个公式就可得：
$\begin{align} Var[Y] &\leq \sum_{i=1}^m E[Y_i] + \sum_{1 \leq i, j \leq m; i \neq j} Cov(Y_i, Y_j) \\ &= E[Y] + \sum_{1 \leq i, j \leq m; i \neq j} Cov(Y_i, Y_j) \end{align}$

根据方差的不等式定理，我们知道除了期望还要考虑协方差。我们已知协方差的计算公式为：
$C o v (X, Y) = E [X Y] - E [X] E [Y]$
假如我们选取的点集（四个点）的情况表示为 ${\lbrace C_1, C_2, \dots, C_{C_n^4} \rbrace}$ ，我们可以将协方差分为四类：
1. 没有公共点：8个点，12条边， $C_n^8 \cdot p^{12} = E[X]E[Y] = C_n^4 \cdot p^6 \cdot C_n^4 \cdot p^6$
2. 有一个公共点：7个点，12条边， $C_n^7 \cdot p^{12} = E[X]E[Y] = C_n^4 \cdot p^6 \cdot C_4^1 C_{n-4}^3 \cdot p^6$
3. 有两个公共点：6个点，11条边， $C_n^6 \cdot p^{11} > E[X]E[Y] = C_n^4 \cdot p^6 \cdot C_4^2 C_n^2 \cdot p^6$
4. 有三个公共点：5个点，9条边， $C_n^5 \cdot p^{9} > E[X]E[Y] = C_n^4 \cdot p^6 \cdot C_4^3 C_n^1 \cdot p^6$
因为 $E [X Y] - E [X] E [Y] < E [X Y]$ 恒成立，我们直接用 $E [X Y]$ ，可以得到：
$\begin{align} Var[Y] &\leq E[Y] + \sum_{1 \leq i, j \leq m; i \neq j} Cov(Y_i, Y_j) \\ &\leq C_n^4 \cdot p^6 + C_n^6 \cdot p^{11} + C_n^5 \cdot p^9 \\ &= O(n^4 q^6 + n^6 q^{11} + n^5 q^9) \end{align}$
代入公式 $\leq \frac{Var[X]}{{(E[X])}^2}$ 可得：
$\begin{align} P(X = 0) &\leq \frac{Var[X]}{{(E[X])}^2} \\ &= \frac{O(n^4 q^6 + n^6 q^{11} + n^5 q^9)}{{o(n^4 q^6)}^2} \\ &= O(n^{-4} q^{-6} + n^{-2} q^{-1} + n^{-3} q^{-3}) \end{align}$
当 $\omega(n^{-\frac{2}{3}})$ 时可得：
$P(X = 0) = o(1 + n^{-4/3} + n^{-1}) = o(1)$

11.2 Lovasz Local Lemma——Lovasz局部引理

11.2.1 LLL定理

在介绍定理之前，我们先介绍一下事件独立性的概念：

假定有一组事件 $A_1, A_2, \dots, A_n$ ，他们发生的概率 $P(A_i) \leq p < 1$ ，如果他们互相独立，则有：
$P(\cap_{i} {\bar {A_i}}) \geq {(1 - p)}^n > 0$
与上条件相同，但事件之间相互不独立，则有：
$P(\cap_{i} {\bar {A_i}}) \geq 1 - \sum P(A_i)$
对于独立的事件具有以下的性质：
$\cap_{i \in [1, N]} A_i)$

我们给LLL定理一个定义：

假设有一组事件 $A_1, A_2, \dots, A_n$ ，满足 $\forall i, P(A_i) \leq p$ ，其中 $A_i$ 与除了 $d$ 个事件之外的事件都相互独立，则有：
1. 若 $\leq \frac{1}{4}$ ，则有 $P(\cap_{i} {\bar {A_i}}) \geq {(1 - 2p)}^n > 0$
2. 若 $\leq \frac{1}{e}$ ，则有 $P(\cap_{i} {\bar {A_i}}) \geq {(1 - \frac{1}{d+1})}^n > 0$

11.2.2 LLL定理证明

这里证明一下 $\leq \frac{1}{4}$ 的情况。

为了证明LLL，这里引入一条引理，就非常好证明LLL了：

Lemma：对于任意一个集合 $\subset {\lbrace A_1, A_2, \dots, A_n \rbrace}$ ，对于任意 $\notin S$ ，有：
$\cap_{j \in S} {\bar {A_j}}) \leq 2p$

通过这条引理我吗就可以证明LLL定理了：

我们将LLL定理中的 $P(\cap_{i} {\bar {A_i}})$ 展开得：
$P(\cap_{i} {\bar {A_i}}) = {(1-P(A_1))} {(1-P(A_2|{\bar {A_1}}))} \dots {(1-P(A_i|\cap_{j < i}{\bar {A_j}}))}$
根据上文的Lemma可以知道：
$\begin{cases} P(A_1) \leq 2p \\ P(A_2|{\bar {A_1}}) \leq 2p \\ \dots \\ P(A_i|\cap_{j < i}{\bar {A_j}}) \leq 2p \\ \end{cases}$
所以可以将公式转换为：
$P(\cap_{i} {\bar {A_i}}) \geq {(1-2p)}^i = {(1-2p)}^n$

所以我们接下来主要证明上述Lemma

我们分成两种情况来讨论：

$∣ S ∣ = 0$ ：没有集合的情况下说明没有其他的事件，所以可得
$\empty) = P(A) \leq p \leq 2p$
得证 $∣ S ∣ = 0$ 时刻
$∣ S ∣ = k + 1$ ：我们假设引理适用于 $\leq k$ 的所有情况，通过数学归纳法证明 $∣ S ∣ = k + 1$ 时刻的情况。

第一种情况我们简单就证明了，核心就在第二种情况上，我们先来给第二种情况做一些定义：

根据LLL定理的条件已知 $\leq \frac{1}{4}$
我们假设有一个事件 $A$ ， $S$ 表示不包含事件 $A$ 的一个事件集合
根据与 $A$ 事件的相对独立性，我们将 $S$ 分成两部分： $S^{ind}$ 表示 $S$ 中与 $A$ 相对独立的事件、 $S^{dep}$ 表示 $S$ 中与 $A$ 有依赖关系的事件

根据以上定义，再次分成两种情况：

当 $S^{ind}| = k+1$ 时，或者说是 $S^{ind} = S$ 时，我们可得：
$\cap_{j \in S} {\bar {A_j}}) = P(A) \leq p \leq 2p$
得证 $∣ S ∣ = k + 1$ 且 $S^{ind}| = k+1$ 的情况
当 $S^{ind}| < k+1$ 时，我们可以通过Bayes Formula将 $S$ 通过条件概率的方式拆分开：
$\begin{align} P(A| \cap_{j \in S} {\bar {A_j}}) &= P(A| \cap_{j \in S^{dep}} {\bar {A_j}}, \cap_{j \in S^{ind}} {\bar {A_j}}) \\ &= \frac{P(A, \cap_{j \in S^{dep}} {\bar {A_j}}| \cap_{j \in S^{ind}} {\bar {A_j}})}{P(\cap_{j \in S^{dep}} {\bar {A_j}}| \cap_{j \in S^{ind}} {\bar {A_j}})} \end{align}$

通过对条件的Bayes变换，我们可以分别将分子与分母求解出来：

分子：
$\begin{align} P(\cap_{j \in S^{dep}} {\bar {A_j}}| \cap_{j \in S^{ind}} {\bar {A_j}}) &\geq \underbrace{ 1 - \sum_{j\in S^{dep}} \overbrace{P(A_j| \cap_{j \in S^{ind}} {\bar {A_j}})}^{ =P(A_j) \text{—独立} } }_{P(\cap_{i} {\bar {A_i}}) \geq 1 - \sum P(A_i)} \\ &\geq 1 - \underbrace{|S^{dep}|}_{pd \leq \frac{1}{4} \implies |S^{dep}| = d \leq \frac{1}{4p}}(2p) \\ &\geq 1- \frac{1}{4p} \cdot 2p \\ &= \frac{1}{2} \\ \end{align}$
分母：
$\cap_{j \in S^{dep}} {\bar {A_j}}| \cap_{j \in S^{ind}} {\bar {A_j}}) \leq \underbrace{P(A| \cap_{j \in S^{ind}} {\bar {A_j}})}_{=P(A) \text{—独立}} \leq p$

由此可证在 $∣ S ∣ = k + 1$ 且 $S^{ind}| < k+1$ 的情况下：
$\cap_{j \in S} {\bar {A_j}}) = \frac{P(A, \cap_{j \in S^{dep}} {\bar {A_j}}| \cap_{j \in S^{ind}} {\bar {A_j}})}{P(\cap_{j \in S^{dep}} {\bar {A_j}}| \cap_{j \in S^{ind}} {\bar {A_j}})} \leq 2p$

11.3 Asymmetric LLL

在上一节的LLL中，我们只用到了两个参数： $p$ 表示概率、 $d$ 表示临域的大小。上一节我们通过定义 $p, d$ 之间的关系求解了概率边界，我们自然会想要通过更普遍的方式求得概率边界。于是我们提出了Asymmetric LLL，下面我们做一个定义：

Asymmetric LLL（非对称LLL）：有一组事件表示为 $A_1, A_2, \dots, A_n$ ，其中 $S_i \subset {\lbrace A_1, A_2, \dots, A_n \rbrace}$ 表示一组与 $A_i$ 相对独立的事件集合。假设存在一组变量 $r_1, \dots, r_n \in [0, 1)$ ，且满足 $\forall i, P(A_i) \leq r_i \prod_{j \notin S_i}(1-r_j)$ ，则有
$P(\cap_{i} {\bar {A_i}}) \geq \prod_{i}(1-r_i)$

这条定理本文就不做证明，但是这条定理是包含LLL的，我们可以做一个分析：

假设 $r_i = \frac{1}{d+1}$ ，我们可以通过在LLL中的定义得到：
$\begin{align} & P(A_i)(d+1) \leq \frac{1}{e} \\ \implies& P(A_i) \leq \frac{1}{d+1} \cdot \frac{1}{e} \leq \frac{1}{d+1} \cdot {\left( 1 - \frac{1}{d+1} \right)}^d \\ &\leq \frac{1}{d+1} \cdot \prod_{j \notin S_i}{\left( 1 - \frac{1}{d+1} \right)} = r_i \cdot \prod_{j \notin S_i} {(1-r_i)} \end{align}$
这样条件就等价变换了
然后代入Asymmetric LLL的结果中可以得到：
$P(\cap_{i} {\bar {A_i}}) \geq \prod_{i}(1-r_i) = {(1-\frac{1}{d+1})}^n > 0$
结果也与LLL等价了