anti-concentration

Anti-concentration results are exactly what they sound like. If concentration inequalities study how random variables concentrate around particular values, anti-concentration inequalities are lower bounds on how much they concentrate around these values. Anti-concentration shows up when proving central limit theorems.

Stated another way, concentration inequalities want to provide an upper bound on the quantity $\mathbb{P}(|X-\mathbb{E}X|>ϵ)$, whereas anti-concentration wants to provide upper bounds on $L_{ϵ}(X)={\sup }_v\mathbb{P}(|X-v|\le ϵ)$, thus showing that the concentration around $X$ for any $v$ is limited. $L_{ϵ}(X)$ is often called “Levy’s concentration function”.

Carbery-Wright

Let $X$ be log-concave and $f$ a polynomial of degree $d$. In 2001, Carbery and Wright proved that

$$\underset{v}{\sup }\mathbb{P}(|f(X)-v|<ϵ)\lesssim {\left(\frac{ϵ}{\sqrt{\mathbb{E}f(X{)}^2}}\right)}^{1/d}.$$

Note this covers the case of sums of normally distributed random variables, which is the typical application. See here for a modern statement and explanation of Carbery-Wright.

Glazer and Mikulincer showed how to get dimension-free bounds on the variance of polynomials, which can then be used in combination with Carbery-Wright to upper bound the right hand side above in terms of $ϵ$ and $d$ only.

Esseen’s inequality

Suppose $X$ has characteristic function $\phi$, then

$$L_{ϵ}(X)\le ϵ{\int }_{-2\pi /ϵ}^{2\pi /ϵ}|\phi (\lambda )|\text{d}\lambda .$$

So if $|\phi (\lambda )|\le |\lambda {|}^{-\alpha }$, then $L_{ϵ}(X)\le {ϵ}^{\alpha }$.

Levy-style anti-concentration

If $X_1,\dots ,X_n$ are independent and symmetric random variables in a Banach space and $S_n={\sum }_i{X}_i$, then for all $u>0$

$$\mathbb{P}(\Vert S_n\Vert >u)\ge \frac{1}{2}\mathbb{P}(\Vert \sum _i{X}_{i}1\{\Vert X_i\Vert \le b\}>u).$$

and

$$\mathbb{P}(\Vert S_n\Vert >u)\ge \frac{1}{2}\mathbb{P}(\underset{i}{\max }\Vert X_i\Vert >u).$$