Concentration inequalities in spaces of random configurations with positive Ricci curvatures

2019/06/09 by Linyuan Lü, Zhiyu Wang, Lu, Linyuan +1
Mathematics · #Geometric Analysis and Curvature Flows #Point processes and geometric inequalities #Geometry and complex manifolds

paper · pdf · doi:10.48550/arxiv.1906.03550

Abstract

In this paper, we prove an Azuma-Hoeffding-type inequality in several classical models of random configurations, including the Erdős-Rényi 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 ν) with Ricci curvature at least κ>0, we have ν( |f-E_νf| ≥ t ) ≤ 2exp( -(t²κ)/(7) ).

Citations

• Ricci curvature for metric-measure spaces via optimal transport
• Gradient flows of the entropy for finite Markov chains
• Ricci curvature of Markov chains on metric spaces

Related

• Mixing and Concentration by Ricci Curvature
• Ricci curvature of Markov chains on metric spaces
• Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings
• A concentration theorem for the equilibrium measure of Markov chains with nonnegative coarse Ricci curvature
• Concentration of empirical barycenters in metric spaces