Welcome to MathOverflow

Question

3

2

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]

flag	asked Mar 28 2011 at 1:00 Jiapeng 37●3

3

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

Ori Gurel-Gurevich · Accepted Answer · 2011-03-28 05:41:30Z UTC

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.

bound the tail distribution

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.