Local tail bounds for functions of independent random variables

DOI10.1214/00911797000000088MaRDI QIDQ2468424zbMATH OpenOpenAlexFDO

Authors Gábor Lugosi, Luc Devroye

Publication date 22 January 2008

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0712.1686, https://projecteuclid.org/euclid.aop/1196268676

zbMATH Keywords

concentration inequalitiesconfiguration functionsconvex distancehypercontractivityTalagrand's inequality

Mathematics Subject Classification ID

Large deviations (60F10)

Abstract: It is shown that functions defined on ${0,1,\mathrm{...},r-1}^n$ satisfying certain conditions of bounded differences that guarantee sub-Gaussian tail behavior also satisfy a much stronger ``local sub-Gaussian property. For self-bounding and configuration functions we derive analogous locally subexponential behavior. The key tool is Talagrand's [Ann. Probab. 22 (1994) 1576--1587] variance inequality for functions defined on the binary hypercube which we extend to functions of uniformly distributed random variables defined on ${0,1,\mathrm{...},r-1}^n$ for $rge2$.

Recommendations

• scientific article; zbMATH DE number 3901725
• Local Limit Theorems for Functionals of Random Processes
• scientific article; zbMATH DE number 4092475
• scientific article; zbMATH DE number 4054691
• scientific article; zbMATH DE number 4137114
• scientific article; zbMATH DE number 4038918
• Local limit theorems for functionals in the conditional invariance principle
• Local limit theorems for the density of the maximum of sums of independent random variables
• Local Probabilities for Sums of Independent Random Variables
• Аппроксимация локальных вероятностей сумм независимых случайных величин

Cites work

• A new look at independence
• A proof of Parisi's conjecture on the random assignment problem
• A sharp concentration inequality with applications
• An Efron-Stein inequality for nonsymmetric statistics
• Concentration for self-bounding functions and an inequality of Talagrand
• Concentration inequalities for functions of independent variables
• Concentration inequalities using the entropy method
• Concentration of measure and isoperimetric inequalities in product spaces
• Discrete orthogonal polynomial ensembles and the Plancherel measure
• First passage percolation has sublinear distance variance.
• Graph products, Fourier analysis and spectral techniques
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3902655 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 522891 (Why is no real title available?)
• Inequalities in Fourier analysis
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• Logarithmic Sobolev inequalities for finite Markov chains
• Martingale inequalities and the jackknife estimate of variance
• New concentration inequalities in product spaces
• On Russo's approximate zero-one law
• On Talagrand's deviation inequalities for product measures
• On the concentration of eigenvalues of random symmetric matrices
• On the distributions of the lengths of the longest monotone subsequences in random words
• On the value of a random minimum spanning tree problem
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• Random words, Toeplitz determinants, and integrable systems. I
• The (2) limit in the random assignment problem
• The concentration of measure phenomenon
• The eigenvalues of random symmetric matrices
• The jackknife estimate of variance
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)

Cited in

(5)

• Proof of Tomaszewski's conjecture on randomly signed sums
• A tail bound for read-k families of functions
• Solving optimal stopping problems via empirical dual optimization
• Biased halfspaces, noise sensitivity, and local Chernoff inequalities
• Local tail bounds for polynomials on the discrete cube

This page was built for publication: Local tail bounds for functions of independent random variables

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