# Cantelli's inequality proof

I am trying to prove the following inequality:

EDIT: Almost immediately after I posted this question, I discovered that the inequality I am being asked to prove is called Cantelli's inequality. When I wrote this up, I didn't realize this particular inequality had a name. I have found multiple proofs through Google, so I don't strictly speaking need a solution anymore. However, I am keeping this question up because none of the proofs I have found involve invoking the fact that $t=E(t-X)\leq E[(t-X)\mathbb{I}_{X<t}]$, as was originally intended.

For $t \geq 0$,

$\mathbb{P}(X-E(X)\geq t)\leq \frac{V(X)}{V(X)+t^2}$

Our professor gave us the following "hints" for working this out: "First work out the problem assuming $E(X)=0$ then use the fact that $t=E(t-X)\leq E[(t-X)\mathbb{I}_{X<t}]$."

EDIT: To be clear, in my notation, $\mathbb{I}$ refers to the indicator function.

The first part is pretty simple. It is basically a variation of the proof for Markov's or Chebychev's inequality. I did it out as follows:

$V(X)=\int_{-\infty}^{\infty}(x-E(X))^2f(x)dx$

(I know that, properly speaking, we should replace $x$ with, say, $u$ and $f(x)$ with $f_x(u)$ when evaluating an integral. To be honest, though, I find that notation/convention to be unnecessarily confusing and not terribly transparent, so I am sticking with my more informal notation.)

If we assume $E(X)=0$, then the above simplifies to

$V(X)=\int_{-\infty}^{\infty}x^2f(x)dx$

For brevity's sake, I will skip some steps, but it is easy to show then that

$V(X)\geq t^2 P(X>t)$, or rather $P(X>t)\leq \frac{V(X)}{t^2}$. Since $E(X)=0$, we can replace the $X$ on the left-hand side of the latter with $X-E(X)$.

Here is where I am having trouble moving forward. I don't understand how to go about using the fact that $t=E(t-X)\leq E[(t-x)\mathbb{I}_{X<t}]$. Again, since $E(X)=0$, we can substitute in $t-E(X)$ for $t$. This is equivalent to $E(t-X)$. Then, we can rewrite the $t^2$ in the denominator at the right-hand side of the inequality as $[E(t-X)]^2$, which since the middle term drops out simplifies to $t^2-[E(X)]^2$. But I don't see where I can go from here, either. Though you can further rewrite this as $t^2+V(X)-E(X^2)$, which at least gets me the $V(X)+t^2$ term in the right place.

Clearly I am missing something, here, related to $E(t-X) \leq E[(t-X)\mathbb{I}_{X<t}]$, but I quite frankly just have no idea what to do with this term. I understand conceptually what this term is telling me. Intuitively, the expected value of $t-X$ is going to be smaller than the same quantity if $X$ is restricted to being strictly less than $t$; that is, the former term is likely to be negative, while the latter must be positive. But I don't see how I can use this fact in the proof.

I tried "distributing" on the inside to simplify ...

$E[(t-X)\mathbb{I}_{X<t}]=E[t\mathbb{I}_{X<t} - X\mathbb{I}_{X<t}]=tP(X<t)-?$

But am not sure how to evaluate $E(X\mathbb{I}_{X<t}]$.

Anyone have an idea or a hint?

• See this answer for a proof of a more general version of what is sometimes called the one-sided Chebyshev inequality (or the one-sided Chebyshev-Cantelli inequality or the Cantelli inequality etc depending on which book you are reading). – Dilip Sarwate Sep 1 '14 at 16:48
• I really wish you hadn't deleted that other question. Far better to have posted an answer to it, so that others could benefit from the suggestions in comments as well as the answer, and you might benefit from further comments. Note, for example, that $p(1-p) \leq \frac{1}{4}$, so $1$ is 4 times bigger than it needs to be. – Glen_b Sep 4 '14 at 13:04
• integral(x(fx)) on interval(t, inf) – user87532 Sep 3 '15 at 2:50

Defining $Y=X-\mathbb{E}[X]$, it follows that $\mathbb{E}[Y]=0$ and $\mathbb{Var}[Y]=\mathbb{Var}[X]=:\sigma^2=\mathbb{E}[Y^2]$.
For $t,u>0$, using Markov's inequality, we have $$\Pr(Y\geq t) = \Pr(Y+u\geq t+u) \leq \Pr((Y+u)^2\geq (t+u)^2)$$ $$\leq \frac{\mathbb{E}[(Y+u)^2]}{(t+u)^2} = \frac{\sigma^2+u^2}{(t+u)^2}=:\varphi(u).$$ Minimize: $\varphi'(u)=0$ gives $u=\sigma^2/t$, and the result follows: $$\Pr(X-\mathbb{E}[X]\geq t) \leq \frac{\sigma^2}{\sigma^2+t^2}.$$