Markov's Inequality

Let \(X\) be a non-negative random variable. Then, \[P(X \geq c) \leq \frac{\mathbb{E}[X]}{c}\]

The expectation is the sum of the outcomes, weighted by the probabilities. Markov's inequality is a simple statement about the contributions that each outcome makes to the expectation. Let's say that \(\frac{\mathbb{E}[X]}{c}\) of the probability mass is on values that are greater than \(c\). Then, the contribution of these values to the expectation is at least \(c\cdot\frac{\mathbb{E}[X]}{c} = \mathbb{E}[X]\). If we tried to add any more probability mass to these values, then we would exceed our expectation.

\[\begin{align*} \mathbb{E}[X] &= \sum_{x\in X, x < c} x\cdot p(x) + \sum_{x\in X, x \geq c}x \cdot p(x)\\ & \geq 0 + c\sum_{x\in X, x \geq c} p(x)\\ & \geq c\cdot p(X\geq x) \end{align*}\] The second line comes from the fact that \(X\geq 0\).