Lesson 3

Theorem (Markov). For a non-negative random variable \(\alpha\) and any constant \(c > 0\), the following inequality holds: \[\Pr[\alpha \ge c] \le \frac{\operatorname{E}[\alpha]}{c} .\]

Proof. \[\begin{align*}\operatorname{E}[\alpha]&=\sum_{a}a\Pr[\alpha=a] = \\&= \sum_{a < c}a\Pr[\alpha=a] + \sum_{a \ge c}a\Pr[\alpha=a] \ge&\text{(\(\alpha \ge 0\))}\\&\ge \sum_{a \ge c}a\Pr[\alpha=a] \ge \\&\ge \sum_{a \ge c}c\Pr[\alpha=a]=\\&=c\sum_{a \ge c}\Pr[\alpha=a]=\\&=c\Pr[\alpha \ge c]  .\end{align*}\]◼