Concentration inequalities via zero bias couplings

Abstract: The tails of the distribution of a mean zero, variance

s i g m a^{2}

random variable

Y

satisfy concentration of measure inequalities of the form

m a t h b b P (Y g e t) l e e x p (- B (t))

for

B(t)=frac{t^2}{2( sigma^2 + ct)} quad mbox{for

t g e 0

, and} quad B(t)=frac{t}{c}left( log t - log log t - frac{sigma^2}{c} ight) 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 = s u m_{i = 1}^{n} a_{i p i (i)}

where

A = (a_{i j})_{1 l e i, j l e n} i n m a t h b b R^{n i m e s n}

and the permutation

p i

has the uniform distribution over the symmetric group, and when its distribution is constant on cycle type.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Concentration inequalities via zero bias couplings