Line 19: | Line 19: | ||
= Problem 2 = | = Problem 2 = | ||
− | Problem | + | Problem: State and prove the Chebyshev inequality for random variable with mean μ and variance σ<sup>2</sup>. In constructing your proof, keep in mind that may be either a discrete or continuous random variable. |
+ | |||
+ | |||
+ | |||
+ | Problem premise: Let <span class="texhtml">''X''</span> be a continuous or discrete random variable with mean <span class="texhtml">μ</span> and variance <span class="texhtml">σ<sup>2</sup></span>. Then, <math>\forall \varepsilon >0</math>, we have<br> <math> P(|X-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2}</math><br> | ||
===== <math>\color{blue}\text{Solution 1:}</math><br> ===== | ===== <math>\color{blue}\text{Solution 1:}</math><br> ===== | ||
Line 25: | Line 29: | ||
*Continuous Case:<br> | *Continuous Case:<br> | ||
− | Let X be | + | Let X be a random variable with mean <span class="texhtml">μ</span> and variance <span class="texhtml">σ<sup>2</sup></span> |
− | Consider two functions <span class="texhtml">''g''<sub>''1''</sub>(''x'')</span> and <span class="texhtml">''g''<sub>''2''</sub>(''x'')</span> | + | Consider two functions <span class="texhtml">''g''<sub>''1''</sub>(''x'')</span> and <span class="texhtml">''g''<sub>''2''</sub>(''x'')</span> |
− | <math>g_{1}(x)= 1_{\{x: \mid x-\mu\mid \geq \varepsilon\}}(x)</math> | + | <math>g_{1}(x)= 1_{\{x: \mid x-\mu\mid \geq \varepsilon\}}(x)</math> |
− | <math>g_{2}(x)=\frac{(x-\mu)^2}{\varepsilon^2}</math> | + | <math>g_{2}(x)=\frac{(x-\mu)^2}{\varepsilon^2}</math> |
− | Clearly, | + | Clearly, |
− | <math>g_{2}(x)-g_{1}(x) \geq 0\; \; \forall x \in \mathbb {R}</math> | + | <math>g_{2}(x)-g_{1}(x) \geq 0\; \; \forall x \in \mathbb {R}</math> |
− | <math>E[g_{2}(x)-g_{1}(x) ] \geq 0 \; \; \forall x \in \mathbb {R}</math> | + | <math>E[g_{2}(x)-g_{1}(x) ] \geq 0 \; \; \forall x \in \mathbb {R}</math> |
Consider, | Consider, | ||
− | < | + | <span class="texhtml">''E''[''g''<sub>2</sub>(''x'') − ''g''<sub>1</sub>(''x'')] = ''E''[''g''<sub>2</sub>(''x'')] − ''E''[''g''<sub>1</sub>(''x'')]</span> |
− | where, | + | where, <math>E[g_{2}(x)]=E[\frac{(x-\mu)^2}{\varepsilon^2}] = \frac{1}{\varepsilon^2} var(X) = \frac{\sigma^2}{\varepsilon^2}</math> |
− | <math>E[g_{2}(x)]=E[\frac{(x-\mu)^2}{\varepsilon^2}] = \frac{1}{\varepsilon^2} var(X) = \frac{\sigma^2}{\varepsilon^2}</math> | + | |
and | and | ||
− | <math>E[g_{1}(x)] = P \{\mid x - \mu\mid \geq \varepsilon \}</math> | + | <math>E[g_{1}(x)] = P \{\mid x - \mu\mid \geq \varepsilon \}</math> |
− | Thus we get, | + | Thus we get, |
− | <math>\frac{\sigma^2}{\varepsilon^2} - P\{\mid X - \mu \mid \geq \varepsilon\} \geq 0</math> | + | <math>\frac{\sigma^2}{\varepsilon^2} - P\{\mid X - \mu \mid \geq \varepsilon\} \geq 0</math> |
− | Therefore, | + | Therefore, |
− | <math>P\{\mid X - \mu \mid \geq \varepsilon\} \leq \frac{\sigma^2}{\varepsilon^2}</math> | + | <math>P\{\mid X - \mu \mid \geq \varepsilon\} \leq \frac{\sigma^2}{\varepsilon^2}</math> |
+ | <br> | ||
*Discrete Case:<br> | *Discrete Case:<br> | ||
− | The inequalities described above hold even if the x-axis is discretized. That is, if the random variable X is discrete. In other words, the discrete case is a proper subset of the continuous case in this problem. Thus, the Chebyshev inequality holds for discrete random variables. | + | The inequalities described above hold even if the x-axis is discretized. That is, if the random variable X is discrete. In other words, the discrete case is a proper subset of the continuous case in this problem. Thus, the Chebyshev inequality holds for discrete random variables. |
− | <font face="serif"><span style="font-size: 19px;"><math>{\color{red} \text{Basically, the whole proof is correct. But, there is a mistake in the following equation,}}</math></span></font><br> | + | <font face="serif"><span style="font-size: 19px;"><math>{\color{red} \text{Basically, the whole proof is correct. But, there is a mistake in the following equation,}}</math></span></font><br> |
− | <font face="serif"><span style="font-size: 19px;"><math>{\color{red} E[g_{1}(x)] = P \{\mid x - \mu\mid \geq \varepsilon \} }</math></span></font><br> | + | <font face="serif"><span style="font-size: 19px;"><math>{\color{red} E[g_{1}(x)] = P \{\mid x - \mu\mid \geq \varepsilon \} }</math></span></font><br> |
<font face="serif"><span style="font-size: 19px;"><math>{\color{red} \text{The probability measure } P( \cdot ) \text{ should evaluate on an event. Thus, I will rewrite this equation as follow}} | <font face="serif"><span style="font-size: 19px;"><math>{\color{red} \text{The probability measure } P( \cdot ) \text{ should evaluate on an event. Thus, I will rewrite this equation as follow}} | ||
− | </math></span></font><br> | + | </math></span></font><br> |
− | <font face="serif"><span style="font-size: 19px;"><math>{\color{red} E[g_{1}(x)] = P \left( \{x: |X(x) - \mu\mid \geq \varepsilon \} \right) }</math></span></font><br> | + | <font face="serif"><span style="font-size: 19px;"><math>{\color{red} E[g_{1}(x)] = P \left( \{x: |X(x) - \mu\mid \geq \varepsilon \} \right) }</math></span></font><br> |
===== <math>\color{blue}\text{Solution 2:}</math> ===== | ===== <math>\color{blue}\text{Solution 2:}</math> ===== | ||
Line 76: | Line 80: | ||
*Discrete Case:<br> | *Discrete Case:<br> | ||
− | Let < | + | Let <span class="texhtml">''p''<sub>''X''</sub>(''x'')</span> be the pmf of X. The probability that <span class="texhtml">''X''</span> differs from <span class="texhtml">μ</span> by at least <math>\varepsilon </math> is <br> |
− | <math> P(|X-\mu| \geq \varepsilon)= \sum_{x \in \{|X-\mu| \geq \varepsilon \} }p_{X}(x)</math | + | <math> P(|X-\mu| \geq \varepsilon)= \sum_{x \in \{|X-\mu| \geq \varepsilon \} }p_{X}(x)</math> |
− | Based on the definition of the variance, we have<br> | + | Based on the definition of the variance, we have<br> <span class="texhtml"> |
− | < | + | </span> |
+ | |||
+ | {| | ||
+ | |- style="text-align: center;" | ||
+ | | σ<sup>2</sup> = ''E''[(''X'' − ''E''[''X''])] = | ||
+ | | <span style="font-size: x-large; font-family: serif;">∑</span> | ||
+ | | (''x'' − μ)<sup>2</sup>''p''<sub>''X''</sub>(''x'') | ||
+ | |- style="text-align: center; vertical-align: top;" | ||
+ | | | ||
+ | | ''x'' | ||
+ | | | ||
+ | |} | ||
+ | |||
+ | <br> | ||
Let a set <math>A= \{ x|\,|x-\mu| \geq \varepsilon \}</math>. We have<br> <math> \sigma^2 = \sum_{x}(x-\mu)^2 p_{X}(x)= \sum_{x \in A}(x-\mu)^2 p_{X}(x)+\sum_{x \notin A}(x-\mu)^2 p_{X}(x)</math><br> <math> \Rightarrow\sigma^2 \geq \sum_{x \in A}(x-\mu)^2 p_{X}(x)</math><br> Since, in set <span class="texhtml">''A''</span>, we have <math>|x-\mu| \geq \varepsilon</math>, we have<br> <math> \Rightarrow\sigma^2 \geq \sum_{x \in A}\varepsilon^2 p_{X}(x)= \varepsilon^2 \sum_{x \in A}p_{X}(x)=\varepsilon^2 P(x \in A) =\varepsilon^2 P(|X-\mu| \geq \varepsilon)</math><br> That is <br> <math> P(|X-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2}</math><br> | Let a set <math>A= \{ x|\,|x-\mu| \geq \varepsilon \}</math>. We have<br> <math> \sigma^2 = \sum_{x}(x-\mu)^2 p_{X}(x)= \sum_{x \in A}(x-\mu)^2 p_{X}(x)+\sum_{x \notin A}(x-\mu)^2 p_{X}(x)</math><br> <math> \Rightarrow\sigma^2 \geq \sum_{x \in A}(x-\mu)^2 p_{X}(x)</math><br> Since, in set <span class="texhtml">''A''</span>, we have <math>|x-\mu| \geq \varepsilon</math>, we have<br> <math> \Rightarrow\sigma^2 \geq \sum_{x \in A}\varepsilon^2 p_{X}(x)= \varepsilon^2 \sum_{x \in A}p_{X}(x)=\varepsilon^2 P(x \in A) =\varepsilon^2 P(|X-\mu| \geq \varepsilon)</math><br> That is <br> <math> P(|X-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2}</math><br> | ||
Line 90: | Line 107: | ||
</math> | </math> | ||
− | ===Related | + | |
+ | |||
+ | <u>'''Shruthi Kubatur's comments on Solution 2:'''</u> | ||
+ | |||
+ | 1. Probabilities are defined on events. So using curtly braces inside parentheses are necessary. | ||
+ | |||
+ | 2. Variance formula is incorrect. The expectation argument is not squared. | ||
+ | |||
+ | 3. Using ":" for "such that" is more standard and less ambiguous than using "|". | ||
+ | |||
+ | |||
+ | |||
+ | === Related Problems === | ||
+ | |||
---- | ---- | ||
− | 1. State and prove the Markov inequality for a nonnegative random variable < | + | |
+ | 1. State and prove the Markov inequality for a nonnegative random variable <span class="texhtml">''X''</span>. | ||
+ | |||
+ | 2. State and solve Chebyshev's inequality for an m-dimensional random vector. | ||
+ | |||
---- | ---- | ||
+ | |||
[[Category:ECE]] [[Category:QE]] [[Category:CNSIP]] [[Category:Problem_solving]] [[Category:Random_variables]] [[Category:Probability]] | [[Category:ECE]] [[Category:QE]] [[Category:CNSIP]] [[Category:Problem_solving]] [[Category:Random_variables]] [[Category:Probability]] |
Revision as of 08:16, 15 August 2014
Communication, Networking, Signal and Image Processing (CS)
Question 1: Probability and Random Processes
August 2012
Contents
[hide]Problem 2
Problem: State and prove the Chebyshev inequality for random variable with mean μ and variance σ2. In constructing your proof, keep in mind that may be either a discrete or continuous random variable.
Problem premise: Let X be a continuous or discrete random variable with mean μ and variance σ2. Then, $ \forall \varepsilon >0 $, we have
$ P(|X-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2} $
$ \color{blue}\text{Solution 1:} $
- Continuous Case:
Let X be a random variable with mean μ and variance σ2
Consider two functions g1(x) and g2(x)
$ g_{1}(x)= 1_{\{x: \mid x-\mu\mid \geq \varepsilon\}}(x) $
$ g_{2}(x)=\frac{(x-\mu)^2}{\varepsilon^2} $
Clearly,
$ g_{2}(x)-g_{1}(x) \geq 0\; \; \forall x \in \mathbb {R} $
$ E[g_{2}(x)-g_{1}(x) ] \geq 0 \; \; \forall x \in \mathbb {R} $
Consider,
E[g2(x) − g1(x)] = E[g2(x)] − E[g1(x)]
where, $ E[g_{2}(x)]=E[\frac{(x-\mu)^2}{\varepsilon^2}] = \frac{1}{\varepsilon^2} var(X) = \frac{\sigma^2}{\varepsilon^2} $
and
$ E[g_{1}(x)] = P \{\mid x - \mu\mid \geq \varepsilon \} $
Thus we get,
$ \frac{\sigma^2}{\varepsilon^2} - P\{\mid X - \mu \mid \geq \varepsilon\} \geq 0 $
Therefore,
$ P\{\mid X - \mu \mid \geq \varepsilon\} \leq \frac{\sigma^2}{\varepsilon^2} $
- Discrete Case:
The inequalities described above hold even if the x-axis is discretized. That is, if the random variable X is discrete. In other words, the discrete case is a proper subset of the continuous case in this problem. Thus, the Chebyshev inequality holds for discrete random variables.
$ {\color{red} \text{Basically, the whole proof is correct. But, there is a mistake in the following equation,}} $
$ {\color{red} E[g_{1}(x)] = P \{\mid x - \mu\mid \geq \varepsilon \} } $
$ {\color{red} \text{The probability measure } P( \cdot ) \text{ should evaluate on an event. Thus, I will rewrite this equation as follow}} $
$ {\color{red} E[g_{1}(x)] = P \left( \{x: |X(x) - \mu\mid \geq \varepsilon \} \right) } $
$ \color{blue}\text{Solution 2:} $
- Discrete Case:
Let pX(x) be the pmf of X. The probability that X differs from μ by at least $ \varepsilon $ is
$ P(|X-\mu| \geq \varepsilon)= \sum_{x \in \{|X-\mu| \geq \varepsilon \} }p_{X}(x) $
Based on the definition of the variance, we have
σ2 = E[(X − E[X])] = | ∑ | (x − μ)2pX(x) |
x |
Let a set $ A= \{ x|\,|x-\mu| \geq \varepsilon \} $. We have
$ \sigma^2 = \sum_{x}(x-\mu)^2 p_{X}(x)= \sum_{x \in A}(x-\mu)^2 p_{X}(x)+\sum_{x \notin A}(x-\mu)^2 p_{X}(x) $
$ \Rightarrow\sigma^2 \geq \sum_{x \in A}(x-\mu)^2 p_{X}(x) $
Since, in set A, we have $ |x-\mu| \geq \varepsilon $, we have
$ \Rightarrow\sigma^2 \geq \sum_{x \in A}\varepsilon^2 p_{X}(x)= \varepsilon^2 \sum_{x \in A}p_{X}(x)=\varepsilon^2 P(x \in A) =\varepsilon^2 P(|X-\mu| \geq \varepsilon) $
That is
$ P(|X-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2} $
- Continuous Case:
Let fX(x) be the pdf of X.
$ \sigma^2=\int_{-\infty}^{\infty}(x-\mu)^2f_{X}(x) \,dx \geq \int_{-\infty}^{\mu-\varepsilon}(x-\mu)^2f_{X}(x) \,dx+ \int_{\mu+\varepsilon}^{\infty}(x-\mu)^2f_{X}(x) \,dx $
The last inequality holds since we integrate a positive function. Since $ x \leq \mu-\varepsilon $ or $ x \geq \mu+\varepsilon $
$ \Rightarrow |x-\mu| \geq \varepsilon \Rightarrow (x-\mu)^2 \geq \varepsilon^2 $
Based on the above equation, we have
$ \sigma^2 \geq \int_{-\infty}^{\mu-\varepsilon}\varepsilon^2 f_{X}(x) \,dx+ \int_{\mu+\varepsilon}^{\infty} \varepsilon^2 f_{X}(x) \,dx $
$ = \varepsilon^2 \left( \int_{-\infty}^{\mu-\varepsilon}f_{X}(x) \,dx+ \int_{\mu+\varepsilon}^{\infty} f_{X}(x) \,dx \right) = \varepsilon^2 P \bigg( X \leq (\mu-\varepsilon)\, \text{or} \, X \geq (\mu+\varepsilon) \bigg) = \varepsilon^2 P(|X-\mu| \geq \varepsilon) $
$ \Rightarrow P(|X-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2} $
Shruthi Kubatur's comments on Solution 2:
1. Probabilities are defined on events. So using curtly braces inside parentheses are necessary.
2. Variance formula is incorrect. The expectation argument is not squared.
3. Using ":" for "such that" is more standard and less ambiguous than using "|".
Related Problems
1. State and prove the Markov inequality for a nonnegative random variable X.
2. State and solve Chebyshev's inequality for an m-dimensional random vector.