二阶矩，方差，切比雪夫不等式
我们可以验证如果两个随机变量\(X,Y\)是独立的，那么一定满足\(E[X\cdot Y]=E[X] \cdot E[Y]\)。只需根据定义把右侧表示出来，\(E[X] \cdot E[Y]\)\(=\left(\sum\limits_{x}x\Pr[X=x]\right)\left(\sum\limits_{y}y\Pr[Y=y]\right)\)\(=\sum\limits_{x}\sum\limits_{y}xy\Pr[X=x]\Pr[Y=y]\)，根据独立的定义\(\Pr[X=x]\cdot \Pr[Y=y]=\Pr[X=x \and Y=y]\)，因此写出\(\sum\limits_{x}\sum\limits_{y}xy\Pr[X=x \and Y=y]\)，我们转而枚举\(x\cdot y\)，对于每个确定的\(x\cdot y\)，我们需要把所有\(\Pr[X=x \and Y=y]\)累加起来，而这得到的就是\(\Pr[X\cdot Y=x\cdot y]\)（充分必要），这样就写出\(\sum\limits_{k}k\Pr[X\cdot Y=k]\)，这就是\(E[X \cdot Y]\)的定义本身了。证毕。而当它们不独立时，容易举出反例说明这是不满足的。
对于任意的随机变量\(X\)，就称\(E[X^2]\)为\(X\)的二阶矩。注意到\(E[X^2]\neq (E[X])^2\)，例如在\(\{1,99\}\)里选一个数，这构成随机变量\(X\)。而\(E[X^2]=\sum\limits_{i=1}^{99}i^2 \Pr(X=i)\)\(=\dfrac{\sum\limits_{i=1}^{99}i^2}{99}=\dfrac{9950}{3}\)。而\((E[X])^2=\left(\sum\limits_{i=1}^{99}\dfrac{i}{99}\right)^2=2500\)。
于是我们定义\(X\)的方差\(Var[X]=E[X^2]-(E[X])^2\)。即方差等于二阶矩减去期望的平方。根据期望的线性性，我们可以验证\(Var[X]=E[(X-E[X])^2]\)与此等价，因为\(E[X^2+(E[X])^2-2XE[X]]=E[X^2]+(E[X])^2-2E[X]E[X]\)\(=E[X^2]-(E[X])^2\)。通过后者，我们容易看到方差反应的是随机变量与期望的偏离程度。比如当随机变量恒为\(E[X]\)时，方差为0。而如果随机变量有比较大的波动，则\(Var[X]\)也会较大。
我们可以直接验证\(Var[X+Y]=E[(X+Y)^2]-(E[X+Y])^2\)，根据期望的线性性展开可得\(Var[X+Y]=E[X^2]+E[Y^2]+2E[X\cdot Y]-E[X]^2-\)\(E[Y]^2\)\(-2E[X]E[Y]\)\(=Var[X]+Var[Y]+2E[X \cdot Y]-2E[X]E[Y]\)。所以我们看到，只有当\(X,Y\)独立时我们消去后面的项得到\(Var[X+Y]=Var[X]+Var[Y]\)。这说明当随机变量独立时方差也具有线性性。
现在，我们希望能够定量地描述“方差反应波动性”这一事实。这就是著名的切比雪夫不等式，它指出\(\forall a>0\)，\(\Pr[|X-E[X]| \geq a] \leq \dfrac{Var[X]}{a^2}\)。对于任意fix的一个\(a\)，方差越大随机变量偏离\(E[X]\)超过\(a\)的概率越大。而它其实本质上只是Markov不等式——我们可以直接根据Markov不等式得到\(\Pr[|X-E[X]|\geq a]\)\(=\Pr[(X-E[X])^2\geq a^2]\leq \dfrac{E[(X-E[X])^2]}{a^2}=\dfrac{Var[X]}{a^2}\)。
考虑值域为\([0,n]\)中的整数的一个随机变量\(X\)。如果要证明\(n \to +\infty\)时\(\Pr[X=0]\to 1\)，只需证明\(\Pr[X\geq 1] \to 0\)，根据Markov不等式只需证明\(E[X] \to 0\)。但这个方法却不能倒过来使用，如果\(E[X] \to +\infty\)，不能保证\(\Pr[X \geq 1] \to 1\)，所以也无法推出\(\Pr[X=0] \to 0\)。此时可以用切比雪夫不等式，\(\Pr[X=0] \leq \Pr[|X-E[X| \geq E[X]]\leq \dfrac{Var[X]}{(E[X])^2}\)\(=\dfrac{E[X^2]-(E[X])^2}{(E[X])^2}\)，因此只需证明\(\lim E[X^2]=\lim (E[X])^2\)即可。这样我们就找到了一个证明方法了。
随机图上的相变
我们已经知道给定顶点个数\(n\)和一个实数\(p \in [0,1]\)就可以随机生成一张图。现在我们假设\(p\)是由顶点个数决定的一个函数\(p(n)\)。这样生成的随机图记为\(G(n,p(n))\)。如果存在一个关于\(n\)的函数\(r(n)\)满足，当\(p(n) \ll r(n)\)时图的“某个性质”成立的概率在\(n \to +\infty\)时趋向0，而当\(p(n) \gg r(n)\)时图的这个性质成立的概率在\(n \to +\infty\)时趋向1，那么就说图的这个性质是“具有相变性”的。其中\(r(n)\)就被称为图的这个性质的阈值函数。
下面我们来证明，“包含一个大小为4的完全图”这一性质是有相变性的。
设随机变量\(X\)表示\(K_4\)的数量，那么性质成立对应事件\(X \geq 1\)。根据Markov不等式\(\Pr[X \geq 1]\leq E[X]\)。根据期望的线性性，我们枚举所有的大小为\(4\)的点集累加它们是完全图的概率，得到\(E[X]=\dbinom{n}{4}\cdot p^{\binom{4}{2}}=\dfrac{n!}{4!(n-4)!}p^6 \leq n(n-1)(n-2)(n-3)p^6 \leq n^4p^6\)。当\(n \to +\infty\)时，为了使它趋向0，可以取\(r(n)=n^{-\frac{2}{3}}\)。
接下来我们来验证\(r(n)=n^{-\frac{2}{3}}\)也能满足\(p(n) \gg r(n)\)的情况。根据切比雪夫不等式，\(\Pr[X=0] \leq \Pr[|X-E[X| \geq E[X]]\leq \dfrac{Var[X]}{(E[X])^2}=\dfrac{E[X^2]-(E[X])^2}{(E[X])^2}\)。