×

Ricci curvature of Markov chains on metric spaces. (English) Zbl 1181.53015

Let \(x\) and \(y\) be two points in a Riemannian manifold \(M\). Let \(w\) be a tangent vector at \(x\), let \(w'\) be the tangent vector at \(y\) obtained by parallel transport of \(w\) from \(x\) to \(y\). If one follows the two geodesics issuing from \(x, w\) and \(y,w'\), in positive curvature the geodesics will get closer and will part away in negative curvature. Starting from this approach of Ricci curvature, the author notices that if one thinks of a direction \(w\) at \(x\) as a point on a small sphere \(S_x\) centered at \(x\), on average, the Ricci curvature controls wether the distance between a point of \(S_x\) and the corresponding point of \(S_y\), is smaller or larger than the distance from \(x\) to \(y\). Let \((X,d)\) be a polish metric space. In \(X\) one can define a random walk as a family of probabilistic measures \(m_x(.)\) on X for each \(x\in X\)satisfying some assumptions.
So now the idea is to replace the notion of “corresponding points” between two closed spheres by transportation distance between measures. The \(L^1\) transportation distance between two probability measures \(\nu_1\) and \(\nu_2\) in \(X\) will be given by \(W_1(\nu_1,\nu_2):=\inf \int_{(x,y)\in X\times X} d(x,y)d\xi (x,y)\) and the infimum is taken over the set of measures in \(X\times X\) projecting to \(\nu_1\) and \(\nu_2\) . The fact that the measures of the random walk are closer or further apart than the points \(x\) and \(y\) will give the sign of the Ricci curvature.
Coarse Ricci curvature \(\kappa (x,y)\) is defined for a metric space \((X,d)\) with a random walk \(m\). Let \(x\) and \(y\) be two points of \(X\), then \(\kappa (x,y):=1-\frac{W_1(\nu_1,\nu_2)}{d(x,y)}\).
According to the author “geometers will think of \(m_x\) as a replacement for the notion of ball around \(x\). Probabilists will rather think of this data as defining a Markov chain with a specific transition probability from \(x\) to \(y\)”.
With this approach to Ricci curvature, the Ricci curvature is positive if and only if the random walk operator is contracting on the space of probability measure with the transportation metric. This generalization is consistent with the Bakry-Émery Ricci curvature for Brownian motion with a drift on a Riemannian manifold (see abstract).
The article includes an introduction that includes historical remarks and related work. It also includes one section with definitions and statements and one on elementary properties that will help the reader to get into this perspective since it includes lots of examples. The author proceeds with sections devoted to concentration results, local control and logarithmic Sobolev inequality, exponential concentration in non-negative curvature, \(L^2\) Bonnet-Myers theorems, coarse Ricci curvature and Gromov-Hausdorff topology, and transportation distance in Riemannian manifolds.

MSC:

53B20 Local Riemannian geometry
54E35 Metric spaces, metrizability
53C23 Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces
60J99 Markov processes

Citations:

Zbl 1132.53011
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ané, C.; Blachère, S.; Chafaï, D.; Fougères, P.; Gentil, I.; Malrieu, F.; Roberto, C.; Scheffer, G., Sur les Inégalités de Sobolev Logarithmiques, Panor. Synthèses, vol. 10 (2000), Société Mathématique de France · Zbl 0982.46026
[2] Arnold, A.; Markowich, P.; Toscani, G.; Unterreiter, A., On convex Sobolev inequalities and the rate of convergence to equilibrium for Fokker-Planck type equations, Comm. Partial Differential Equations, 26, 1-2, 43-100 (2001) · Zbl 0982.35113
[3] Burago, D.; Burago, Y.; Ivanov, S., A Course in Metric Geometry, Grad. Stud. Math., vol. 33 (2001), Amer. Math. Soc. · Zbl 0981.51016
[4] Bubley, R.; Dyer, M. E., Path coupling: A technique for proving rapid mixing in Markov chains, Found. Comput. Sci., 223-231 (1997)
[5] Bakry, D.; Émery, M., Hypercontractivité de semi-groupes de diffusion, C. R. Math. Acad. Sci. Paris Sér. I, 299, 15, 775-778 (1984) · Zbl 0563.60068
[6] Bakry, D.; Émery, M., Diffusions hypercontractives, (Séminaire de Probabilités, XIX, 1983/1984. Séminaire de Probabilités, XIX, 1983/1984, Lecture Notes in Math., vol. 1123 (1985), Springer: Springer Berlin), 177-206 · Zbl 0561.60080
[7] Berger, M., A Panoramic View of Riemannian Geometry (2003), Springer: Springer Berlin · Zbl 1038.53002
[8] Bobkov, S.; Ledoux, M., On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures, J. Funct. Anal., 156, 2, 347-365 (1998) · Zbl 0920.60002
[9] Brémaud, P., Markov Chains, Texts Appl. Math., vol. 31 (1999), Springer: Springer New York · Zbl 0949.60009
[10] A.-I. Bonciocat, K.-T. Sturm, Mass transportation and rough curvature bounds for discrete spaces, preprint; A.-I. Bonciocat, K.-T. Sturm, Mass transportation and rough curvature bounds for discrete spaces, preprint · Zbl 1184.28015
[11] Chen, M.-F., Trilogy of couplings and general formulas for lower bound of spectral gap, (Probability Towards 2000. Probability Towards 2000, New York, 1995. Probability Towards 2000. Probability Towards 2000, New York, 1995, Lecture Notes in Statist., vol. 128 (1998), Springer: Springer New York), 123-136 · Zbl 1044.60513
[12] Chen, M.-F., From Markov Chains to Non-Equilibrium Particle Systems (2004), World Scientific · Zbl 1078.60003
[13] Chen, M.-F.; Li, S.-F., Coupling methods for multidimensional diffusion processes, Ann. Probab., 17, 1, 151-177 (1989) · Zbl 0686.60083
[14] Chen, M.-F.; Wang, F.-Y., Application of coupling method to the first eigenvalue on manifold, Sci. China Ser. A, 37, 1, 1-14 (1994) · Zbl 0799.53044
[15] Djellout, H.; Guillin, A.; Wu, L., Transportation cost-information inequalities and applications to random dynamical systems and diffusions, Ann. Probab., 32, 3B, 2702-2732 (2004) · Zbl 1061.60011
[16] Dobrušin, R. L., On the condition of the central limit theorem for inhomogeneous Markov chains, Dokl. Akad. Nauk SSSR (N.S.), 108, 1004-1006 (1956), (in Russian) · Zbl 0074.34002
[17] Dobrushin, R., Central limit theorem for non-stationary Markov chains I, Teor. Veroyatnost. i Primenen., 1, 72-89 (1956), (in Russian) · Zbl 0093.15001
[18] Dobrušin, R. L., Definition of a system of random variables by means of conditional distributions, Teor. Verojatnost. i Primenen., 15, 469-497 (1970), (in Russian) · Zbl 0264.60037
[19] Dobrushin, R., Perturbation methods of the theory of Gibbsian fields, (Dobrushin, R.; Groeneboom, P.; Ledoux, M.; Bernard, P., Lectures on Probability Theory and Statistics, Lectures from the 24th Saint-Flour Summer School held July 7-23, 1994. Lectures on Probability Theory and Statistics, Lectures from the 24th Saint-Flour Summer School held July 7-23, 1994, Lecture Notes in Math., vol. 1648 (1996), Springer: Springer Berlin), 1-66 · Zbl 0871.60086
[20] Dobrushin, R. L.; Shlosman, S. B., Constructive criterion for the uniqueness of Gibbs field, (Fritz, J.; Jaffe, A.; Szász, D., Statistical Physics and Dynamical Systems, papers from the Second Colloquium and Workshop on Random Fields: Rigorous Results in Statistical Mechanics, held in Köszeg. Statistical Physics and Dynamical Systems, papers from the Second Colloquium and Workshop on Random Fields: Rigorous Results in Statistical Mechanics, held in Köszeg, August 26-September 1, 1984. Statistical Physics and Dynamical Systems, papers from the Second Colloquium and Workshop on Random Fields: Rigorous Results in Statistical Mechanics, held in Köszeg. Statistical Physics and Dynamical Systems, papers from the Second Colloquium and Workshop on Random Fields: Rigorous Results in Statistical Mechanics, held in Köszeg, August 26-September 1, 1984, Progress in Phys., vol. 10 (1985), Birkhäuser: Birkhäuser Boston), 347-370 · Zbl 0569.46042
[21] Diaconis, P.; Saloff-Coste, L., Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab., 6, 3, 695-750 (1996) · Zbl 0867.60043
[22] Dembo, A.; Zeitouni, O., Large Deviations Techniques and Applications, Appl. Math., vol. 38 (1998), Springer: Springer New York · Zbl 0896.60013
[23] Granas, A.; Dugundji, J., Fixed Point Theory, Springer Monogr. Math. (2003), Springer: Springer New York · Zbl 1025.47002
[24] Ghys, É.; de la Harpe, P., Sur les Groupes Hyperboliques d’Après Mikhael Gromov, Progr. Math., vol. 83 (1990), Birkhäuser · Zbl 0731.20025
[25] Gromov, M.; Milman, V., A topological application of the isoperimetric inequality, Amer. J. Math., 105, 843-854 (1983) · Zbl 0522.53039
[26] Griffiths, R. B., Correlations in Ising ferromagnets III, Commun. Math. Phys., 6, 121-127 (1967)
[27] Gromov, M., Isoperimetric inequalities in Riemannian manifolds, (Milman, V.; Schechtman, G., Asymptotic Theory of Finite Dimensional Normed Spaces. Asymptotic Theory of Finite Dimensional Normed Spaces, Lecture Notes in Math., vol. 1200 (1986), Springer: Springer Berlin), 114-129 · Zbl 0606.46013
[28] Joulin, A., Poisson-type deviation inequalities for curved continuous time Markov chains, Bernoulli, 13, 3, 782-798 (2007) · Zbl 1131.60069
[29] Ledoux, M., The Concentration of Measure Phenomenon, Math. Surveys Monogr., vol. 89 (2001), Amer. Math. Soc. · Zbl 0995.60002
[30] J. Lott, Optimal transport and Ricci curvature for metric-measure spaces, expository manuscript; J. Lott, Optimal transport and Ricci curvature for metric-measure spaces, expository manuscript · Zbl 1155.53026
[31] J. Lott, C. Villani, Ricci curvature for metric-measure spaces via optimal transport, preprint; J. Lott, C. Villani, Ricci curvature for metric-measure spaces via optimal transport, preprint · Zbl 1178.53038
[32] Marton, K., Bounding \(\overline{d} \)-distance by informational divergence: A method to prove measure concentration, Ann. Probab., 24, 2, 857-866 (1996) · Zbl 0865.60017
[33] Marton, K., A measure concentration inequality for contracting Markov chains, Geom. Funct. Anal.. Geom. Funct. Anal., Geom. Funct. Anal., 7, 3, 609-613 (1997), Erratum · Zbl 0895.60073
[34] Martinelli, F., Relaxation times of Markov chains in statistical mechanics and combinatorial structures, (Kesten, H., Probability on Discrete Structures. Probability on Discrete Structures, Encyclopaedia Math. Sci., vol. 110 (2004), Springer: Springer Berlin), 175-262 · Zbl 1206.82058
[35] Milman, V.; Schechtman, G., Asymptotic Theory of Finite Dimensional Normed Spaces, Lecture Notes in Math., vol. 1200 (1986), Springer: Springer Berlin · Zbl 0606.46013
[36] M. Hazewinkel, The Online Encyclopaedia of Mathematics, article Wasserstein metric, http://eom.springer.de/W/w120020.htm; M. Hazewinkel, The Online Encyclopaedia of Mathematics, article Wasserstein metric, http://eom.springer.de/W/w120020.htm
[37] Ohta, S.-i., On the measure contraction property of metric measure spaces, Comment. Math. Helv., 82, 4, 805-828 (2007) · Zbl 1176.28016
[38] R. Imbuzeiro Oliveira, On the convergence to equilibrium of Kac’s random walk on matrices, preprint, arXiv: 0705.2253; R. Imbuzeiro Oliveira, On the convergence to equilibrium of Kac’s random walk on matrices, preprint, arXiv: 0705.2253 · Zbl 1173.60343
[39] Ollivier, Y., Sharp phase transition theorems for hyperbolicity of random groups, Geom. Funct. Anal., 14, 3, 595-679 (2004) · Zbl 1064.20045
[40] Ollivier, Y., Ricci curvature of metric spaces, C. R. Math. Acad. Sci. Paris, 345, 11, 643-646 (2007) · Zbl 1132.53011
[41] Otto, F.; Villani, C., Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality, J. Funct. Anal., 173, 361-400 (2000) · Zbl 0985.58019
[42] Y. Peres, Mixing for Markov chains and spin systems, Lecture Notes, 2005; Y. Peres, Mixing for Markov chains and spin systems, Lecture Notes, 2005
[43] von Renesse, M.-K.; Sturm, K.-T., Transport inequalities, gradient estimates, and Ricci curvature, Comm. Pure Appl. Math., 68, 923-940 (2005) · Zbl 1078.53028
[44] M.D. Sammer, Aspects of mass transportation in discrete concentration inequalities, PhD thesis, Georgia institute of technology, 2005, etd.gatech.edu/theses/available/etd-04112005-163457/unrestricted/sammer_marcus_d_200505_phd.pdf; M.D. Sammer, Aspects of mass transportation in discrete concentration inequalities, PhD thesis, Georgia institute of technology, 2005, etd.gatech.edu/theses/available/etd-04112005-163457/unrestricted/sammer_marcus_d_200505_phd.pdf
[45] Schechtman, G., Concentration, results and applications, (Handbook of the Geometry of Banach Spaces, vol. 2 (2003), North-Holland: North-Holland Amsterdam), 1603-1634 · Zbl 1057.46011
[46] Sturm, K.-T., On the geometry of metric measure spaces, Acta Math., 196, 1, 65-177 (2006) · Zbl 1106.53032
[47] Villani, C., Topics in Optimal Transportation, Grad. Stud. Math., vol. 58 (2003), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI · Zbl 1106.90001
[48] Villani, C., Optimal Transport, Old and New, Grundlehren Math. Wiss., vol. 338 (2008), Springer · Zbl 1158.53036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.