Concentration inequalities via zero bias couplings

Abstract

The tails of the distribution of a mean zero, variance ${\sigma }^2$ random variable $Y$ satisfy concentration of measure inequalities of the form $\mathbb{P}(Y\ge t)\le \exp (-B(t))$ for $$ B(t)=\frac{t^2}{2( σ^2 + ct)} \quad \mbox{for $t \ge 0$, and} \quad B(t)=\frac{t}{c}\left( \log t - \log \log t - \frac{σ^2}{c}\right) \quad \mbox{for $t>e$} $$ whenever there exists a zero biased coupling of $Y$ bounded by $c$, under suitable conditions on the existence of the moment generating function of $Y$. These inequalities apply in cases where $Y$ is not a function of independent variables, such as for the Hoeffding statistic $Y={\sum }_{i=1}^n{a}_{i\pi (i)}$ where $A=(a_{ij}{)}_{1\le i,j\le n}\in {\mathbb{R}}^{n\times n}$ and the permutation $\pi$ has the uniform distribution over the symmetric group, and when its distribution is constant on cycle type.

11 pages, presentation revised, shortened by referencing existing constructions

Cited by in corpus (4)

• Size biased couplings and the spectral gap for random regular graphs
• The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems
• Sharp finite statistics for quantum key distribution
• Concentration inequalities using approximate zero bias couplings with applications to Hoeffding's statistic under the Ewens distribution