Variation of Chebsyhev: How to prove that?

Question

I have the "job" to prove that for any random variable with standard deviation $\sigma$ and expectation $\mu$ and for any $t>0$ we have $$Pr[X-\mu \geq t \sigma] \leq \frac{1}{1+t^2}.$$

I thought that this would be quite easy and tried to apply Chebyshev, but here's my result:

$$Pr[X - \mu \geq t \sigma] \leq Pr[|X-\mu| \geq t \sigma] \leq \frac{Var[X]}{t^2\sigma^2}=\frac{1}{t^2},$$ so my result is too bad, either because Chebyshev is not good enough or because (what I think is the main reason) my first inequality is too "weak".

How should I handle this in order to get $\frac{1}{1+t^2}$?

Answer 1

The one-sided version of Chebyshev that you are trying to prove is known as Cantelli's Inequality. See Theorem 2.2 of link. It's been around for 104 years.

Answer 2

If you are content with the weaker inequality $$ \mathrm{Pr} (X-\mu \ge t\sigma) \le \frac{2}{1+t^2}, $$ then you are already done. Apply your Chebyshev-like inequality when $t\ge 1$ (so that $\frac{1}{t^2}\le \frac{2}{1+t^2}$) and the trivial bound $\mathrm{Pr}(X-\mu \ge t\sigma)\le 1$ when $0\le t< 1$.