Lesson 6

Stronger estimates from Markov's theorem can be obtained if it is known that the considered random variable \(\alpha\) is always at least \(l\). For this, consider the random variable \(\beta=\alpha-l\). It will be non-negative, and \(\operatorname{E}[\beta]=\operatorname{E}[\alpha]-l\). Then, for \(c>l\), \[\Pr[\alpha \ge c]=\Pr[\beta+l \ge c]=\Pr[\beta \ge c-l] \le \frac{\operatorname{E}[\alpha]-l}{c-l} .\]