Cantelli's inequality proof

Question

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?

Answer 1

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