Concentration of measures via size-biased couplings

DOI10.1007/S00440-009-0253-3zbMATH Open1239.60011arXiv0906.3886OpenAlexW2077877142MaRDI QIDQ718869FDOQ718869

Authors: Subhankar Ghosh, Larry Goldstein 

Publication date: 27 September 2011

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: Let $Y$ be a nonnegative random variable with mean $mu$ and finite positive variance $sigm{a}^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 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.

Full work available at URL: https://arxiv.org/abs/0906.3886

Recommendations

• Applications of size biased couplings for concentration of measures
• Concentration inequalities via zero bias couplings
• Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models
• Bounded size bias coupling: a gamma function bound, and universal Dickman-function behavior
• Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings

zbMATH Keywords

Stein's methodLarge deviationssize-biased couplings

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15)

Cites Work

• The concentration of measure phenomenon
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Introduction to Stein's Method
• Multivariate normal approximations by Stein's method and size bias couplings
• Composition Markov chains of multinomial type
• CLT-related large deviation bounds based on Stein's method
• Stein's method for concentration inequalities
• A Berry-Esseen bound for the lightbulb process
• One bulb? two bulbs? how many bulbs light up? -- A discrete probability problem involving dermal patches

Cited In (23)

• Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models
• Size bias for one and all
• Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process
• Fundamentals of Stein's method
• Weighted Poincaré inequalities, concentration inequalities and tail bounds related to Stein kernels in dimension one
• Stein's method via induction
• Applications of size biased couplings for concentration of measures
• Particle density in diffusion-limited annihilating systems
• On the number of leaves in a random recursive tree
• On the second eigenvalue of random bipartite biregular graphs
• Zero bias enhanced Stein couplings
• Concentration inequalities using approximate zero bias couplings with applications to Hoeffding’s statistic under the Ewens distribution
• Bounded size bias coupling: a gamma function bound, and universal Dickman-function behavior
• The Bennett-Orlicz norm
• Stein's method for conditional central limit theorem
• A Berry-Esseen bound for the lightbulb process
• Size biased couplings and the spectral gap for random regular graphs
• A square bias transformation of probability distributions: some properties and applications
• Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings
• Concentration inequalities from monotone couplings for graphs, walks, trees and branching processes
• Non uniform exponential bounds on normal approximation by Stein's method and monotone size bias couplings
• Central moment inequalities using Stein's method
• Concentration inequalities via zero bias couplings

This page was built for publication: Concentration of measures via size-biased couplings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q718869)