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 GurelGurevich 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 kwise 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/boundthetaildistribution $\endgroup$ – Ori GurelGurevich 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 / (1p)$. 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] ChernoffHoeffding 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 GurelGurevich 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 GurelGurevich Mar 29 '11 at 15:25