Analog of Chebyshev's inequality for higher moments

Question

I have a positive random variable $X$ with $E[X] = 1$ and a small number $k$ more moments bounded by constants:

$$E[(X-1)^i] = O(1) \forall i \in \{2, ..., k\}.$$

I'd like to bound the average of $n$ independent samples of $X$. Markov's inequality only uses the first moment to get:

$$\Pr[\frac{1}{n}\sum_{i=1}^n x_i \geq c] \leq 1/c$$

Chebyshev's inequality also uses the second moment to get:

$$\Pr[\frac{1}{n}\sum x_i \geq 1 + c] \leq \frac{O(1)}{nc^2}$$

which is better asymptotic behavior in $n$. If infinite moments converged, I could use Azuma/Chernoff/Hoeffding/McDiarmid to get

$$\Pr[\frac{1}{n}\sum x_i \geq 1 + c] \leq e^{-f(c)n}$$

for some function $f(c)$. But what if I have somewhere between 2 and infinite moments, say 10 moments. Is there a theorem with better asymptotic behavior for intermediate moments?

Answer 1

Thomas Bloom is right: the proof of the usual Chebyshev inequality can be easily adapted to the higher moment case. Rather than looking at the statement of the theorem and being satisfied with it, however, I think it's worth digging into the proof and seeing exactly what to change.

The proof of the Chebyshev inequality is simple and robust, and I recommend takng the time to memorize it. It goes as follows (assume $\mathbb EX = 0$):$$\mathbb P( |X| > u ) = \int 1_{|X| > u} ~d\mathbb P = \frac 1 {u^2} \int u^2 1_{|X| > u} ~d\mathbb P < \frac 1 {u^2} \int |X|^2 1_{|X| > u} ~ d\mathbb P \le \frac 1 {u^2} \mathbb E|X|^2.$$

In the second step, we introduce the factor of $1 = u^2 / u^2$. If you want to prove the theorem for the $p$th moment, modify this factor to $u^p / u^p$. If you want to prove the exponential Chebyshev inequality, use $\exp(ru) / \exp(ru)$. If you want to bound the probability by the entropy $-\mathbb E X \log X$, then use the factor $-u\log u / (-u \log u)$.

Answer 2

There is an easy generalisation of Chebyshev's inequality for higher moments, proved exactly the same way: $$ \mathbb{P}(\lvert X-\mathbb{E}(X)\rvert>\lambda)\leq\frac{\mbox{M}_p(X)}{\lambda^p}$$

for any $\lambda>0$ and $p\geq2$, where $M_p(X)$ is the pth moment, $$\mathbb{E}(\lvert X-\mathbb{E}(X)\rvert^p).$$

Answer 3

Tom is right: the proof of Chebyshev's inequality can be easily adapted to every nondecreasing nonnegative function. The proof of this generalization that I prefer has a principle worth remembering:

First find an inequality between random variables, then integrate it.

To apply the principle, let $g$ denote a nondecreasing nonnegative function defined on $[0,+\infty)$ and $Z$ a nonnegative random variable. Let $z\ge0$ such that $g(z)>0$. Then, $$ g(z)\mathbf{1}_A\le g(Z)\ \mbox{with}\ A=[Z\ge z]. $$ Proof: if $\omega\notin A$, the assertion reduces to $0\le g(Z(\omega))$, which holds because $g$ is nonnegative everywhere; if $\omega\in A$, the assertion reduces to $g(z)\le g(Z(\omega))$, which holds because $Z(\omega)\ge z$ and $g$ is nondecreasing.

Integrating the inequality yields $$ g(z)P(A)\le E(g(Z)), $$ and, dividing both sides by $g(z)$, we are done.

The usual case is when $Z=|X-E(X)|$ and $g(z)=z$. The case mentioned by Thomas is when $Z=|X-E(X)|$ and $g(z)=z^p$, for every positive $p$ (and not only for $p\ge2$). Another case, mentioned by Tom and at the basis of the whole field of large deviations principles, is when $Z=\mathrm{e}^{rX}$ for a nonnegative $r$ and $g(z)=z$. But to deal with the $u\log(u)$ case mentioned by Tom requires to be more careful because the function $u\mapsto u\log(u)$ is non monotonous on $[0,1]$ and not of a constant sign on $[0,+\infty)$ (but everything works fine for $g(z)=z\log(z)$ on $[1,+\infty)$, that is, if $Z\ge1$ almost surely).