Local tail bounds for functions of independent random variables

• 成果类型: Article
• 署名作者: Devroye, Luc; Lugosi, Gabor
• 署名单位: McGill University; Pompeu Fabra University; ICREA; Pompeu Fabra University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/00911797000000088
• 发表日期: 2008
• 页码: 143-159
• 关键词: Concentration Inequalities; jackknife estimate; spanning tree; eigenvalues; limit; graph

摘要

It is shown that functions defined on {0, 1,..., 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,..., r - 1}(n) for r >= 2.