1
$\begingroup$

Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. By partially I mean the variables could be divided into subsets of size atmost k such that any variable from two different sets are independent.

Of course one possible technique is that we sum the variables in a set and treat the sums as my new random variables but now the bound of the value we would have on these variables would be k and that's unreasonable in the setting that we have. So could something better be said ?

If needed the corelation between variables belonging to a set could be better characterized.

Thanks

Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ I guess that under the assumptions you mentioned, treating each subset as a single random variable is tight. To see it, just take each subset to be k copies of the same variable. Some more assumptions are needed if you'd like to prove a better bound. $\endgroup$
    – Or Meir
    Commented May 2, 2013 at 2:33
  • $\begingroup$ Yes that makes sense and hence I had put the last comment in the question. I ll exactly figure out what the dependence is and get back in case its not resolved then. Thanks :) $\endgroup$
    – NAg
    Commented May 2, 2013 at 2:47
  • $\begingroup$ The term "limited independence" is usually interpreted as k-wise independence i.e. every subset of of the variables of size at most k is independent. The two answers have interpreted your question like this, which is not quite what you want. $\endgroup$
    – Thomas Steinke
    Commented May 2, 2013 at 3:40
  • $\begingroup$ yes indeed .. I hope I have stated it clear enough $\endgroup$
    – NAg
    Commented May 2, 2013 at 3:42
  • 2
    $\begingroup$ See Theorem 2 in these notes: terrytao.wordpress.com/2010/01/03/…. If the total variance over all variables is $\sigma$, since each subset random variable is bounded by $k$ in absolute value, you get $\Pr[|S| >= t \sigma] \leq C \max\{\exp(-c t^2), \exp(-c t \sigma/k)\}$, where $S$ is the sum and $C,c$ are constants. Provided you have a significant number of subsets, this is still very good. $\endgroup$
    – Sasho Nikolov
    Commented May 2, 2013 at 6:06

2 Answers 2

Reset to default
9
$\begingroup$

If $X_1, \cdots, X_n$ are $k$-wise independent random variables on $[0,1]$, then $$\text{Pr} \left[ \left| \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right| \geq n \cdot \varepsilon \right] \leq \left( \frac{k^2}{4 n \varepsilon^2} \right)^{\lfloor k/2 \rfloor}.$$ Note that this bound does not necessarily improve with greater $k$. So you may want to choose a smaller $k$ to get the best results.

Proof Sketch. W.L.O.G. $k$ is even. Consider the $k^\text{th}$ moment: $$\text{Ex} \left[ \left( \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right)^k \right] = \sum_{S \in [n]^k} \text{Ex} \left[ \prod_{i \in S} X_i - \text{Ex}[X_i] \right].$$ Each summand on the RHS is nonzero only if every $i$ appears at least twice in $S$. (Otherwise, since $\text{Ex}[X_i-\text{Ex}[X_i]]=0$ and the other terms are independent, the product is zero.) So each nonzero summand has at most $k/2$ different values of $i$. So there are at most ${n \choose k/2} (k/2)^k$ nonzero summands. Each summand is bounded by $1$. Thus $$\text{Ex} \left[ \left( \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right)^k \right] \leq {n \choose k/2} (k/2)^k \leq (n \cdot k^2 /4)^{k/2}.$$ Now apply Markov's inequality to obtain the result. Q.E.D. (Sorry the proof sketch is so brief. I can elaborate if you want.)

This appears as Prob. 3.8 p. 52 in Pseudorandomness by S. Vadhan.

Improve this answer
$\endgroup$
0
4
$\begingroup$

This is the first link on Google for the search "chernoff limited independence":

"Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt et al.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot for the pointer but I just read the first few pages and it seems like their method works for k-wise independence but the case I presented here was not k-wise independence (if I understood the definition of k-wise independence correctly). This was more like a variable being mutually independent with most except a few variables. Sorry if I am missing something very elementary here. $\endgroup$
    – NAg
    Commented May 2, 2013 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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