Concentration inequalities in spaces of random configurations with positive Ricci curvatures

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.

Full Text (PDF format)

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