UA MATH567 高维统计I 概率不等式2 在Erdős–Rényi随机图模型中的应用_erd枚s-r茅nyi

Erdős–Rényi随机图模型是第一个系统性讨论随机图的模型，它讨论了两类模型，$G(n,M)$和$G(n,p)$，前者表示一个有$n$个点的图要随机选出$M$条边；后者表示一个有$n$个点的图每条边存在的概率是$p$。给定每条边存在的概率为$p$，每种$G(n,M)$的概率都是
$$p^M(1-p{)}^{C_n^2-M}$$

称与某一个点相连的边的数目为这个点的度，$G(n,p)$中每个点的度的期望记为$d$，则
$$d=(n-1)p$$

基于Chernoff不等式，我们可以证明$G(n,p)$具有下面的性质：

稠密图几乎正则，这句话非常不严谨，我们用数学语言精确描述一下。$\exists C>0$, 当$d\ge C\log n$时，$G(n,p)$每个点的度有很大概率位于$0.9d-1.1d$之间。具体有多大概率是可以用Chernoff Bound来近似的，下面我们简单推导一下。

引理1 小偏差下的Chernoff不等式
$$P(|S_N-\mu |\ge \delta \mu )\le 2e^{-c\mu {\delta }^2}$$

其中$S_N={\sum }_{i=1}^N{X}_i,E{S}_N=\mu$.

考虑顶点$i$，记它的度为$d_i$，记$X_{j(i)}$表示第$j$个点是否与顶点$i$相连， j ∈ I ( i ) = { 1 , ⋯   , i − 1 , i + 1 , n } j \in I(i) = \{1,\cdots,i-1,i+1,n\} j∈I(i)={ 1,⋯,i−1,i+1,n}，$X_j{\sim }_{iid}Ber(p)$，则
$$d_i=\sum _{j\in I(i)}{X}_{j(i)},E{d}_i$$