The full text of this article is unavailable through your IP address: 3.141.198.75
Contents Online
Pure and Applied Mathematics Quarterly
Volume 18 (2022)
Number 6
Special issue in honor of Fan Chung
Guest editors: Paul Horn, Yong Lin, and Linyuan Lu
Concentration inequalities in spaces of random configurations with positive Ricci curvatures
Pages: 2569 – 2598
DOI: https://dx.doi.org/10.4310/PAMQ.2022.v18.n6.a11
Authors
Abstract
In this paper, we prove an Azuma–Hoeffding-type inequality in several classical models of random configurations by a Ricci curvature approach. Adapting Ollivier’s work on the Ricci curvature of Markov chains on metric spaces, we prove a cleaner form of the corresponding concentration inequality in graphs. Namely, we show that for any Lipschitz function $f$ on any graph (equipped with an ergodic random walk and thus an invariant distribution $\nu$) with Ricci curvature at least $\kappa \gt 0$, we have\[\nu (\lvert f - E_\nu f \rvert \geq t) \leq 2 \exp \left( - \dfrac{t^2 \kappa}{7} \right) \: \textrm{.}\]
Keywords
Ricci curvature, concentration inequality, random graphs
2010 Mathematics Subject Classification
Primary 05C81. Secondary 53C44, 60F10.
The first-named author was supported in part by NSF grant DMS-1600811 and NSF DMS-2038080.
Received 27 May 2021
Received revised 3 June 2022
Accepted 10 November 2022
Published 29 March 2023