Concentration inequalities via zero bias couplings

The tails of the distribution of a mean zero, variance σ2σ2 random variable YY satisfy concentration of measure inequalities of the form P(Y≥t)≤exp(−B(t))P(Y≥t)≤exp(−B(t)) forB(t)=t22(σ2+ct)for  t≥0,andB(t)=tc(logt−loglogt−σ2c)for  t>e whenever there exists a zero biased coupling of YY bounded by cc, under suitable conditions on the existence of the moment generating function of YY. These inequalities apply in cases where YY is not a function of independent variables, such as for the Hoeffding statistic Y=∑i=1naiπ(i) where A=(aij)1≤i,j≤n∈Rn×nA=(aij)1≤i,j≤n∈Rn×n and the permutation ππ has the uniform distribution over the symmetric group, and when its distribution is constant on cycle type.