MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose that Z_1, ... , Z_n are binomial distributions with E[Z_i]=z_i.

If (Z_i) are pairwise independent, then, It's well known that the Chebyshev inequality can bound the tail distributions.

If (Z_i) are i.i.d, then, one can use Chernoff bound to bound the tail distributions.

As we know, Chernoff bound gives exponentially decreasing bounds.

My question is that, suppose (Z_i) are sqrt(n)-wise independent, are there any results to bound the tail distributions, i.e, in the case that, Z_(i_1), Z_(i_2),...,Z_(i_sqrt(n)) are i.i.d for arbitrary {i_1,...,i_sqrt(n)}\subset [n]

share|cite|improve this question
Do you mean that the $Z_i$ are Bernoulli random variables and you want a bound on the tail probability of $\sum_i Z_i$ ? – Or Zuk Mar 28 '11 at 2:37
Yes, I want a bound on the tail probability of \sum Z_i. – Jiapeng Mar 28 '11 at 8:20
up vote 4 down vote accepted

Some tools from the theory of the classical moments problem are useful here. You can see how they are used and get some bounds on your question in my joint paper with Itai Benjamini and Ron Peled here (this is an extended abstract, hopefully the paper itself will also be written some day), and the followup paper by Ron Peled, Ariel Yadin and Amir Yehudayoff here.

share|cite|improve this answer
Got it , many thanks :) – Jiapeng Mar 28 '11 at 8:24
np. Feel free to ask questions, here or by email. – Ori Gurel-Gurevich Mar 28 '11 at 20:22

Exponential tail bounds automatically imply moment bounds and vice versa. That is to say, $(a)$ is equivalent to $(A)$ for $a\in \{j,k,l\}$ below where $X$ is a nonnegative random variable and $\|X\|_p = (\mathbb{E} X^p)^{1/p}$. $C,c>0$ are universal constants that may change from line to line.

$(j)$ For all $p\ge 1$, $\|X\|_p \le c\sigma\sqrt{p}$

$(J)$ For all $\lambda>0$, $\mathbb{P}(X > \lambda) \le C \cdot e^{-c\lambda^2/\sigma^2}$

$(k)$ For all $p\ge 1$, $\|X\|_p \le cKp$

$(K)$ For all $\lambda>0$, $\mathbb{P}(X > \lambda) \le C\cdot e^{-c\lambda/K}$

$(l)$ For all $p\ge 1$, $\|X\|_p \le c\sigma\sqrt{p} + cKp$

$(L)$ For all $\lambda>0$, $\mathbb{P}(X > \lambda) \le C\cdot\max\left\{e^{-c\lambda^2/\sigma^2}, e^{-c\lambda/K}\right\}$

One can come up with other examples. Now, $(a)$ implies $(A)$ by Markov's inequality on the $p$th moment. $(A)$ implies $(a)$ using integration by parts (let $\varphi$ be the pdf in what follows and $\Phi$ be the cdf): $$ \mathbb{E} X^p = \int_0^\infty \lambda^p \varphi(\lambda)d\lambda = -\int_0^\infty \lambda^p (-\varphi(\lambda))d\lambda = [\lambda^p\cdot(1 - \Phi(\lambda))]_{\lambda=0}^\infty + \int_0^\infty p\lambda^{p-1}(1 - \Phi(\lambda))d\lambda $$ Now note $1-\Phi(\lambda) = \mathbb{P}(X > \lambda)$, so as long as $\mathbb{P}(X>\lambda)$ decays fast enough, the $[\lambda^p\cdot(1 - \Phi(\lambda))]_{\lambda=0}^\infty$ term goes to $0$ and we've now expressed the $p$th moment in terms of something depending on the tail bound (i.e. $(A)$ implies $(a)$ as claimed).

Now back to your question. Whatever Chernoff bound you're thinking of, it gives a tail bound. Thus, by the above, it automatically implies a moment bound. So if your random variables are $p$-wise independent for $p = \sqrt{n}$ or whatever other value, you can see what tail bound you get by doing Markov's inequality on the $p$th moment.

share|cite|improve this answer

Your Answer


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.