概率论与数理统计 (Spring 2023)/Threshold of k-clique in random graph: Difference between revisions
(22 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
在 Erdős-Rényi 随机图模型 <math>G(n,p)</math> 中,一个随机无向图 <math>G</math> 以如下的方式生成:图 <math>G</math> 包含 <math>n</math> 个顶点,每一对顶点之间都独立同地以概率 <math>p</math> 连一条无向边。如此生成的随机图记为 <math>G\sim G(n,p)</math>。 | |||
固定整数 <math>k\ge 3</math>,考虑随机图 <math>G\sim G(n,p)</math> 包含 <math>K_k</math>(<math>k</math>-团,<math>k</math>-clique)子图概率。 | 固定整数 <math>k\ge 3</math>,考虑随机图 <math>G\sim G(n,p)</math> 包含 <math>K_k</math>(<math>k</math>-团,<math>k</math>-clique)子图概率。 | ||
Line 38: | Line 38: | ||
于是,容易验证有: | 于是,容易验证有: | ||
:<math>\mathbb{E}[X]=\Theta\left(n^kp^{k(k-1)/2}\right)=\begin{cases} | :<math>\mathbb{E}[X]=\Theta\left(n^kp^{k(k-1)/2}\right)=\begin{cases} | ||
o(1) & \text{如果} p=o(p_k(n))\\ | o(1) & \text{如果 } p=o(p_k(n))=o\left(n^{-2/(k-1)}\right)\\ | ||
\omega(1) & \text{如果} p=\omega(p_k(n)) | \omega(1) & \text{如果 } p=\omega(p_k(n))=\omega\left(n^{-2/(k-1)}\right) | ||
\end{cases}</math> | \end{cases}</math> | ||
特别地,当 <math>p=o(p_k(n))</math> 时,<math>\mathbb{E}[X]=o(1)</math>。根据马尔可夫不等式: | 特别地,当 <math>p=o(p_k(n))=o\left(n^{-2/(k-1)}\right)</math> 时,<math>\mathbb{E}[X]=o(1)</math>。根据马尔可夫不等式: | ||
:<math> | :<math> | ||
\Pr\left(G\text{ 包含子图 }K_k\right)=\Pr(X\ge 1)\le \mathbb{E}[X]=o(1). | \Pr\left(G\text{ 包含子图 }K_k\right)=\Pr(X\ge 1)\le \mathbb{E}[X]=o(1). | ||
</math> | </math> | ||
因此,<math>({\color{red}\star})</math> 中的概率上界已得到证明。 | 因此,<math>({\color{red}\star})</math> 中的概率上界已得到证明。 | ||
事实上,这一结果可以更加直接地使用 union bound 证明: | |||
:<math> | |||
\Pr\left(G\text{ 包含子图 }K_k\right)=\mbox{$\Pr\left(\bigcup_{S\in{[n]\choose k}}(K_S\subseteq G)\right)$}\le {n\choose k}p^{{k\choose 2}}=o(1)\qquad\left(\text{如果 $p=o(p_k(n))$}\right) | |||
</math> | |||
尽管如此,对于一阶矩的分析,有助于我们猜测出正确的阈值 <math>p_k(n)</math>,而且对于更高阶矩的估计也是必要的。 | |||
=二阶矩方法= | =二阶矩方法= | ||
Line 71: | Line 78: | ||
\sum_{S\in{[n]\choose k}}\mathbb{E}[I_S^2] + \sum_{\substack{S,T\in{[n]\choose k}\\S\neq T}}\mathbb{E}[I_SI_T] | \sum_{S\in{[n]\choose k}}\mathbb{E}[I_S^2] + \sum_{\substack{S,T\in{[n]\choose k}\\S\neq T}}\mathbb{E}[I_SI_T] | ||
</math> | </math> | ||
我们将分别计算这两项。首先,由于随机变量 <math>I_S</math> 取值为0或1,因此 <math>I_S^2=I_S</math>,于是有: | |||
:<math> | :<math> | ||
\begin{align} | \begin{align} | ||
Line 79: | Line 86: | ||
= | = | ||
\mathbb{E}[X] | \mathbb{E}[X] | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
另一方面,<math>I_SI_T=1</math> 当且仅当 <math>S</math> 和 <math>T</math> 在随机图 <math>G</math> 中都是 <math>k</math>-团,于是: | |||
:<math> | :<math> | ||
\begin{align} | \begin{align} | ||
Line 92: | Line 97: | ||
\sum_{\ell=0}^{k-1}\sum_{|S\cap T|=\ell}p^{2{k\choose 2}-{\ell\choose 2}}\\ | \sum_{\ell=0}^{k-1}\sum_{|S\cap T|=\ell}p^{2{k\choose 2}-{\ell\choose 2}}\\ | ||
&\le | &\le | ||
\sum_{\ell=0}^{k-1}{n\choose 2k-\ell} {2k-\ell\choose k}{k\choose \ell} p^{2{k\choose 2}-{\ell\choose 2}} && \text{ | \sum_{\ell=0}^{k-1}{n\choose 2k-\ell} {2k-\ell\choose k}{k\choose \ell} p^{2{k\choose 2}-{\ell\choose 2}} && \left(\text{因为 }{2k-\ell\choose k}{k\choose \ell}\le 2^{2k}=O(1)\right)\\ | ||
&= | &= | ||
O\left(n^{2k}p^{2{k\choose 2}}\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right)\\ | O\left(n^{2k}p^{2{k\choose 2}}\cdot\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right)\\ | ||
&= | &= | ||
\mathbb{E}[X]^2\cdot O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right) && \text{ | \mathbb{E}[X]^2\cdot O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right). && \left(\text{因为 }\mathbb{E}[X]=\Theta\left(n^kp^{{k\choose 2}}\right)\right) | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
综上,我们有 <math>\mathbf{Var}[X]\le \mathbb{E}[X^2]\le \mathbb{E}[X]+\mathbb{E}[X]^2\cdot O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right)</math>,于是: | |||
:<math> | :<math> | ||
\begin{align} | \begin{align} | ||
Line 108: | Line 113: | ||
\frac{1}{\mathbb{E}[X]} + O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right)\\ | \frac{1}{\mathbb{E}[X]} + O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right)\\ | ||
&= | &= | ||
O\left(\sum_{\ell=2}^{k}n^{-\ell}p^{-{\ell\choose 2}} \right)\\ | O\left(\sum_{\ell=2}^{k}n^{-\ell}p^{-{\ell\choose 2}} \right) && \left(\text{因为 }\mathbb{E}[X]=\Theta\left(n^kp^{{k\choose 2}}\right)\right)\\ | ||
&=o(1) | &=o(1). && (\text{当 }p=\omega(p_k(n))) | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
正如我们之前分析的,根据切比雪夫不等式,这证明了当 <math>p=\omega(p_k(n))</math> | 正如我们之前分析的,根据切比雪夫不等式,这证明了当 <math>p=\omega(p_k(n))=\omega\left(n^{-2/(k-1)}\right)</math> 时,有 <math>\Pr(X=0)=o(1)</math>。和一阶矩方法的部分合起来,这证明了 <math>({\color{red}\star})</math>。 |
Latest revision as of 04:29, 19 April 2023
在 Erdős-Rényi 随机图模型 [math]\displaystyle{ G(n,p) }[/math] 中,一个随机无向图 [math]\displaystyle{ G }[/math] 以如下的方式生成:图 [math]\displaystyle{ G }[/math] 包含 [math]\displaystyle{ n }[/math] 个顶点,每一对顶点之间都独立同地以概率 [math]\displaystyle{ p }[/math] 连一条无向边。如此生成的随机图记为 [math]\displaystyle{ G\sim G(n,p) }[/math]。
固定整数 [math]\displaystyle{ k\ge 3 }[/math],考虑随机图 [math]\displaystyle{ G\sim G(n,p) }[/math] 包含 [math]\displaystyle{ K_k }[/math]([math]\displaystyle{ k }[/math]-团,[math]\displaystyle{ k }[/math]-clique)子图概率。
特别地,对于任意固定(即,常数)的整数 [math]\displaystyle{ k\ge 3 }[/math],我们将证明存在函数 [math]\displaystyle{ p_k(n) }[/math] 使得对所有足够大的 [math]\displaystyle{ n }[/math] 和随机图 [math]\displaystyle{ G\sim G(n,p) }[/math] 有
- [math]\displaystyle{ ({\color{red}\star})\qquad }[/math] [math]\displaystyle{ \begin{align} \Pr\left(G\text{ 包含子图 }K_k\right) =\begin{cases} o(1) & \text{如果} p=o(p_k(n))\\ 1-o(1) & \text{如果} p=\omega(p_k(n)) \end{cases} \end{align} }[/math]
这描述了“包含 [math]\displaystyle{ k }[/math]-团“这一性质,在随机图 [math]\displaystyle{ G(n,p) }[/math] 上,展现出的一种所谓的阈值现象:随着参数 [math]\displaystyle{ p }[/math] 从远小于 [math]\displaystyle{ p_k(n) }[/math] 增长到远大于 [math]\displaystyle{ p_k(n) }[/math],“包含 [math]\displaystyle{ k }[/math]-团“这一事件在随机图 [math]\displaystyle{ G(n,p) }[/math] 上从渐进几乎从不(asymptotically almost never)发生变为渐进几乎一定(a.a.s.)发生。
固定整数 [math]\displaystyle{ k\ge 3 }[/math],假设[math]\displaystyle{ k=O(1) }[/math]为常数。抽取随机图 [math]\displaystyle{ G\sim G(n,p) }[/math]。令随机变量 [math]\displaystyle{ X }[/math] 表示 [math]\displaystyle{ G }[/math] 中包含的 [math]\displaystyle{ k }[/math]-团的个数,因此有:
- [math]\displaystyle{ \Pr\left(G\text{ 包含子图 }K_k\right) = \Pr(X\ge 1) }[/math].
一阶矩方法
根据马尔可夫不等式:
- [math]\displaystyle{ \Pr(X\ge 1)\le\mathbb{E}[X] }[/math].
因此,通过计算 [math]\displaystyle{ X }[/math] 的期望(一阶矩),可得到概率 [math]\displaystyle{ \Pr\left(G\text{ 包含子图 }K_k\right) }[/math] 的上界。
对于顶点集合 [math]\displaystyle{ [n] }[/math] 的任意 [math]\displaystyle{ k }[/math]-子集 [math]\displaystyle{ S\in{[n]\choose k} }[/math],定义指示随机变量 [math]\displaystyle{ I_S=I(K_S\subseteq G) }[/math],即 [math]\displaystyle{ I_S=1 }[/math] 当且仅当点集 [math]\displaystyle{ S }[/math] 在随机图 [math]\displaystyle{ G }[/math] 中构成了一个 [math]\displaystyle{ k }[/math]-团。根据这个定义,有:
- [math]\displaystyle{ X=\sum_{S\in{[n]\choose k}}I_S }[/math]
- [math]\displaystyle{ \mathbb{E}[I_S]=\Pr(K_S\subseteq G)=p^{{k\choose 2}} }[/math]
于是根据期望的线性:
- [math]\displaystyle{ \mathbb{E}[X]=\sum_{S\in{[n]\choose k}}\mathbb{E}[I_S]={n\choose k}p^{{k\choose 2}} }[/math].
对于常数 [math]\displaystyle{ k=O(1) }[/math],当 [math]\displaystyle{ n }[/math] 足够大时,[math]\displaystyle{ {n\choose k}p^{{k\choose 2}}=\Theta\left(n^kp^{k(k-1)/2}\right) }[/math]。这提示我们将函数 [math]\displaystyle{ p_k(n) }[/math] 做如下定义:
- [math]\displaystyle{ p_k(n)=n^{-2/(k-1)} }[/math].
于是,容易验证有:
- [math]\displaystyle{ \mathbb{E}[X]=\Theta\left(n^kp^{k(k-1)/2}\right)=\begin{cases} o(1) & \text{如果 } p=o(p_k(n))=o\left(n^{-2/(k-1)}\right)\\ \omega(1) & \text{如果 } p=\omega(p_k(n))=\omega\left(n^{-2/(k-1)}\right) \end{cases} }[/math]
特别地,当 [math]\displaystyle{ p=o(p_k(n))=o\left(n^{-2/(k-1)}\right) }[/math] 时,[math]\displaystyle{ \mathbb{E}[X]=o(1) }[/math]。根据马尔可夫不等式:
- [math]\displaystyle{ \Pr\left(G\text{ 包含子图 }K_k\right)=\Pr(X\ge 1)\le \mathbb{E}[X]=o(1). }[/math]
因此,[math]\displaystyle{ ({\color{red}\star}) }[/math] 中的概率上界已得到证明。
事实上,这一结果可以更加直接地使用 union bound 证明:
- [math]\displaystyle{ \Pr\left(G\text{ 包含子图 }K_k\right)=\mbox{$\Pr\left(\bigcup_{S\in{[n]\choose k}}(K_S\subseteq G)\right)$}\le {n\choose k}p^{{k\choose 2}}=o(1)\qquad\left(\text{如果 $p=o(p_k(n))$}\right) }[/math]
尽管如此,对于一阶矩的分析,有助于我们猜测出正确的阈值 [math]\displaystyle{ p_k(n) }[/math],而且对于更高阶矩的估计也是必要的。
二阶矩方法
为了完全证明 [math]\displaystyle{ ({\color{red}\star}) }[/math],我们需要补全其中的概率下界,即在 [math]\displaystyle{ \mathbb{E}[X]=\omega(1) }[/math] 的情况下,证明
- [math]\displaystyle{ \Pr(X\ge 1)\ge 1-o(1) }[/math]
很遗憾,为实现这一目的,仅知道 [math]\displaystyle{ \mathbb{E}[X]=\omega(1) }[/math] 是不够的。我们还需要知道关于随机变量 [math]\displaystyle{ X }[/math] 更多的信息,比方说它的方差(二阶中心矩)。
根据切比雪夫不等式:
- [math]\displaystyle{ \Pr(X=0)\le \Pr(|X-\mathbb{E}[X]|\ge \mathbb{E}[X])\le \frac{\mathbf{Var}[X]}{\mathbb{E}[X]^2} }[/math]
于是,上述目标归结为证明方差和期望之间有如下渐进关系: [math]\displaystyle{ \mathbf{Var}[X]=o\left(\mathbb{E}[X]^2\right) }[/math]。实际上我们证明了更强的性质
- [math]\displaystyle{ \mathbb{E}[X^2]=o\left(\mathbb{E}[X]^2\right) }[/math].
这足以推出 [math]\displaystyle{ \mathbf{Var}[X]=\mathbb{E}[X^2]-\mathbb{E}[X]^2\le \mathbb{E}[X^2]=o\left(\mathbb{E}[X]^2\right) }[/math]。
还记得 [math]\displaystyle{ X=\sum_{S\in{[n]\choose k}}I_S }[/math],于是有:
- [math]\displaystyle{ \mathbb{E}\left[X^2\right] = \mathbb{E}\left[\left(\sum_{S\in{[n]\choose k}}I_S\right)^2\right] = \sum_{S\in{[n]\choose k}}\mathbb{E}[I_S^2] + \sum_{\substack{S,T\in{[n]\choose k}\\S\neq T}}\mathbb{E}[I_SI_T] }[/math]
我们将分别计算这两项。首先,由于随机变量 [math]\displaystyle{ I_S }[/math] 取值为0或1,因此 [math]\displaystyle{ I_S^2=I_S }[/math],于是有:
- [math]\displaystyle{ \begin{align} \sum_{S\in{[n]\choose k}}\mathbb{E}[I_S^2] = \sum_{S\in{[n]\choose k}}\mathbb{E}[I_S] = \mathbb{E}[X] \end{align} }[/math]
另一方面,[math]\displaystyle{ I_SI_T=1 }[/math] 当且仅当 [math]\displaystyle{ S }[/math] 和 [math]\displaystyle{ T }[/math] 在随机图 [math]\displaystyle{ G }[/math] 中都是 [math]\displaystyle{ k }[/math]-团,于是:
- [math]\displaystyle{ \begin{align} \sum_{\substack{S,T\in{[n]\choose k}\\S\neq T}}\mathbb{E}[I_SI_T] &= \sum_{\substack{S,T\in{[n]\choose k}\\S\neq T}}\Pr((K_S\cup K_T)\subseteq G)\\ &= \sum_{\ell=0}^{k-1}\sum_{|S\cap T|=\ell}p^{2{k\choose 2}-{\ell\choose 2}}\\ &\le \sum_{\ell=0}^{k-1}{n\choose 2k-\ell} {2k-\ell\choose k}{k\choose \ell} p^{2{k\choose 2}-{\ell\choose 2}} && \left(\text{因为 }{2k-\ell\choose k}{k\choose \ell}\le 2^{2k}=O(1)\right)\\ &= O\left(n^{2k}p^{2{k\choose 2}}\cdot\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right)\\ &= \mathbb{E}[X]^2\cdot O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right). && \left(\text{因为 }\mathbb{E}[X]=\Theta\left(n^kp^{{k\choose 2}}\right)\right) \end{align} }[/math]
综上,我们有 [math]\displaystyle{ \mathbf{Var}[X]\le \mathbb{E}[X^2]\le \mathbb{E}[X]+\mathbb{E}[X]^2\cdot O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right) }[/math],于是:
- [math]\displaystyle{ \begin{align} \frac{\mathbf{Var}[X]}{\mathbb{E}[X]^2} &\le \frac{\mathbb{E}[X^2]}{\mathbb{E}[X]^2}\\ &\le \frac{1}{\mathbb{E}[X]} + O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right)\\ &= O\left(\sum_{\ell=2}^{k}n^{-\ell}p^{-{\ell\choose 2}} \right) && \left(\text{因为 }\mathbb{E}[X]=\Theta\left(n^kp^{{k\choose 2}}\right)\right)\\ &=o(1). && (\text{当 }p=\omega(p_k(n))) \end{align} }[/math]
正如我们之前分析的,根据切比雪夫不等式,这证明了当 [math]\displaystyle{ p=\omega(p_k(n))=\omega\left(n^{-2/(k-1)}\right) }[/math] 时,有 [math]\displaystyle{ \Pr(X=0)=o(1) }[/math]。和一阶矩方法的部分合起来,这证明了 [math]\displaystyle{ ({\color{red}\star}) }[/math]。