| Line 1: | Line 1: | ||
2.2 Chebyshev inequality | 2.2 Chebyshev inequality | ||
| − | Let <math>\mathbf{X}</math> be a random variable with mean <math>\mu</math> and variance <math>\sigma^{2}</math> . Then <math>\forall\epsilon>0</math> | + | Let <math class="inline">\mathbf{X}</math> be a random variable with mean <math class="inline">\mu</math> and variance <math class="inline">\sigma^{2}</math> . Then <math class="inline">\forall\epsilon>0</math> |
| − | <math>p\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)\leq\frac{\sigma^{2}}{\epsilon^{2}}</math>. | + | <math class="inline">p\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)\leq\frac{\sigma^{2}}{\epsilon^{2}}</math>. |
Proof 1 | Proof 1 | ||
| Line 9: | Line 9: | ||
[[Image:ECE600 Note Chebyshev inequality1.jpg]] | [[Image:ECE600 Note Chebyshev inequality1.jpg]] | ||
| − | <math>\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}}</math>. | + | <math class="inline">\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}}</math>. |
| − | <math>\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}.</math> | + | <math class="inline">\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}.</math> |
| − | <math>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. </math> | + | <math class="inline">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. </math> |
| − | <math>\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}}.</math> | + | <math class="inline">\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}}.</math> |
| − | <math>\therefore p\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)\leq\frac{\sigma^{2}}{\epsilon^{2}}.</math> | + | <math class="inline">\therefore p\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)\leq\frac{\sigma^{2}}{\epsilon^{2}}.</math> |
Proof 2 | Proof 2 | ||
| − | <math>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).</math> | + | <math class="inline">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).</math> |
| − | <math>P\left(\left\{ \mathbf{X}\geq\epsilon\right\} \right)\leq\frac{E\left[\mathbf{X}\right]}{\epsilon}.</math> | + | <math class="inline">P\left(\left\{ \mathbf{X}\geq\epsilon\right\} \right)\leq\frac{E\left[\mathbf{X}\right]}{\epsilon}.</math> |
| − | <math>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}}.</math> | + | <math class="inline">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}}.</math> |
| − | <math>\therefore p\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)\leq\frac{\sigma^{2}}{\epsilon^{2}}.</math> | + | <math class="inline">\therefore p\left(\left\{ \left|\mathbf{X}-\mu\right|\geq\epsilon\right\} \right)\leq\frac{\sigma^{2}}{\epsilon^{2}}.</math> |
---- | ---- | ||
Latest revision as of 11:38, 30 November 2010
2.2 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}} $.
Proof 1
$ \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}}. $
Proof 2
$ 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}}. $
