Is there a version of Talagrand's concentration inequality known when the variables have limited independence. More precisely, Let $F:\mathbb{R}^n \rightarrow \mathbb{R}$ be a $1$-Lipschitz convex function. Then, we know that if $X$ is drawn u.a.r. from the $n$-dimensional hypercube, then $\Pr[ |F(X)-M(F)|>t ] \le 2e^{-t^2}$ where $M(F)$ is the median of $F$. If instead $X$ is sampled from a $k$-wise independent distribution over the hypercube, does one get a similar measure concentration result?

  • $\begingroup$ You probably want to insert the variance somewhere - otherwise take the distribution concentrated at a single point. $\endgroup$ – Ori Gurel-Gurevich Mar 28 '11 at 23:36
  • $\begingroup$ @Ori : I am not sure what is the best way to put the variance condition. So, I am changing it to just asking if k-wise independence suffices. $\endgroup$ – Anindya De Mar 29 '11 at 1:30
  • $\begingroup$ $k$-wise independence isn't enough, if you want to get exponential bounds, see my answer here: mathoverflow.net/questions/59784/bound-the-tail-distribution $\endgroup$ – Ori Gurel-Gurevich Mar 29 '11 at 7:08

It won't be true for small $k$. For example, flip a fair coin: if it's heads, set $X = 0$, and if it's tails, set $X = (1,\dots,1)$. This measure is $1$-wise dependent, but there is certainly no concentration. (Edit: This is a trivial counterexample, but it illustrates the point: When $k$ is small, then each component can have an outsized influence on the function $F(X)$, and this prevents the concentration phenomenon from occurring).

For general Lipschitz functions, I am not familiar with any extension to a $k$-wise setting.

Hoeffding's inequality is the deviation estimate you stated above (but for the mean), applied to the special case $F(X) = \sum_{i=1}^n X_i$: $$\mathbb P( |F(X) - \mathbb E X| > t) \le 2 e^{-2t^2}.$$

There is a generalization of Hoeffding's inequality to the setting of $k$-wise independent random variables, for $k$ sufficiently large. This was proved by Schmidt, Siegel and Srinivasan in [1].

Theorem. (cf. Theorem 4.21 on page 66 of [2])

Let $X_i$ be random variables on $[0,1]$ with $\mathbb E(X_i) = p_i$. Let $X = \sum_{i=1}^n X_i$, and write $\mu := \mathbb E X$ and $p := \mu/n$. Let $\delta > 0$, and let $k_*$ be the first integer greater than $\mu \delta / (1-p)$. If $X_1, \dots, X_n$ are $k$-wise independent for $k \ge k_*$, then $$\mathbb P( X \ge \mu(1+\delta) ) \le \binom{n}{k_*} p^{k_*} \Big/ \binom{\mu(1+\delta)}{k_*}$$

[1] Chernoff-Hoeffding Bounds for Applications with Limited Independence, Schmidt, Siegel and Srinivasan, 1995.

[2] Concentration of Measure for the Analysis of Randomised Algorithms, Dubhashi and Panconesi, 2006.

  • $\begingroup$ According to the authors of [2], "a plethora of versions of CH bounds for limited independence are given in [Schmidt, Siegel & Srinivasan]". So perhaps you'll be able to find a more general concentration inequality written there. $\endgroup$ – Tom LaGatta Mar 29 '11 at 6:16
  • 1
    $\begingroup$ Usually, when talking about $k$-wise independence, one implicitly assumes that $k>1$... $\endgroup$ – Ori Gurel-Gurevich Mar 29 '11 at 7:18
  • $\begingroup$ A trivial counterexample is still a counterexample. The point here is that $k$-wise independence interpolates between the case of full dependence, where there is no concentration, and full independence, where we have superconcentration. I encourage you (or Anindya) to construct a counterexample in the case that $k=2$. $\endgroup$ – Tom LaGatta Mar 29 '11 at 14:50
  • 2
    $\begingroup$ It is not too hard to build a counterexample for small $k$ (but of course, much harder than $k=1$), see the links in my comment to the question. As for "trivial counterexample is still a counterexample" - if someone gave you a theorem saying that for $\mathbb{R}^d$ such and such happens and you say: "well it's wrong, here's a counterexample when $d=0$", the answer would probably be: "right, I meant $d>0$" and this would not be any indication that the theorem is wrong. $\endgroup$ – Ori Gurel-Gurevich Mar 29 '11 at 15:25

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.