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]

  • 3
    $\begingroup$ 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$ ? $\endgroup$ – Or Zuk Mar 28 '11 at 2:37
  • $\begingroup$ Yes, I want a bound on the tail probability of \sum Z_i. $\endgroup$ – Jiapeng Mar 28 '11 at 8:20

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.

  • $\begingroup$ np. Feel free to ask questions, here or by email. $\endgroup$ – 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.


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.