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$. Is there some other If instead $X$ is sampled from a $k$-wise independent distribution over the hypercubewhich can be sampled using $\ll n$ of randomness and , does one can get a similar statement on measure concentration of $F$ around its medianresult?
|
2 | deleted 41 characters in body | ||
|
|
||||
|
|
1 |
|
||
Talagrand's concentration inequality with limited independenceIs 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$. Is there some other distribution over the hypercube which can be sampled using $\ll n$ of randomness and one can get a similar statement on concentration of $F$ around its median?
|
||||
