Mixing and concentration by Ricci curvature

DOI10.1016/J.JFA.2015.12.010zbMATH Open1335.60135arXiv1404.2802OpenAlexW2963967990MaRDI QIDQ905875FDOQ905875

Authors: Daniel Paulin 

Publication date: 28 January 2016

Published in: Journal of Functional Analysis (Search for Journal in Brave)

Abstract: We generalise the coarse Ricci curvature method of Ollivier by considering the coarse Ricci curvature of multiple steps in the Markov chain. This implies new spectral bounds and concentration inequalities. We also extend this approach to the bounds for MCMC empirical averages obtained by Joulin and Ollivier. We prove a recursive lower bound on the coarse Ricci curvature of multiple steps in the Markov chain, making our method broadly applicable. Applications include the split-merge random walk on partitions, Glauber dynamics with random scan and systemic scan for statistical physical spin models, and random walk on a binary cube with a forbidden region.

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

Recommendations

• A concentration phenomenon in mean curvature flow
• scientific article; zbMATH DE number 6389773
• Diffusion, optimal transport and Ricci curvature
• Mixed integral norms for Ricci flow
• Concentration inequalities in spaces of random configurations with positive Ricci curvatures
• Concentration, Ricci curvature, and eigenvalues of Laplacian
• Curvature cones and the Ricci flow
• Ricci curvature and volume convergence
• Concentration of solutions for the mean curvature problem
• Ricci curvature, entropy, and optimal transport

zbMATH Keywords

Markov chainconcentration inequalityRicci curvature

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) Inequalities; stochastic orderings (60E15) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Discrete-time Markov processes on general state spaces (60J05)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• The concentration of measure phenomenon
• Ricci curvature for metric-measure spaces via optimal transport
• On the geometry of metric measure spaces. I
• Generating a random permutation with random transpositions
• Ricci curvature of Markov chains on metric spaces
• Concentration of measure and isoperimetric inequalities in product spaces
• Nonnormal approximation by Stein's method of exchangeable pairs with application to the Curie-Weiss model
• Prescribing a System of Random Variables by Conditional Distributions
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
• Properties of isoperimetric, functional and transport-entropy inequalities via concentration
• Title not available (Why is that?)
• A visual introduction to Riemannian curvatures and some discrete generalizations
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Explicit error bounds for lazy reversible Markov chain Monte Carlo
• Sharp isoperimetric inequalities and model spaces for the curvature-dimension-diameter condition
• The mixing time evolution of Glauber dynamics for the mean-field Ising model
• A survey of Ricci curvature for metric spaces and Markov chains
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• A new Poisson-type deviation inequality for Markov jump processes with positive Wasserstein curvature
• Applications of Stein's method for concentration inequalities
• Mixing time of exponential random graphs
• Dobrushin Conditions and Systematic Scan
• Title not available (Why is that?)
• Poincaré and transportation inequalities for Gibbs measures under the Dobrushin uniqueness condition
• Explicit error bounds for Markov chain Monte Carlo
• The Poisson-Dirichlet law is the unique invariant distribution for uniform split-merge transfor\-mations.
• Concentration of measure and mixing for Markov chains
• Title not available (Why is that?)
• Computation of expectations by Markov chain Monte Carlo methods

Cited In (15)

• A weighted discrepancy bound of quasi-Monte Carlo importance sampling
• Coarse Ricci curvature of quantum channels
• Lower bound for the coarse Ricci curvature of continuous-time pure-jump processes
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Discrete Ricci curvature bounds for Bernoulli-Laplace and random transposition models
• Transport-information inequalities for Markov chains
• Kuzmin, coupling, cones, and exponential mixing
• Strict Kantorovich contractions for Markov chains and Euler schemes with general noise
• Long-term concentration of measure and cut-off
• Empirical measures: regularity is a counter-curse to dimensionality
• Cutoff for conjugacy-invariant random walks on the permutation group
• Mixing time and expansion of non-negatively curved Markov chains
• Quantitative contraction rates for Markov chains on general state spaces
• Transportation Distance between Probability Measures on the Infinite Regular Tree
• Ricci curvature bounds for weakly interacting Markov chains

This page was built for publication: Mixing and concentration by Ricci curvature

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