APPLICATIONS OF SIZE BIASED COUPLINGS FOR CONCENTRATION OF MEASURES

作者：Ghosh Subhankar^*; Goldstein Larry

来源：Electronic Communications in Probability, 2011, 16: 70-83.

• Large deviations
• size biased couplings
• Stein's method

Let Y be a nonnegative random variable with mean mu and finite positive variance sigma(2), and let Y(s), defined on the same space as Y, have the Y size biased distribution, that is, the distribution characterized by
E[Yf (Y)] = mu Ef (Y(s)) for all functions f for which these expectations exist.
Under a variety of conditions on the coupling of Y and Y(s), including combinations of boundedness and monotonicity, concentration of measure inequalities such as
P(Y-mu/sigma >= t) <= exp (-t(2)/2(A+Bt) for all t >= 0
are shown to hold for some explicit A and B in [8]. Such concentration of measure results are applied to a number of new examples: the number of relatively ordered subsequences of a random permutation, sliding window statistics including the number of m-runs in a sequence of coin tosses, the number of local maxima of a random function on a lattice, the number of urns containing exactly one ball in an urn allocation model, and the volume covered by the union of n balls placed uniformly over a volume n subset of R(d).

• 出版日期2011-1-23