Displacement convexity of entropy and related inequalities on graphs

DOI10.1007/S00440-013-0523-YMaRDI QIDQ466893zbMATH OpenOpenAlexFDO

Authors N. Gozlan, Prasad Tetali, C. Roberto, P.-M. Samson

Publication date 31 October 2014

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

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

displacement convexity modified logarithmic-Sobolev inequalities relative entropy Ricci curvature transport inequalities

Mathematics Subject Classification ID

Analytical consequences of geometric convexity (vanishing theorems, etc.) (32F32) Discrete version of topics in analysis (39A12) Inequalities; stochastic orderings (60E15)

Abstract: We introduce the notion of an interpolating path on the set of probability measures on finite graphs. Using this notion, we first prove a displacement convexity property of entropy along such a path and derive Prekopa-Leindler type inequalities, a Talagrand transport-entropy inequality, certain HWI type as well as log-Sobolev type inequalities in discrete settings. To illustrate through examples, we apply our results to the complete graph and to the hypercube for which our results are optimal -- by passing to the limit, we recover the classical log-Sobolev inequality for the standard Gaussian measure with the optimal constant.

Review text

In recent years, there has been a great interest in developing a notion of Ricci curvature in the setting of discrete spaces, i.e., finite graphs or finite Markov chains. A fruitful direction has been one where Ricci curvature is defined via convexity properties of the relative entropy regarded as a function on the space of probability measures equipped with a \(L_p\)-Wasserstein metric or a related metric. The study of convexity properties of relative entropy is important because of its connection to several geometric and function inequalities, and several approaches to extend this theory to discrete settings have been proposed. One which uses a pseudo Wasserstein metric was developed in [\textit{J. Maas}, J. Funct. Anal. 261, No. 8, 2250--2292 (2011; Zbl 1237.60058)] and [\textit{M. Erbar} and \textit{J. Maas}, Arch. Ration. Mech. Anal. 206, No. 3, 997--1038 (2012; Zbl 1256.53028)]. Consider the discrete hypercube \(X = \{0,1\}^n\), and let \(\nu\) be the uniform probability measure on \(X\). \textit{Y. Ollivier} and \textit{C. Villani} [SIAM J. Discrete Math. 26, No. 3, 983--996 (2012; Zbl 1267.52010)] proved that, for any probability measures \(\mu_0\) and \(\mu_1\) in \(X\), one can construct a probability measure \(\mu_{1/2}\) on the set of midpoints of the supports of \(\mu_0\) and \(\mu_1\) such that \[ H(\mu_{1/2}|\nu) \leq \frac{1}{2}\, H(\mu_0|\nu) + \frac{1}{2}\, H(\mu_1|\nu) - \frac{1}{16n}\, W_1(\mu_0,\mu_1)^2, \] where \(H(\cdot|\nu)\) denotes relative entropy, and \(W_1\) denotes the \(L_1\)-Wasserstein distance. In this article, the authors propose another interpolation between probability measures and derive a similar inequality which holds in a more general setting. More precisely, let \(G\) be a finite graph with vertex set \(V\). For any two vertices \(x\) and \(y\), the authors define a path \(\mu_t^{x,y}\) between the corresponding delta measures \(\delta_x\) and \(\delta_y\) based on a binomial interpolation. The definition of \(\mu_t^{x,y}\) includes the contribution of all the geodesics from \(x\) to \(y\). From this, they construct a path between any two probability measures on \(V\). That is, let \(\mu_0\) and \(\mu_1\) be any two probability measures on \(V\). For any coupling \(\pi\) of \(\mu_0\) and \(\mu_1\), the authors define a path \(\mu_t^{\pi}\) from \(\mu_0\) to \(\mu_1\) by \[ \mu_t^{\pi} (\cdot) = \sum_{(x,y)\in V^2} \pi (x,y) \mu_t^{x,y}(\cdot) ,\quad \text{for all } t \in [0,1]. \] Using this new notion the authors derive a displacement convexity of entropy inequality with respect to the \(L_1\)-Wasserstein-metric on the complete graph and products of complete graphs, and from this result they derive several important inequalities, i.e., a discrete version of the Prékopa-Leindler type inequalities, and HWI type inequalities on graphs. In particular, for the discrete hypercube, they prove the following result: Theorem. Let \(\mu\) be a probability on \(\{0,1\}\), and denote by \(\mu^{\otimes n}\) its \(n\)-fold product on \(X\). Then, for any two probability measures \(\mu_0\) and \(\mu_1\) on \(X\), there exists a coupling \(\pi\) of \(\mu_0\) and \(\mu_1\) such that, for all \(t\in [0,1]\), \[ H(\mu_t^{\pi}|\mu^{\otimes n}) \leq (1-t) H (\mu_0|\mu^{\otimes n}) + t H(\mu_1| \mu^{\otimes n}) - \frac{2t(1-t)}{n} W_1(\mu_0,\mu_1)^2. \] In the introduction, the authors provide an overview of known results with extensive references for both continuous and discrete settings. A related work which uses another type of binomial interpolation can be found in [\textit{E. Hillion}, Potential Anal. 41, No. 3, 679--698 (2014; Zbl 1305.60014)].

Recommendations

Cites work

Cited in

(33)

This page was built for publication: Displacement convexity of entropy and related inequalities on graphs

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