Concentration of measures via size biased couplings

2009/06/21 by Ghosh, Subhankar, Goldstein, Larry
#60C05 #60E15 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.0906.3886

Abstract

Let Y be a nonnegative random variable with mean μ and finite positive variance σ², 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)]=μE f(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 hold. Examples include 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 maximum of a random function on a lattice, the number of urns containing exactly one ball in an urn allocation model, the volume covered by the union of n balls placed uniformly over a volume n subset of d dimensional Euclidean space, the number of bulbs switched on at the terminal time in the so called lightbulb process, and the infinitely divisible and compound Poisson distributions that satisfy a bounded moment generating function condition.

Related

• Bounded size bias coupling: a Gamma function bound, and universal Dickman-function behavior
• Multivariate Concentration Inequalities with Size Biased Couplings
• Bounded size biased couplings, log concave distributions and\n concentration of measure for occupancy models
• Concentration inequalities for random fields via coupling
• Multivariate concentration of measure type results using exchangeable pairs and size biasing