Zero Biasing and Combinatorial Central Limit Theorems

Larry Goldstein

Abstract

For a mean zero, variance one random variable W, we say W^{∗} has the W zero biased distribution if

EW f(W) = Ef′(W^{∗}) for all smooth f.

It can be shown using Stein’s method, that W, with distribution F, is close to normal when it can be coupled closely to its zero biased version W^{∗} with distribution F^{∗}, as quantified by the L^{1} norm inequality

||F − Φ||_{1} ≤ 2||F^{∗} − F ||_{1},

where Φ is the cumulative standard normal. The bound provides Berry Esseen type inequalities, with explicit, moderate, constants. By the use of smoothing inequalities, L^{∞} bounds can also be derived in terms of distances between W and W^{∗}. Bounds of these types will be illustrated to assess the quality of the normal approximation in combinatorial central limit theorems, that is, to

Y = ∑_{i=1}^{n} a_{iπ(i)}

when the random permutation π has distribution uniform over the symmetric group S_{n}, and also for certain distributions on S_{n} which are constant on conjugacy classes.