Part 1

State and prove the Tchebycheff Inequality.

Share and discuss your solutions below.

Solution 1 (retrived from here)

First we state the Chebyshev Inequality: Let $ \mathbf{X} $ be a random variable with mean $ \mu $ and variance $ \sigma^{2} $ . Then $ \forall\epsilon>0 $

$ p\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)\leq\frac{\sigma^{2}}{\epsilon^{2}} $.

Now we prove it.

$ \text{Let }g_{1}\left(\mathbf{X}\right)=\mathbf{1}_{\left\{ r\in\mathbf{R}:\left|\mathbf{X}-\mu\right|\geq\epsilon\right\} }\left(\mathbf{X}\right)\text{ and }g_{2}\left(\mathbf{X}\right)=\frac{\left(\mathbf{X}-\mu\right)^{2}}{\epsilon^{2}} $.

$ \text{Let }\phi\left(\mathbf{X}\right)=g_{2}\left(\mathbf{X}\right)-g_{1}\left(\mathbf{X}\right)\Longrightarrow\phi\left(\mathbf{X}\right)\geq0,\;\forall\mathbf{X}\in\mathbf{R}. $

$ E\left[\phi\left(\mathbf{X}\right)\right]=E\left[g_{2}\left(\mathbf{X}\right)-g_{1}\left(\mathbf{X}\right)\right]=E\left[g_{2}\left(\mathbf{X}\right)\right]-E\left[g_{1}\left(\mathbf{X}\right)\right]=\frac{\sigma^{2}}{\epsilon^{2}}-p\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)\text{ and }E\left[\phi\left(\mathbf{X}\right)\right]\geq0. $

$ \because E\left[g_{2}\left(\mathbf{X}\right)\right]=E\left[\frac{\left(\mathbf{X}-\mu\right)^{2}}{\epsilon^{2}}\right]=\frac{1}{\epsilon^{2}}E\left[\left(\mathbf{X}-\mu\right)^{2}\right]=\frac{\sigma^{2}}{\epsilon^{2}}. $

$ \therefore p\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)\leq\frac{\sigma^{2}}{\epsilon^{2}}. $

Solution 2 (retrived from here)

$ E\left[\mathbf{X}\right]=\int_{0}^{\epsilon}xf_{\mathbf{X}}\left(x\right)dx+\int_{\epsilon}^{\infty}xf_{\mathbf{X}}\left(x\right)dx\geq\int_{\epsilon}^{\infty}xf_{\mathbf{X}}\left(x\right)dx\geq\int_{\epsilon}^{\infty}\epsilon f_{\mathbf{X}}\left(x\right)dx=\epsilon P\left(\left\{ \mathbf{X}\geq\epsilon\right\} \right). $

$ P\left(\left\{ \mathbf{X}\geq\epsilon\right\} \right)\leq\frac{E\left[\mathbf{X}\right]}{\epsilon}. $

$ P\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)=P\left(\left\{ \left(\mathbf{X}-\mu\right)^{2}\geq\epsilon^{2}\right\} \right)\leq\frac{E\left[\left(\mathbf{X}-\mu\right)^{2}\right]}{\epsilon^{2}}=\frac{\sigma^{2}}{\epsilon^{2}}. $

$ \therefore p\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)\leq\frac{\sigma^{2}}{\epsilon^{2}}. $

Solution 3

Write it here.

Back to QE CS question 1, January 2001

Back to ECE Qualifying Exams (QE) page