7.4 Other Inequalities
Result 7.4.1 (One-Sided Chebyshev’s Inequality). If \(X\) is a random variable with mean \(0\) and
finite variance \(\sigma ^2\), then for any \(a>0\),
\(P(X\geq a)\leq \dfrac {\sigma ^2}{\sigma ^2 +a^2}\)
Proof. \begin {align*} P(X\geq a) &=P(X+k\geq a+k)\hspace {0.3cm}\text {for}\hspace {0.3cm} k>0\\ &=P\Big ((X+k)^2\geq (a+k)^2\Big )\\ &\leq \frac {E(X+k)^2}{(a+k)^2}\\ &=\frac {E(X^2+2Xk+k^2)}{(a+k)^2}\\ &=\frac {\sigma ^2+k^2}{(a+k)^2} \end {align*}
We find a \(k\) that minimizes \(\dfrac {\sigma ^2+k^2}{(a+k)^2}\) \begin {align*} \text {Let}\hspace {0.5cm} g(k) &=\frac {\sigma ^2+k^2}{(a+k)^2}\\\\ g'(k) &=\frac {2k(a+k)^2-(\sigma ^2+k^2)\hspace {0.1cm} 2(a+k)}{(a+k)^4} \end {align*}
\[g'(k)=0\hspace {0.1cm}\Longleftrightarrow \hspace {0.1cm}k(a+k)^2-(a+k)(\sigma ^2+k^2)=0\] \[(a+k)(k(a+k)-\sigma ^2-k^2)=0\] \[(a+k)(ak-\sigma ^2)=0\hspace {0.3cm}\text {either}\hspace {0.3cm}k=-a\hspace {0.3cm}\text {or}\hspace {0.3cm} k=\frac {\sigma ^2}{a}\] \begin {align*} \therefore \hspace {0.5cm} P(X\geq a) &\leq \frac {\sigma ^2+\Big (\frac {\sigma ^2}{a}\Big )^2}{\Big (a+\frac {\sigma ^2}{a}\Big )^2}\\\\ &=\frac {\sigma ^2\Big (1+\frac {\sigma ^2}{a^2}\Big )}{\frac {(a^2+\sigma ^2)}{a^2}}\\\\ &=\frac {\sigma ^2\Big (\frac {a^2+\sigma ^2}{a^2}\Big )}{\frac {(a^2+\sigma ^2)}{a^2}}\\ &=\frac {\sigma ^2}{a^2+\sigma ^2} \end {align*}
Q.E.D
Example 7.4.2. In example 3.1.3, the number of items produced in a week \(X\) is a random variable with mean \(60\) and variance \(16\). Find the bound of the production that the week’s production will be fewer than \(70\). \begin {align*} P(X<70) &=1-P(X\geq 70)\\\\ P(X\geq 70) &\leq \frac {16}{(70)^2+16}=\frac {16}{4916}\\\\ \implies \hspace {0.5cm} P(X<70) &\geq 1-\frac {16}{4916}\\\\ &=1-0.003255\\\\ &=0.996745 \end {align*}
\begin {align*} P(X\geq a) &=P\Big (e^X\geq e^t\Big )=P\Big (e^{aX}\geq e^{at}\Big )\\ &\leq \frac {E\Big (e^{Xt}\Big )}{e^{at}}\\ &=\frac {M_X(t)}{e^{at}}\\\\ \implies \hspace {0.3cm} P(X\geq a) &\leq M_X(t)e^{-at}\hspace {0.5cm}t>0\\ \end {align*}
\begin {align*} P(x\leq a) &=P\Big (e^X\leq e^a\Big )=P\Big (e^{Xt}\leq e^{at}\Big )\\ &\leq \frac {E\Big (e^{Xt}\Big )}{e^{at}}\\ &=E\Big (e^{Xt}\Big )e^{-at}\\\\ \implies \hspace {0.5cm} P(X\leq a) &\leq M_X(t)e^{-at}\hspace {0.3cm} \text {if}\hspace {0.3cm} t<0. \\ \end {align*}
Result 7.4.3 (Chernoff Bounds). If \(X\) is a random variable with mgf \(M_X(t)\), then for \(a>0\), then we have
- (i)
- \(P(X\geq a)\leq e^{-at}M_X(t)\) if \(t>0\).
- (ii)
- \(P(X\leq a)\leq e^{-at}M_X(t)\) if \(t<0\).
Definition 7.4.4. A twice differentiable real-valued function \(f(x)\) is said to be
- (i)
- Convex if \(f''(x)\geq 0\) for all \(x\).
- (ii)
- Concave if \(f''(x)\leq 0\) for all \(x\).
\[\text {Let}\hspace {0.4cm} f(x)=x^2,\hspace {0.4cm} g(x)=e^{ax},\hspace {0.4cm} h(x)=-x^{\frac {1}{n}}\] \[f'(x)=2x,\hspace {0.5cm}f''(x)=2;\hspace {0.5cm} f(x)=x^2\hspace {0.3cm}\text {is convex.}\] \[K(x)=-f(x)=-x^2,\hspace {0.5cm}\text {then}\hspace {0.3cm}K(x)\hspace {0.3cm}\text {is concave.}\] \begin {align*} g'(x)=ae^{ax},\hspace {0.5cm}& g''(x) =a^2e^{ax}\geq 0.\\\\ &\implies \hspace {0.5cm} g(x)\hspace {0.3cm} \text {is convex}\\\\ &\implies \hspace {0.5cm} -ae^{ax}\hspace {0.3cm}\text {is concave}\\ \end {align*}
\begin {align*} h'(x)=-\frac {1}{n}x^{\frac {1}{n}-1},\hspace {0.5cm} &h''(x)=-\frac {1}{n}\Big (\frac {1}{n}-1\Big )x^{\frac {1}{n}-2}=\frac {n-1}{n^2}x^{\frac {1}{n}-2}\\\\ &\implies \hspace {0.5cm} h(x)\hspace {0.3cm}\text {is convex}\\\\ &\implies \hspace {0.5cm} \frac {1}{n}x^{\frac {1}{n}}\hspace {0.3cm}\text {is concave}\\ \end {align*}
Result 7.4.5 (Jensen’s Inequality). If \(g(\cdot )\) is a convex real valued function and \(X\) is random variable
then \(E\Big (g(X)\Big )\geq g\Big (E(X)\Big ).\)
Proof. We expand \(g(X)\) by Taylor’s series at \(X=\mu =E(X)\). \begin {align*} g(X) &=g(\mu )+g'(\mu )(X-\mu )+\frac {g''(\eta )(X-\eta )^2}{2!},\\ &{\text {where}\hspace {0.3cm}\eta \hspace {0.3cm}\text {is between}\hspace {0.3cm}X\hspace {0.3cm}\text {and}\hspace {0.3cm}\mu .}\\\\ g(X)&\geq g(\mu )+g'(\mu )(X-\mu ),\hspace {0.5cm}\text {since}\hspace {0.3cm}\frac {g''(\eta )(X-\eta )^2}{2!}\geq 0.\\\\ E\Big (g(X)\Big ) &\geq g(\mu )+0\\\\ \implies \hspace {0.4cm} E\Big (g(X)\Big )&\geq g(\mu )=g\Big (E(X)\Big ).\\\\ \end {align*} □
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.