Lesson 4

A commonly used corollary of Markov's inequality states that for any \(t \ge 1\), the probability that a non-negative random variable is at least \(t\) times its mean is at most \(1/t\). Formally, for any non-negative random variable \(\alpha\) with \(\operatorname{E}[\alpha]>0\) and any number \(t \ge 1\), the following holds: \[\Pr[\alpha \ge t \cdot \operatorname{E}[\alpha]] \le \frac{1}{t}  .\]