| Line 1: | Line 1: | ||
| − | + | <br> | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
<center> | <center> | ||
| − | <font size= 4> | + | <font size="4">[[ECE PhD Qualifying Exams|ECE Ph.D. Qualifying Exam]] </font> |
| − | [[ | + | |
| − | </font | + | |
| − | <font size= 4> | + | <font size="4">Communication, Networking, Signal and Image Processing (CS)</font> |
| − | Communication, Networking, Signal and Image Processing (CS) | + | |
| − | Question 1: Probability and Random Processes | + | <font size="4">Question 1: Probability and Random Processes </font> |
| − | </font | + | |
| − | August 2012 | + | August 2012 |
| − | </center> | + | </center> |
---- | ---- | ||
| + | |||
---- | ---- | ||
| − | Jump to [[ECE- | + | |
| + | Jump to [[ECE-QE CS1-2012 solution-1|Problem 2]],[[ECE-QE CS1-2012 solution-2|3]] | ||
| + | |||
---- | ---- | ||
| − | =Problem 2 = | + | |
| − | Problem statement: Let < | + | = Problem 2 = |
| − | <math> P(|X-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2}</math><br> | + | |
| − | ===== <math>\color{blue}\text{Solution 1:}</math> | + | 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> |
| + | |||
| + | ===== <math>\color{blue}\text{Solution 1:}</math><br> ===== | ||
| + | |||
| + | Statement: If '''X''' is random variable (continuous or discrete) with mean <math>\mu</math> and variance <math>\sigma^2</math>, then | ||
| + | |||
| + | P{|'''X'''-<math>\mu \geq \varepsilon</math>} | ||
===== <math>\color{blue}\text{Solution 2:}</math> ===== | ===== <math>\color{blue}\text{Solution 2:}</math> ===== | ||
| + | |||
*Discrete Case:<br> | *Discrete Case:<br> | ||
| − | Let < | + | |
| − | <math> P(|X-\mu| \geq \varepsilon)= \sum_{|X-\mu| \geq \varepsilon}p_{X}(x)</math><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"> |
| − | Based on the definition of the variance, we have<br> | + | </span> |
| − | < | + | |
| − | Let a set <math | + | {| |
| − | <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> | + | |- style="text-align: center;" |
| − | <math> \Rightarrow\sigma^2 \geq \sum_{x \in A}(x-\mu)^2 p_{X}(x)</math><br> | + | | σ<sup>2</sup> = |
| − | Since, in set < | + | | <span style="font-size: x-large; font-family: serif;">∑</span> |
| − | <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> | + | | (''x'' − μ)<sup>2</sup>''p''<sub>''X''</sub>(''x'') |
| − | That is <br> | + | |- style="text-align: center; vertical-align: top;" |
| − | <math> P(|X-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2}</math><br> | + | | |
| + | | ''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> | ||
*Continuous Case:<br> | *Continuous Case:<br> | ||
| − | Let < | + | |
| − | <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> | + | 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} |
| − | The last inequality holds since we integrate a positive function. Since <math | + | </math> |
| − | <math> \Rightarrow |x-\mu| \geq \varepsilon \Rightarrow (x-\mu)^2 \geq \varepsilon^2 </math><br> | + | |
| − | Based on the above equation, we have <br> | + | [[Category:ECE]] [[Category:QE]] [[Category:CNSIP]] [[Category:Problem_solving]] [[Category:Random_variables]] [[Category:Probability]] |
| − | <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} | + | |
Revision as of 12:24, 26 January 2014
Communication, Networking, Signal and Image Processing (CS)
Question 1: Probability and Random Processes
August 2012
Problem 2
Problem statement: 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:} $
Statement: If X is random variable (continuous or discrete) with mean $ \mu $ and variance $ \sigma^2 $, then
P{|X-$ \mu \geq \varepsilon $}
$ \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-\mu| \geq \varepsilon}p_{X}(x) $
Based on the definition of the variance, we have
| σ2 = | ∑ | (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} $
