Exercise C.3.6

$\star$ Let $X$ be a nonnegative random variable, and suppose that $E[Y]$ is well defined. Prove Markov's inequality:

$$ \Pr\{X \ge t\} \le \E[X]/t $$

for all $t > 0$.

$$ \begin{aligned} \E[X] &= \sum_{x}x \cdot \Pr\{X \ge t\} \\ &= \sum_{x < t}x \cdot \Pr\{X = x\} + \sum_{x \ge t} x \cdot \Pr\{X = x\} \\ & \ge \sum_{x < t}x \cdot \Pr\{X = x\} + \sum_{x \ge t} t \cdot \Pr\{X = x\} \\ & \ge t \sum_{x \ge t} \Pr\{X = x\} \\ &= t \cdot \Pr\{X \ge t\} \end{aligned} $$

Chaning $x$ with $t$ in one of the sum works, since that is the sum where $x \ge t$.

Thus follows:

$$ \E[X] \ge t \cdot \Pr\{X \ge t\} \\ \Downarrow \\ \Pr\{X \ge t\} \le \E[X]/t $$