Press "Enter" to skip to content

Month: January 2011

Curvature on discrete spaces

Let us consider an infinite continuous or discrete metric space \((S,d)\) equipped with a probability measure \(\mu\).  For instance a Riemannian manifold with a potential,  such as the sphere equipped with its uniform measure, or \(\mathbb{R}^n\) equipped with the Gaussian measure. One of the most studied problems are the concentration of measure phenomenon for \(\mu\)  and the numerical simulation of \(\mu\). To address these problems, one may introduce an auxiliary Markov process  \((X_t)_{t\geq0}\)  on \(S\) which admits \(\mu\) as an invariant distribution (e.g. the Brownian motion on the sphere and the Ornstein-Uhlenbeck process on \(\mathbb{R}^n\)). Perhaps the most famous instance of the approach is the Metropolis-Hastings simulation algorithm (Monte Carlo Markov Chain).

The speed of convergence of  \((X_t)_{t\geq0}\) to \(\mu\) in entropy can be related to the concentration of measure of \(\mu\). In the case of a Riemannian manifold, this can be related to a notion of curvature taking into account both the geometry (Ricci) of the manifold and the Markov dynamics. It is known as the Bakry-Émery curvature. By using Wasserstein coupling instead of entropy, Ollivier extended this notion of curvature to discrete spaces (there are some connections with ideas of M.-F. Chen, Joulin, Villani, Lott, and Sturm). This allows primarily to control the concentration of measure of \(\mu\). From this point of view the Markov process is instrumental.

If however one has a specific  Markov process of interest (coming from computer science, mathematical biology, or mathematical physics) for which the question is to study the speed of convergence to the equilibrium in entropy, then the curvature of Ollivier seems useless because Wasserstein coupling decay does not  give entropy decay in general (it does for elliptic Markov diffusions). To our knowledge, for birth and death processes, a good notion of curvature for the decay of entropy was developed by Caputo, Dai Pra, and Posta, and relies only on commutation and convexity as in the Bakry-Émery approach. To our knowledge, there is a lack of a good notion of curvature for the decay of entropy for multidimensional discrete processes.

1 Comment
Syntax · Style · .