## bound the tail distribution

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]

-
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 2011 at 2:37
Yes, I want a bound on the tail probability of \sum Z_i. – Jiapeng Mar 28 2011 at 8:20