Cantelli's inequality

For one-sided tail bounds, Cantelli's inequality is better, since Chebyshev's inequality can only get

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

On the other hand, for two-sided tail bounds, Cantelli's inequality gives

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

which is always worse than Chebyshev's inequality (when ${\displaystyle \lambda \geq \sigma }$; otherwise, both inequalities bound a probability by a value greater than one, and so are trivial).

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}$

Various stronger inequalities can be shown. He, Zhang, and Zhang showed[6] (Corollary 2.3) when ${\displaystyle \mathbb {E} [X]=0,\,\mathbb {E} [X^{2}]=1}$ and ${\displaystyle \lambda \geq 0}$:

${\displaystyle \Pr(X\geq \lambda )\leq 1-(2{\sqrt {3}}-3){\frac {(1+\lambda ^{2})^{2}}{\mathbb {E} [X^{4}]+6\lambda ^{2}+\lambda ^{4}}}.}$

In the case ${\displaystyle \lambda =0}$ this matches a bound in Berger's "The Fourth Moment Method",[7]

${\displaystyle \Pr(X\geq 0)\geq {\frac {2{\sqrt {3}}-3}{\mathbb {E} [X^{4}]}}.}$

This improves over Cantelli's inequality in that we can get a non-zero lower bound, even when ${\displaystyle \mathbb {E} [X]=0}$.

• Chebyshev's inequality
• Paley–Zygmund inequality