Question

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?

Answer 1

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.