View source for 10/27 Lecture: Merkov and Chebyshev Inequalities ECE302Fall2008sanghavi - Rhea

[[Category:ECE302Fall2008_ProfSanghavi]]
[[Category:probabilities]]
[[Category:ECE302]]

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 \frac{\textrm{E}(X)}{a}.</math>

Proof (discrete case):

<math>\textrm{Pr}(X \geq a) = {\sum_{x \geq a} P_x(x)} </math><br><br>
<math> {\sum_{x \geq a} P_x(x)} \leq  {\sum_{x \geq a} P_x(x) \cdot \frac{x}{a}}</math><br><br>
<math> {\sum_{x \geq a} P_x(x) \cdot \frac{x}{a}} = \frac{1}{a} {\sum_{x \geq a} x\cdot P_x(x)}</math><br><br>
<math> \frac{1}{a} {\sum_{x \geq a} x\cdot P_x(x)} \leq \frac{1}{a} {\sum_{x} x\cdot P_x(x)}</math><br><br>
<math> \frac{1}{a} {\sum_{x} x\cdot P_x(x)} = \frac{\textrm{E}(X)}{a}</math>


Chebyshev inequality:
Any RV is likely to be close to its mean<br>
for any c >0, any x:<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.
----
[[Main_Page_ECE302Fall2008sanghavi|Back to ECE302 Fall 2008 Prof. Sanghavi]]