Markov's Inequality

March 24, 2023 - Markov's Inequality is a fundamental theorem in probability theory that provides an upper bound on the probability of a random variable taking on a specific value.

Theorem: Markov's Inequality

The inequality states that for any non-negative random variable X and any positive number a, the probability that X is greater than or equal to a is bounded by the expectation of X divided by a:

$$p(X \geq a) \leq \frac{E[X]}{a}$$

Proof of Markov's Inequality (Discrete Case):

$$E[X] = \sum_{x \in X} x \cdot p(x)$$ $$= \sum_{x < a} x \cdot p(x) + \sum_{x \geq a} x \cdot p(x)$$ As X is non-negative, we know that all values in the sum are positive and the following inequality holds: $$\sum_{x < a} x \cdot p(x) + \sum_{x \geq a} x \cdot p(x) \geq \sum_{x \geq a} x \cdot p(x)$$ As x is always larger or equal to a, it holds: $$\sum_{x \geq a} x \cdot p(x) \geq \sum_{x \geq a} a \cdot p(x)$$ $$ = a \cdot p(X \geq a)$$ So we got: $$E[X] \geq a \cdot p(X \geq a)$$ $$ \Leftrightarrow p(X \geq a) \leq \frac{E[X]}{a} $$