Bounded size bias coupling: a gamma function bound, and universal Dickman-function behavior

DOI10.1007/S00440-014-0572-XMaRDI QIDQ495548zbMATH OpenOpenAlexFDO

Authors Richard Arratia, Peter H. Baxendale

Publication date 14 September 2015

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

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

zbMATH Keywords

concentration inequalitiescouplingsize biasChernoff-Hoeffding boundsDickman function

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15)

Abstract: Under the assumption that the distribution of a nonnegative random variable $X$ admits a bounded coupling with its size biased version, we prove simple and strong concentration bounds. In particular the upper tail probability is shown to decay at least as fast as the reciprocal of a Gamma function, guaranteeing a moment generating function that converges everywhere. The class of infinitely divisible distributions with finite mean, whose L'evy measure is supported on an interval contained in $[0,c]$ for some $c<infty$, forms a special case in which this upper bound is logarithmically sharp. In particular the asymptotic estimate for the Dickman function, that $ho(u)approx{u}^{-u}$ for large $u$, is shown to be universal for this class. A special case of our bounds arises when $X$ is a sum of independent random variables, each admitting a 1-bounded size bias coupling. In this case, our bounds are comparable to Chernoff--Hoeffding bounds; however, ours are broader in scope, sharper for the upper tail, and equal for the lower tail. We discuss emph{bounded} and emph{monotone} couplings, give a sandwich principle, and show how this gives an easy conceptual proof that any finite positive mean sum of independent Bernoulli random variables admits a 1-bounded coupling with the same conditioned to be nonzero.

Recommendations

• Applications of size biased couplings for concentration of measures
• Concentration of measures via size-biased couplings
• Non uniform exponential bounds on normal approximation by Stein's method and monotone size bias couplings
• Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models
• Concentration inequalities from monotone couplings for graphs, walks, trees and branching processes

Cites work

• scientific article; zbMATH DE number 3172038 (Why is no real title available?)
• scientific article; zbMATH DE number 3183467 (Why is no real title available?)
• scientific article; zbMATH DE number 1402217 (Why is no real title available?)
• scientific article; zbMATH DE number 1418383 (Why is no real title available?)
• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• A guided tour of Chernoff bounds
• Applications of Stein's method for concentration inequalities
• Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models
• Concentration of measures via size-biased couplings
• Distances of Probability Measures and Random Variables
• Gravitational interaction in seven-dimensional space-time
• Integers without large prime factors
• Logarithmic combinatorial structures: A probabilistic approach
• Multivariate normal approximations by Stein's method and size bias couplings
• Normal approximation for coverage models over binomial point processes
• Probability Inequalities for Sums of Bounded Random Variables
• Size bias for one and all
• Stein's method for concentration inequalities
• The Existence of Probability Measures with Given Marginals
• The concentration of measure phenomenon
• Weighted sums of certain dependent random variables

Cited in

(15)

• 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
• Error bounds in local limit theorems using Stein's method
• Applications of size biased couplings for concentration of measures
• Concentration of measures via size-biased couplings
• On the largest part size of low‐rank combinatorial assemblies
• Particle density in diffusion-limited annihilating systems
• Negative dependence and stochastic orderings
• A generalised Dickman distribution and the number of species in a negative binomial process model
• Concentration inequalities using approximate zero bias couplings with applications to Hoeffding’s statistic under the Ewens distribution
• Size biased couplings and the spectral gap for random regular graphs
• Concentration inequalities from monotone couplings for graphs, walks, trees and branching processes
• Central moment inequalities using Stein's method
• Relaxation of monotone coupling conditions: Poisson approximation and beyond

This page was built for publication: Bounded size bias coupling: a gamma function bound, and universal Dickman-function behavior

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