Concentration inequalities in spaces of random configurations with positive Ricci curvatures

DOI10.4310/PAMQ.2022.V18.N6.A11MaRDI QIDQ6320188arXivFDO

Authors Linyuan Lu, Zhiyu Wang

Publication date 8 June 2019

Mathematics Subject Classification ID

Large deviations (60F10) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81) Local Riemannian geometry (53B20)

Abstract: In this paper, we prove an Azuma-Hoeffding-type inequality in several classical models of random configurations, including the ErdH{o}s-R'enyi random graph models $G(n,p)$ and $G(n,M)$, the random $d$-out(in)-regular directed graphs, and the space of random permutations. The main idea is using Ollivier's work on the Ricci curvature of Markov chairs on metric spaces. Here we give a cleaner form of such 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 $u$) with Ricci curvature at least $kappa>0$, we have [

u left( |f-E_{

u}f| geq t ight) leq 2expleft( -frac{t^2kappa}{7} ight).]

This page was built for publication: Concentration inequalities in spaces of random configurations with positive Ricci curvatures

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