对于给定的 \(n\) 个顶点, 对于任意一个点对, 以 \(p\) 的概率连边, 这样得到的一个无向简单图上的概率分布, 称为 Erdős–Rényi 随机图模型.
那么, \(p\) 有多大的时候, 得到的图将会有很大概率连通呢? Erdős 和 Rényi 给出了如下结果:
对于 \(p = (\log n + c) / n\), 记事件 \(A(G)\) 为 "\(G\) 是连通图", 那么
\[\lim_{n\to\infty} \Pr[A(G_{n,p})] = e^{-e^{-c}}. \]
这在随机图的研究中一般称为一个阈值结果 (threshold result), 如果 \(p=o(\log n / n)\), 那么图几乎一定不是连通的 (概率趋于 \(0\)), 而如果 \(p = \omega(\log n / n)\), 那么图几乎一定是连通的!
令人意外的是, 证明这个结果的思路其实相当直接, 或者说, 证明它的途径是基于这样一个直觉:
对于 \(p=(\log n + c)/n\) 的随机图, 当 \(c\) 变大的时候, 基本上图已经是一个连通了所有点的连通块, 剩下的功夫只是通过提升概率将剩余的孤立点加到连通块中.
一个图不连通, 当且仅当它没有大小 \(\leq n/2\) 的连通块. 我们记事件 \(A_k\) 是 "\(G_{n, p}\) 里存在大小为 \(k\) 的连通块", 那么根据 union bound, 就有
\[\Pr[A_1] \leq \Pr[A(G_{n,p})] \leq \sum_{k=1}^{n/2} \Pr[A_k]. \]我们接下来要分别控制 \(\Pr[A_1]\) 和 \(\sum_{k=2}^{n/2} \Pr[A_k]\).
控制 \(\sum_{k=2}^{n/2} \Pr[A_k]\)
这一部分通过一阶矩方法 (也即 Markov 不等式) 就能够得到我们需要的结果.
对于一个大小为 \(k\) 的连通块, 它至少有一颗生成树. 所以我们可以用大小为 \(k\) 的支撑子树的数量来控制存在大小为 \(k\) 的连通块的概率:
\[\Pr[A_k] \leq \binom{n}{k} k^{k-2} p^{k-1}(1-p)^{k(n-k)}. \]首先 \(\binom{n}{k}\) 是选这个连通块占据的位置, \(k^{k-2}\) 是 Cayley 公式, 也即 \(k\) 个点的完全图的生成树的数量, 我们只要求所选的这 \(k-1\) 条边是存在的, 并且这个集合和外部集合之间的边都是不存在的, 分别对应于 \(p^{k-1},(1-p)^{k(n-k)}\).
对于小的 \(k\) 和更大的 \(k\) 我们分别控制, 对于 \(k< 10\), 我们分别证明每一项是 \(o(1)\) 就可以了, 有:
\[\begin{align*} &\quad \binom{n}{k} k^{k-2} p^{k-1}(1-p)^{k(n-k)}\\ &\sim Cn^k p^{k-1} (1-p)^{-nk}\\ &\sim Cn^k p^{k-1} \exp \{ -nkp \}\\ &= C n^k p^{k-1} \exp \{ -k(\log n + c_n) \}\\ &\sim Cp^{k-1} \\ &= O\left(\left(\frac{\log n}{n}\right)^k\right). \end{align*}\]对于 \(10 \leq k\leq n/2\), 我们用到的不等式有:
- \(\binom n k \leq n^k / k!\).
- \(\frac 1{k!} \leq (\frac{e}{k})^k\), 这可以通过对 \(\frac 1{k!} \leq \sum_{j\geq 0} \frac{x^{j-k}}{j!} = x^{-k}e^x\) 带入 \(x=k\) 得到.
- \(n-k \geq n/2\).
- \(1-p \leq e^{-p}\).
都加进去, 我们得到了
\[\begin{align*} &\leq \left(\frac{ne}{k}\right)^k k^{k-2} p^{k-1} \exp \left\{-\frac{nkp}2 \right\} \\ &= \frac 1{k^2p} \left( e n p \exp \left\{ -\frac{np}2 \right\}\right)^k \\ &\leq \frac 1 p \left(\frac{e(\log n + c)}{n^{1/2}}\right)^k, \end{align*}\]那么由于 \(\frac{e(\log n + c)}{n^{1/2}}\to 0\), 我们有
\[\begin{align*} &\quad \sum_{k=2}^{n/2} \Pr[A_k]\\ &\leq O\left(\frac{\log n} n\right) + \frac 1 p\sum_{k=10}^{n/2}\left(\frac{e(\log n + c)}{n^{1/2}}\right)^k\\ &= O\left(\frac{\log n} n\right) + (1+o(1))\frac{1}{p} \cdot \left(\frac{e(\log n + c)}{n^{1/2}}\right)^{10}\\ &= O\left(\frac{\log n} n\right) +(1+o(1)) n^{-4} \cdot O \left((\log n)^9\right)\\ &= O\left(\frac{\log n} n\right). \end{align*} \]控制 \(\Pr[A_1]\)
注意到, 图中的某一个点是孤立点的概率是 \((1 - p)^{n-1} \sim e^{-np} = e^{-c}/n\), 所以期望的孤立点数量应该趋近于 \(\lambda = e^{-c}\). 如果假装 \(n\) 个点的概率是独立的, 那么孤立点的数量 \(X\) 的分布应该收敛到 Poisson 分布 \(\Pr[X = k] = e^{-\lambda} \frac{\lambda^k}{k!}\). 当然实际上这是不独立的, 但由于每个点之间的关联很小, 这个结论仍然是成立的, 我们有标准的技术来处理这个问题.
首先让我们来计算任意阶矩 \(\mathbb E[\binom X k]\), 这相当于是任选 \(k\) 个点看看它们是不是孤立点, 因此有
\[\begin{align*} \mathbb E \left[\binom X k\right] &= \binom n k (1-p)^{\binom k 2 + k(n-k)}\\ &\sim \frac{n^k}{k!} (1-p)^{nk}\\ &\sim \frac{n^k}{k!} \exp \{ -nkp \}\\ &= \frac{e^{-ck}}{k!}\\ &= \frac{\lambda^k}{k!}. \end{align*}\]我们小学就学过了容斥原理 \(\Pr[X=0] = \mathbb E[\binom X 0]-\mathbb E[\binom X 1]+\mathbb E[\binom X 2] - \cdots\), 看起来如果能逐项取极限就和我们想要的结论一致了, 当然实际上我们还得稍微克制一下.
考虑求和
\[\sum_{j=0}^k (-1)^j \binom X j = (-1)^k\binom{X-1}{k}, \]当 \(X=0\) 时右式总是 \(1\), 否则有 \(\binom{X-1}{k} \geq 0\), 所以
\[ \begin{align*} \sum_{j=0}^{2k} (-1)^j \mathbb E \left[ \binom X j \right] &\geq \Pr[X = 0], \\ \sum_{j=0}^{2k+1} (-1)^j \mathbb E \left[ \binom X j \right] &\leq \Pr[X = 0]. \end{align*} \]这也就是称作所谓的 Bonferroni 不等式.
那么如果固定了 \(k\), 我们对两边取极限, 就有
\[ \begin{align*} \sum_{j=0}^{2k} (-1)^j \frac{\lambda^j}{j!} &\geq \limsup_{n\to \infty} \Pr[X = 0], \\ \sum_{j=0}^{2k+1} (-1)^j \frac{\lambda^j}{j!} &\leq \liminf_{n\to \infty} \Pr[X = 0] . \end{align*} \]因此再对 \(k\) 取极限, 我们就有
\[\lim_{n\to \infty} \Pr[X = 0] = \sum_{j=0}^\infty (-1)^j \frac{\lambda^j}{j!} = e^{-\lambda}. \]这也就得到了
\[\Pr[A(G_{n,p})] \to e^{-e^{-c}}. \]上面的容斥手法在 The Probabilistic Method 一书中称为 Brun 筛法. 更一般地, 它还可以进一步得到 \(\Pr[X=k] \to e^{-\lambda} \lambda^k/k!\), 也就是说 \(X\) 确实趋近于 Poisson 分布. 所以更精细地说, 我们有如下结果:
\(G_{n,p}\) 趋近于有 \(e^{-e^{-c}-ck}/k!\) 的概率形如 "\(k\) 个孤立点, 剩下的点连通".
更一般地说, 对于满足一定条件的随机变量 \(X\), 我们只要确定了任意阶矩 \(\mathbb E[X_n^k] \to \mathbb E[X^k]\), 就能够得到分布的收敛性. 有些时候这是比控制特征函数要容易的.
标签：Pr,right,frac,Erd,leq,nyi,连通性,binom,left From： https://www.cnblogs.com/Elegia/p/17354474.html