When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence

DOI10.1016/J.SPL.2021.109272MaRDI QIDQ2070641zbMATH OpenOpenAlexFDO

Authors Rui-Ray Zhang

Publication date 24 January 2022

Published in Statistics \& Probability Letters (Search for Journal in Brave)

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

zbMATH Keywords

concentration inequalitiesdependency graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Inequalities; stochastic orderings (60E15) Central limit and other weak theorems (60F05) Stationary stochastic processes (60G10)

Abstract: We establish concentration inequalities for Lipschitz functions of dependent random variables, whose dependencies are specified by forests. We also give concentration results for decomposable functions, improving Janson's Hoeffding-type inequality for the summation of graph-dependent bounded variables. These results extend McDiarmid's bounded difference inequality to the dependent cases.

Recommendations

• Variations on McClelland's bound for graph energy
• Bounds on the differential of a graph
• Lower bounds on the differential of a graph
• The McClelland inequality for the energy of digraphs
• Discrepancy inequalities for directed graphs
• scientific article; zbMATH DE number 3982159
• On variants of the Johnson–Lindenstrauss lemma
• From Hardy to Rellich inequalities on graphs
• Remarks on Li-Yau inequality on graphs
• Harnack type inequality on graphs

Cites work

• scientific article; zbMATH DE number 4212111 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3438144 (Why is no real title available?)
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Concentration inequalities for dependent random variables via the martingale method
• Concentration inequalities. A nonasymptotic theory of independence
• Concentration of measure inequalities for Markov chains and \(\Phi\)-mixing processes.
• Concentration of measure without independence: a unified approach via the martingale method
• Extreme value theory for triangular arrays of dependent random variables
• Large deviations for sums of partly dependent random variables
• Measure concentration and strong mixing
• Normal approximation under local dependence.
• Normal convergence by higher semi-invariants with applications to sums of dependent random variables and random graphs
• On 1-dependent processes and k-block factors
• On normal approximations of distributions in terms of dependency graphs
• Poisson approximation for dependent trials
• Poisson approximation for large deviations
• The Central Limit Theorem for a Sequence of Random Variables with a Slowly Growing Number of Dependences
• The central limit theorem for dependent random variables

Cited in

(2)

• On the method of typical bounded differences
• Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence

This page was built for publication: When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence

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