Markov Inequality: if X is a a positive random variable with small mean, it is unlikely to be very large

Let X be a random variable such that X >= 0.
$ \textrm{Pr}(X \geq a) \leq \frac{\textrm{E}(X)}{a}. $

Proof (discrete case):

$ \textrm{Pr}(X \geq a) = {\sum_{x \geq a} P_x(x)} $

$ {\sum_{x \geq a} P_x(x)} \leq {\sum_{x \geq a} P_x(x) \cdot \frac{x}{a}} $

$ {\sum_{x \geq a} P_x(x) \cdot \frac{x}{a}} = \frac{1}{a} {\sum_{x \geq a} x\cdot P_x(x)} $

$ \frac{1}{a} {\sum_{x \geq a} x\cdot P_x(x)} \leq \frac{1}{a} {\sum_{x} x\cdot P_x(x)} $

$ \frac{1}{a} {\sum_{x} x\cdot P_x(x)} = \frac{\textrm{E}(X)}{a} $


Chebyshev inequality: Any RV is likely to be close to its mean
for any c >0, any x:

$ \textrm{Pr}(|x - \textrm{E}(X)| \geq c) \leq \frac{\operatorname{Var}(X)}{c^2}. $

This can be proved by letting $ Y = (x - \textrm{E}(X))^2 $ and using the markov inequality.


Back to ECE302 Fall 2008 Prof. Sanghavi

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett