Proof of Cantelli's Inequality

About Posts which Tagged by 'Probability'

Cantelli's inequality.  Suppose $\sigma^2=\mbox{Var}(X)<\infty$.  Then for $a>0$, we have $$\mathscr{P}\{|X-\mathscr{E}(X)|>a\}\leq\frac{2\sigma^2}{a^2+\sigma^2}.$$
See List of Inequalities.

$\bullet$ Proof.

Define $Y=X-\mathscr{E}(X)$, thus $\mathscr{E}(Y)=0$, $\mbox{Var}(Y)=\mbox{Var}(X)=\sigma^2$.  First, suppose $Y\geq0$.  Define $h(y)=(y+c)^2$ for $c\in\mathbb{R}$.  By Chebyshev's inequality, since $h>0$ and is increasing with $y$, we have $$\begin{array}{rl}\mathscr{P}\{X-\mathscr{E}(X)>a\}=\mathscr{P}\{Y>a\} & \leq\frac{\mathscr{E}[h(Y)]}{h(a)}\\ &=\frac{\mathscr{E}(Y+c)^2}{(a+c)^2}\\ &=\frac{\mathscr{E}(Y^2)+2c\mathscr{E}(Y)+c^2}{(a+c)^2}=\frac{\sigma^2+c^2}{(a+c)^2},\;c\in\mathbb{R}.\end{array}$$Then a sharp bound is achieved by taking the minimum of the right-hand-side of the inequality w.r.t. $c$.  Let $$\frac{\partial}{\partial\,c}\frac{\sigma^2+c^2}{(a+c)^2}=\frac{2c(a+c)-2(\sigma^2+c^2)}{(a+c)^3}=0.$$We have $c^*=\sigma^2/a$ minimizes $\frac{\sigma^2+c^2}{(a+c)^2}$.  Thus, $$\mathscr{P}\{X-\mathscr{E}(X)>a\}\leq\frac{\sigma^2+{c^*}^2}{(a+c^*)^2}=\frac{\sigma^2}{a^2+\sigma^2}.$$Next, suppose $Y<0$.  Let $a'<0$.  Similarly, we have $$\mathscr{P}\{Y<a'\}=\mathscr{P}\{-Y>-a'\}\leq\frac{\sigma^2}{a'^2+\sigma^2}.$$Hence, combine these two bounds, we have $$\mathscr{P}\{|X-\mathscr{E}(X)|>a\}=\mathscr{P}\{Y<-a\}+\mathscr{P}\{Y>a\}\leq\frac{2\sigma^2}{a^2+\sigma^2}.$$

$\Box$