Cantelli's inequality

Let ${\displaystyle X}$ be a real-valued random variable with finite variance ${\displaystyle \sigma ^{2}}$ and expectation ${\displaystyle \mu }$, and define ${\displaystyle Y=X-\mathbb {E} [X]}$ (so that ${\displaystyle \mathbb {E} [Y]=0}$ and ${\displaystyle \operatorname {Var} (Y)=\sigma ^{2}}$).

Then, for any ${\displaystyle u\geq 0}$, we have

${\displaystyle \Pr(X-\mathbb {E} [X]\geq \lambda )=\Pr(Y\geq \lambda )=\Pr(Y+u\geq \lambda +u)\leq \Pr((Y+u)^{2}\geq (\lambda +u)^{2})\leq {\frac {\mathbb {E} [(Y+u)^{2}]}{(\lambda +u)^{2}}}={\frac {\sigma ^{2}+u^{2}}{(\lambda +u)^{2}}}.}$

the last inequality being a consequence of Markov's inequality. As the above holds for any choice of ${\displaystyle u\in \mathbb {R} }$, we can choose to apply it with the value that minimizes the function ${\displaystyle u\geq 0\mapsto {\frac {\sigma ^{2}+u^{2}}{(\lambda +u)^{2}}}}$. By differentiating, this can be seen to be ${\displaystyle u_{\ast }={\frac {\sigma ^{2}}{\lambda }}}$, leading to

${\displaystyle \Pr(X-\mathbb {E} [X]\geq \lambda )\leq {\frac {\sigma ^{2}+u_{\ast }^{2}}{(\lambda +u_{\ast })^{2}}}={\frac {\sigma ^{2}}{\lambda ^{2}+\sigma ^{2}}}}$ if ${\displaystyle \lambda >0}$

We proceed as before, writing ${\displaystyle \alpha =-\lambda >0}$ and for any ${\displaystyle u\geq 0}$

${\displaystyle \Pr(X-\mathbb {E} [X]<\lambda )=\Pr(-Y>\alpha )\leq {\frac {\sigma ^{2}}{\alpha ^{2}+\sigma ^{2}}}={\frac {\sigma ^{2}}{\lambda ^{2}+\sigma ^{2}}}}$

using the previous derivation on ${\displaystyle -Y}$. By taking the complement of the left-hand side, we obtain

${\displaystyle \Pr(X-\mathbb {E} [X]\geq \lambda )\geq 1-{\frac {\sigma ^{2}}{\lambda ^{2}+\sigma ^{2}}}}$ if ${\displaystyle \lambda <0}$