Toolbox

T1: Some Inequalities on Random Graphs

Reminder: This post contains 320 words · 1 min read · by Xianbin

Lemma 1\textbf{Lemma 1} (Second Moment Method). If XX is a non-negative integer random variable, then we have

P(X=0)≤VarX(EX)2=E[X2](EX)2−1P(X=0) \leq \frac{\text{Var} X}{(EX)^2} = \frac{E[X^2]}{(EX)^2}-1

Lemma 2\textbf{Lemma 2} (Strong Second Moment Method). If XX is a non-negative integer random variable, then we have

P(X=0)≤VarXEX2=1−(EX)2E[X2]P(X=0) \leq \frac{\text{Var} X}{EX^2} = 1-\frac{(EX)^2}{E[X^2]}