Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  Mark Meckes Jun 15 '10 at 18:50
1  
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$. –  Kevin O'Bryant Jun 16 '10 at 0:21
add comment

3 Answers

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

share|improve this answer
2  
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! –  Kevin O'Bryant Jun 16 '10 at 0:25
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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