# Talagrand's concentration inequality with limited independence

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?

-
You probably want to insert the variance somewhere - otherwise take the distribution concentrated at a single point. – Ori Gurel-Gurevich Mar 28 '11 at 23:36
@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. – Anindya De Mar 29 '11 at 1:30
$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 – 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.

-
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. – Tom LaGatta Mar 29 '11 at 6:16
Usually, when talking about $k$-wise independence, one implicitly assumes that $k>1$... – Ori Gurel-Gurevich Mar 29 '11 at 7:18
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$. – Tom LaGatta Mar 29 '11 at 14:50
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. – Ori Gurel-Gurevich Mar 29 '11 at 15:25