Lesson 2

Theorem (Chebyshev). For any random variable \(\alpha\) with finite variance and any constant \(c>0\), the following holds: \[\Pr[|\alpha-\operatorname{E}[\alpha]| \ge c] \le \frac{\operatorname{Var}[\alpha]}{c^2}\ .\]

Proof. Consider the non-negative random variable \(\beta=(\alpha-\operatorname{E}[\alpha])^{2}\). Applying Markov's inequality to it: \[\Pr[|\alpha-\operatorname{E}[\alpha]| \ge c] = \Pr[\beta \ge c^{2}] \le \frac{\operatorname{E}[\beta]}{c^2}=\frac{\operatorname{Var}[\alpha]}{c^2}\ .\]◼