(14 intermediate revisions by 2 users not shown)
Line 3: Line 3:
 
<font size="4">[[ECE PhD Qualifying Exams|ECE Ph.D. Qualifying Exam]] </font>  
 
<font size="4">[[ECE PhD Qualifying Exams|ECE Ph.D. Qualifying Exam]] </font>  
  
<font size="4">Communication, Networking, Signal and Image Processing (CS)</font>
+
<font size="4">Communication, Networking, Signal and Image Processing (CS)</font>  
  
 
<font size="4">Question 1: Probability and Random Processes </font>  
 
<font size="4">Question 1: Probability and Random Processes </font>  
Line 19: Line 19:
 
= Problem 2  =
 
= Problem 2  =
  
Problem statement: 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>
+
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.
  
===== <math>\color{blue}\text{Solution 1:}</math><br> =====
+
<br>  
  
Statement: If '''X''' is random variable (continuous or discrete) with mean <math>\mu</math> and variance <math>\sigma^2</math>, then
+
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>
  
P{|'''X'''-<math>\mu \geq \varepsilon</math>}
+
===== <math>\color{blue}\text{Solution 1:}</math><br>  =====
 +
 
 +
*Continuous Case:<br>
 +
 
 +
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>
 +
 
 +
<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>
 +
 
 +
Clearly,
 +
 
 +
<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>
 +
 
 +
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, <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
 +
 
 +
<math>E[g_{1}(x)] = P \{\mid x - \mu\mid \geq \varepsilon \}</math>
 +
 
 +
Thus we get,
 +
 
 +
<math>\frac{\sigma^2}{\varepsilon^2} - P\{\mid X - \mu \mid \geq \varepsilon\} \geq 0</math>
 +
 
 +
Therefore,
 +
 
 +
<math>P\{\mid X - \mu \mid \geq \varepsilon\} \leq \frac{\sigma^2}{\varepsilon^2}</math>
 +
 
 +
<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.
 +
 
 +
<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} \text{The probability measure } P( \cdot ) \text{ should evaluate on an event. Thus, I will rewrite this equation as follow}}
 +
</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 31: Line 80:
 
*Discrete Case:<br>
 
*Discrete Case:<br>
  
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-\mu| \geq \varepsilon}p_{X}(x)</math><br> Based on the definition of the variance, we have<br> <span class="texhtml">
+
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>  
</span>
+
 
 +
<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> <span class="texhtml">
 +
</span>  
  
 
{|
 
{|
 
|- style="text-align: center;"
 
|- style="text-align: center;"
| σ<sup>2</sup> =  
+
| σ<sup>2</sup> = ''E''[(''X'' − ''E''[''X''])] =  
| <span style="font-size: x-large; font-family: serif;">∑</span>
+
| <span style="font-size: x-large; font-family: serif;">∑</span>  
 
| (''x'' − μ)<sup>2</sup>''p''<sub>''X''</sub>(''x'')
 
| (''x'' − μ)<sup>2</sup>''p''<sub>''X''</sub>(''x'')
 
|- style="text-align: center; vertical-align: top;"
 
|- style="text-align: center; vertical-align: top;"
 
|  
 
|  
| ''x''
+
| ''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>  
+
<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>  
  
 
*Continuous Case:<br>
 
*Continuous Case:<br>
Line 51: Line 106:
 
Let <span class="texhtml">''f''<sub>''X''</sub>(''x'')</span> be the pdf of X. <br> <math> \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</math><br> The last inequality holds since we integrate a positive function. Since <math>x \leq \mu-\varepsilon</math> or <math>x \geq \mu+\varepsilon</math><br> <math> \Rightarrow |x-\mu| \geq \varepsilon \Rightarrow (x-\mu)^2 \geq \varepsilon^2 </math><br> Based on the above equation, we have <br> <math> \sigma^2 \geq \int_{-\infty}^{\mu-\varepsilon}\varepsilon^2 f_{X}(x) \,dx+ \int_{\mu+\varepsilon}^{\infty} \varepsilon^2 f_{X}(x) \,dx</math><br> <math> = \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)</math><br> <math>  \Rightarrow P(|X-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2}
 
Let <span class="texhtml">''f''<sub>''X''</sub>(''x'')</span> be the pdf of X. <br> <math> \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</math><br> The last inequality holds since we integrate a positive function. Since <math>x \leq \mu-\varepsilon</math> or <math>x \geq \mu+\varepsilon</math><br> <math> \Rightarrow |x-\mu| \geq \varepsilon \Rightarrow (x-\mu)^2 \geq \varepsilon^2 </math><br> Based on the above equation, we have <br> <math> \sigma^2 \geq \int_{-\infty}^{\mu-\varepsilon}\varepsilon^2 f_{X}(x) \,dx+ \int_{\mu+\varepsilon}^{\infty} \varepsilon^2 f_{X}(x) \,dx</math><br> <math> = \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)</math><br> <math>  \Rightarrow P(|X-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2}
 
</math>  
 
</math>  
 +
 +
<br>
 +
 +
<font color="red"><u>'''Comments on Solution 2:'''</u>
 +
 +
1. Probabilities are defined on events. So using curly 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 "|".
 +
 +
</font>
 +
<br>
 +
 +
=== Related Problems  ===
 +
 +
----
 +
 +
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.&nbsp;
 +
 +
----
  
 
[[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]]

Latest revision as of 08:21, 15 August 2014


ECE Ph.D. Qualifying Exam

Communication, Networking, Signal and Image Processing (CS)

Question 1: Probability and Random Processes

August 2012



Jump to Problem 2,3


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[(XE[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} $


Comments on Solution 2:

1. Probabilities are defined on events. So using curly 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. 


Alumni Liaison

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

Dr. Paul Garrett