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

DOI10.1016/J.SPL.2021.109272zbMATH Open1478.60095arXiv2110.05374OpenAlexW3206825499MaRDI QIDQ2070641FDOQ2070641

Authors: Rui-Ray Zhang 

Publication date: 24 January 2022

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

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.

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

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

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)

Cites Work

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