10
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ You probably want to insert the variance somewhere - otherwise take the distribution concentrated at a single point. $\endgroup$ Mar 28, 2011 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, 2011 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$ Mar 29, 2011 at 7:08

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Mar 29, 2011 at 6:16
  • 1
    $\begingroup$ Usually, when talking about $k$-wise independence, one implicitly assumes that $k>1$... $\endgroup$ Mar 29, 2011 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$ Mar 29, 2011 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$ Mar 29, 2011 at 15:25

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.