(New page: 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. <br> <math>\textrm{Pr}(X \geq a) \leq...) |
|||
| Line 1: | Line 1: | ||
| + | [[Category:ECE302Fall2008_ProfSanghavi]] | ||
| + | [[Category:probabilities]] | ||
| + | [[Category:ECE302]] | ||
| + | |||
Markov Inequality: | Markov Inequality: | ||
if X is a a positive random variable with small mean, it is unlikely to be very large | if X is a a positive random variable with small mean, it is unlikely to be very large | ||
| Line 20: | Line 24: | ||
<math>\textrm{Pr}(|x - \textrm{E}(X)| \geq c) \leq \frac{\operatorname{Var}(X)}{c^2}.</math><br><br> | <math>\textrm{Pr}(|x - \textrm{E}(X)| \geq c) \leq \frac{\operatorname{Var}(X)}{c^2}.</math><br><br> | ||
This can be proved by letting <math>Y = (x - \textrm{E}(X))^2</math> and using the markov inequality. | This can be proved by letting <math>Y = (x - \textrm{E}(X))^2</math> and using the markov inequality. | ||
| + | ---- | ||
| + | [[Main_Page_ECE302Fall2008sanghavi|Back to ECE302 Fall 2008 Prof. Sanghavi]] | ||
Latest revision as of 12:59, 22 November 2011
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.
