Probabilistic Method

符号约定

均值：\(\mu=\mathbb{E}[X]\)

方差：\(\sigma=\text{Var}[X]\).

斜方差：\(\text{Cov}(X,Y)\).

引入

对于 0/1 随机变量 \(X_i\)（也对应着一个事件是否发生），令 \(X=\sum X_i\)，考虑如下显然的性质：

\[\Pr[\bigvee X_i]=\Pr[X\ge 1]\leq \mathbb{E}[X] \]

(Markov Inequality)

由此，当 \(\mathbb{E}[X]\to 0\) 时，我们可以说几乎所有事件 \(X_i\) 都不发生。

这个 bound 非常松，但是由于计算期望比计算所有事件发生的概率容易的多，在很多场景下用于简单估计。

一类问题的刻画

本文中用如下的问题来讲解 Probabilistic Method。

假设有随机图： \(G(n,p)\)：\(|V|=n\)，所有 \(\binom{n}{2}\) 条边独立，以 \(p\) 的概率出现。

有性质：\(A: \mathbb{G} \to \{0,1\}\)，例如 \(A:\) \(G\) 含有一个三元环。

很显然，当 \(p\) 越大，\(A(G)\) 成立的概率也越高，我们希望找到一个 \(p_n\)，使得：

当 \(p\gg p_n\) 时，\(\Pr[A(G)] \to 1\)。
当 \(p\ll p_n\) 时，\(\Pr[A(G)]\to 0\)。

这样的一个 threshold 在估计特定问题时效果非常好，比如：在特定温度考虑一个物质的结构，可以认为其中的每一个分子团之间有 \(p\) 的概率有边，当 \(n\to +\infty\) 时，通过描述图的大致形态来分析相态变化。

这里对于 \(p_n\) 存在性给出定理：

Theorem(Bollobas, Thomason, 1987):
对于所有单调增的性质 \(A\)，\(p_n\) 总存在。
单调增的定义：在满足性质的图上加入一条边依然满足性质，即 \(A(G)\implies A(G\cup \{e\})\)

FOL \(\forall, \exists, x,y,z\) ; \(\neg,\land,\lor,\to,\leftrightarrow\) ; \(=,\sim,(,)\)
we use such FOL to describe \(A\).

Theorem (Glebskii et al 1969, Fagin 1976)
对于任何固定的 \(p\in (0,1)\)，若 \(A\) 可以用一阶逻辑表示，则 \(\lim_{n\to+\infty} \Pr[G(n,p)\vDash A]=0 / 1\)
(定理说明常数无法作为 threshold)

Theorem (Shelah and Spencer, 1988)
对于任何非有理数 \(\alpha\in (0,1)\), \(p_n=\frac{1}{n^{\alpha}}\), 若 \(A\) 可以用一阶逻辑表示, \(\lim_{n\to+\infty} P(G(n,p)\vDash A)=0 / 1\)
(定理说明 \(\frac{1}{n^{\alpha}}\) 无法作为 threshold)

First Moment Method

第一类概率方法的核心即引子里提到的 \(\Pr[\bigvee X]\leq \mu\)。

考虑用这个方法来估计三元环出现的概率，令 \(X_i\) 表示图中任意三个点之间成环。

则 \(\mu=\binom{n}{3} p^3\sim (np)^3\)，故当 \(p=o(n^{-1})\) 时，\(\mu \to 0\)，即图中几乎不可能出现三元环。

期望的估计固然简单，但是也存在显然的缺陷，比如：

若 \(\Pr[X=0]=1-\frac{1}{n},\Pr[X=n^2]=\frac{1}{n}\),
则： \(\mathbb{E}>1,\Pr[X\ge 1]\to 0\). (期望容易受到一个特殊单点的影响)。

Second Moment Method

第二类概率方法用于估计 \(\Pr[X= 0]\to 0\)，即证明 threshold 的另一边。

由 Chebyshev Inequality: \(\Pr[|X-\mu|\ge \lambda \sigma]\leq\frac{1}{\lambda^2}\)
则 \(\Pr[X=0]\leq P(|X-\mu|\ge \mu)\leq \frac{\sigma^2}{\mu^2}=\frac{\mathbb{E}(X^2)}{\mathbb{E}(X)^2}-1\)

由 Cauthy inequality: \((\mathbb{E}(X))^2\leq \Pr[X\ge 1]\cdot \mathbb{E}(X^2)\)
则 \(\Pr[X=0]\leq \frac{\sigma^2}{\mathbb{E}(X^2)}=1-\frac{\mathbb{E}(X)^2}{\mathbb{E}(X^2)}\)

这样我们就可以通过计算 \(\mathbb{E}[X]\) 和 \(\mathbb{E}[X^2]\) 来估计 \(\Pr[X=0]\) 的上界。

不过有时候计算 \(\mathbb{E}[X^2]\) 并不是容易事，这里我们也可以总结出一些条件。

\(\sigma^2=\sum \text{Var}(X_i)^2 +\sum_{i\ne j} \text{Cov}(X_i,X_j)\xlongequal{\Delta}I_1+I_2\)，我们想要 \(\sigma^2=o(\mu^2)\).

\(I_1=\sum\mathbb{E}(X_i^2)-\mathbb{E}(X_i)^2\leq \sum\mathbb{E}(X_i^2)\)，在我们的问题中基本可以认为 \(\sum \mathbb{E}(X_i^2)= o(\mu^2)\)

\(\begin{aligned}I_2&=\sum_{i\ne j} \text{Cov}(X_i,X_j)\\&=\sum_{i\ne j}\mathbb{E}(X_iX_j)-\mathbb{E}(X_i)\mathbb{E}(X_j)\\&=\sum_{i}\Pr[X_i] \sum_{j\ne i}(\Pr[X_j\mid X_i]-\Pr[X_j])\\&\leq \Delta^*\sum \Pr[X_i]\\&=\Delta^*\mu\end{aligned}\)
where \(\displaystyle \Delta^*=\max_i\{\sum_{j\ne i}\Pr[X_j\mid X_i]-\Pr[X_j]\}\)

于是我们估计得 \(\sigma^2= o(\mu^2)+O(\Delta^*\mu)\)

只需要 \(\Delta^*=o(\mu)\) 即可说明 \(\Pr[X=0]\to 0\)

回到三元环问题， \(\mu=n^3p^3\), 每一个 \(X_i\) 与 \(3(n-3)\) 个 \(X_j\) 相关，所以 \(\Delta^*=3(n-3)(p^2-p^3)\sim np^2\)

当 \(p\gg n^{-1/2}\) 时，有 \(\Delta^*=o(\mu)\)，此时 \(\Pr[X=0]\to 0\)

总结

1st: 估计期望，\(\mu\to 0 \implies P(X\ge 1)\to 0\)
2nd: 三种方法， \(\begin{cases}\sigma^2=o(\mu^2)\\\sigma^2=o(\mathbb{E}(X^2))\\\Delta^*=o(\mu)\end{cases}\implies P(X=0)\to 0\)