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?

  • 2
    $\begingroup$ Incidentally, the terminology in the field is not consistent. Both "Markov's inequality" and "Chebyshev's inequality" are often used to refer to more general results than the ones you state, including the one stated in Thomas Bloom's answer. $\endgroup$ Jun 15 '10 at 18:50
  • 2
    $\begingroup$ The CLT kicks in with asymptotic information as soon as you have finite expectation and finite second moment. As $n\to\infty$, that tells you the truth. Hoeffding and such are useful when you have particular knowledge of the $X_i$ (they are Bernoulli, for example), and you want a result that doesn't require large $n$. $\endgroup$ Jun 16 '10 at 0:21

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

  • 6
    $\begingroup$ I remember Markov/Chebyshev like this: If $X$ is nonnegative, then the area above the distribution function $F(x)=\mathbb P(X \leq x)$, below 1, and to the right of $x=0$ is $\mathbb E[X]$. Since that region includes a rectangle with width $\lambda$ and height $1-\mathbb P(X\leq \lambda) = \mathbb P(X>\lambda)$, I get Markov's inequality: $E[X] \geq \lambda \mathbb P(X>\lambda)$. Apply to the correct nonnegative $X$ with the correct $\lambda$ to proceed to Chebyshev! $\endgroup$ Jun 16 '10 at 0:25

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


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.