Gradient flows of the entropy for finite Markov chains

DOI10.1016/J.JFA.2011.06.009MaRDI QIDQ719491zbMATH OpenOpenAlexWikidataFDO

Authors Jan Maas

Publication date 10 October 2011

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

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

zbMATH Keywords

gradient flowsMarkov chainsoptimal transportationWasserstein metric

Mathematics Subject Classification ID

Diffusion processes and stochastic analysis on manifolds (58J65) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Let K be an irreducible and reversible Markov kernel on a finite set X. We construct a metric W on the set of probability measures on X and show that with respect to this metric, the law of the continuous time Markov chain evolves as the gradient flow of the entropy. This result is a discrete counterpart of the Wasserstein gradient flow interpretation of the heat flow in R^n by Jordan, Kinderlehrer, and Otto (1998). The metric W is similar to, but different from, the L^2-Wasserstein metric, and is defined via a discrete variant of the Benamou-Brenier formula.

Review text

Let \(K\) be an irreducible and reversible Markov kernel on a finite set \(\mathcal{X}\), and consider the continuous time heat semigroup on \(\mathcal{X}\) associated with \(K\). It seems natural to ask whether the heat flow can also be identified as the gradient flow of an entropy functional with respect to some metric on the space of probability densities on \(\mathcal{X}\). The author argues that it is easily seen that the \(L^2\)-Wasserstein metric over a discrete space is not appropriate for this purpose; the metric derivative of the heat flow in the Wasserstein metric is typically infinite in a discrete setting, hence the heat flow cannot be interpret as the gradient flow of any functional in the \(L^2\)-Wasserstein metric. To address this issue, the author constructs a metric \(\mathcal{W}\) on the set of probability measures on \(\mathcal{X}\), which allows him to extend the interpretation of the heat flow as the gradient flow of the entropy to the setting of finite Markov chains. This result can be seen as a discrete counterpart of the Wasserstein gradient flow interpretation of the heat flow in \(\mathbb{R}^n\) by \textit{R. Jordan, D. Kinderlehrer} and \textit{F. Otto} [SIAM J. Math. Anal. 29, No. 1, 1--17 (1998; Zbl 0915.35120)]. Furthermore, the metric \(\mathcal{W}\) is similar to, but different from, the \(L^2\)-Wasserstein metric, and is defined via a discrete variant of the Benamou-Brenier formula.

Recommendations

• Ricci curvature and gradient flows of the entropy for jump processes
• On gradient structures for Markov chains and the passage to Wasserstein gradient flows
• Gradient flow structures for discrete porous medium equations
• Heat and entropy flows in Carnot groups
• Generalized Bakry-Émery curvature condition and equivalent entropic inequalities in groups
• Gradient flows on Wasserstein spaces over compact Alexandrov spaces
• A trajectorial approach to relative entropy dissipation of McKean-Vlasov diffusions: gradient flows and HWBI inequalities
• \{Euclidean, metric, and Wasserstein\} gradient flows: an overview
• Geodesic convexity of the relative entropy in reversible Markov chains
• q-heat flow and the gradient flow of the Renyi entropy in the p-Wasserstein space

Cites work

• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• A curved Brunn-Minkowski inequality on the discrete hypercube, or: what is the Ricci curvature of the discrete hypercube?
• A new class of transport distances between measures
• A note on diagonally dominant matrices
• Existence and stability for Fokker-Planck equations with log-concave reference measure
• Fokker-Planck equations for a free energy functional or Markov process on a graph
• Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality
• Gradient flows and diffusion semigroups in metric spaces under lower curvature bounds
• Gradient flows in metric spaces and in the space of probability measures
• Heat flow on Finsler manifolds
• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• Mass transportation and rough curvature bounds for discrete spaces
• Nonlinear mobility continuity equations and generalized displacement convexity
• On the geometry of metric measure spaces. II
• On the heat flow on metric measure spaces: existence, uniqueness and stability
• Optimal Transport
• Positive definite matrices
• Ricci curvature and eigenvalue estimate on locally finite graphs
• Ricci curvature for metric-measure spaces via optimal transport
• Ricci curvature of Markov chains on metric spaces
• Ricci curvature of metric spaces
• Riemannian geometry and geometric analysis
• THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
• The heat equation on manifolds as a gradient flow in the Wasserstein space
• The Variational Formulation of the Fokker--Planck Equation
• Wasserstein space over the Wiener space

Cited in

(only showing first 100 items - show all)

• On the geometry of geodesics in discrete optimal transport
• Computations of optimal transport distance with Fisher information regularization
• On quotients of spaces with Ricci curvature bounded below
• Entropy dissipation of Fokker-Planck equations on graphs
• Numerical analysis of a robust free energy diminishing finite volume scheme for parabolic equations with gradient structure
• Poincaré, modified logarithmic Sobolev and isoperimetric inequalities for Markov chains with non-negative Ricci curvature
• About the entropic structure of detailed balanced multi-species cross-diffusion equations
• Natural gradient via optimal transport
• Optimal transport over nonlinear systems via infinitesimal generators on graphs
• A discrete Schrödinger equation via optimal transport on graphs
• Variational methods for evolution. Abstracts from the workshop held November 12--18, 2017
• Canonical structure and orthogonality of forces and currents in irreversible Markov chains
• Ricci curvature of finite Markov chains via convexity of the entropy
• Gromov-Hausdorff limit of Wasserstein spaces on point clouds
• Population games and discrete optimal transport
• Ricci curvature for parametric statistics via optimal transport
• A discrete Bakry-Emery method and its application to the porous-medium equation
• Nonlocal-interaction equation on graphs: gradient flow structure and continuum limit
• Gradient flow formulations of discrete and continuous evolutionary models: a unifying perspective
• Entropy-information inequalities under curvature-dimension conditions for continuous-time Markov chains
• A multi-step Lagrangian scheme for spatially inhomogeneous evolutionary games
• Complete logarithmic Sobolev inequalities via Ricci curvature bounded below
• Jump processes as generalized gradient flows
• The entropy method under curvature-dimension conditions in the spirit of Bakry-Émery in the discrete setting of Markov chains
• Entropic curvature on graphs along Schrödinger bridges at zero temperature
• Data-driven gradient flows
• Data-driven efficient solvers for Langevin dynamics on manifold in high dimensions
• Gradient flows for bounded linear evolution equations
• Traditional and accelerated gradient descent for neural architecture search
• Semi-discrete optimization through semi-discrete optimal transport: a framework for neural architecture search
• Applications of optimal transportation in the natural sciences. Abstracts from the workshop held February 21--27, 2021 (online meeting)
• A probabilistic approach to convex \((\phi)\)-entropy decay for Markov chains
• Primal dual methods for Wasserstein gradient flows
• Transport information geometry: Riemannian calculus on probability simplex
• Gradient flow formulation of diffusion equations in the Wasserstein space over a metric graph
• Dynamical Schrödinger bridge problems on graphs
• Heat and entropy flows in Carnot groups
• The exchange-driven growth model: basic properties and longtime behavior
• Super Ricci flows for weighted graphs
• Homogenisation of one-dimensional discrete optimal transport
• A variational finite volume scheme for Wasserstein gradient flows
• Fisher information and logarithmic Sobolev inequality for matrix-valued functions
• Hopf-Cole transformation via generalized Schrödinger bridge problem
• Complete gradient estimates of quantum Markov semigroups
• What is a stochastic Hamiltonian process on finite graph? An optimal transport answer
• Curvature-dimension inequalities for non-local operators in the discrete setting
• Gradient flows and evolution variational inequalities in metric spaces. I: structural properties
• The heat flow on metric random walk spaces
• Computation of optimal transport on discrete metric measure spaces
• Gradient flow approach to local mean-field spin systems
• Non-commutative calculus, optimal transport and functional inequalities in dissipative quantum systems
• An inequality connecting entropy distance, Fisher information and large deviations
• A Benamou-Brenier formulation of martingale optimal transport
• Exponential decay of Rényi divergence under Fokker-Planck equations
• Gradient flow and entropy inequalities for quantum Markov semigroups with detailed balance
• An entropic gradient structure for Lindblad equations and couplings of quantum systems to macroscopic models
• Acceleration of convergence to equilibrium in Markov chains by breaking detailed balance
• Entropy dissipation semi-discretization schemes for Fokker-Planck equations
• A rough curvature-dimension condition for metric measure spaces
• On the curvature and heat flow on Hamiltonian systems
• Diffusion by optimal transport in Heisenberg groups
• Characterisation of gradient flows on finite state Markov chains
• On gradient structures for Markov chains and the passage to Wasserstein gradient flows
• Modeling of chemical reaction systems with detailed balance using gradient structures
• Operator-splitting schemes for degenerate, non-local, conservative-dissipative systems
• Curvature-dimension conditions for symmetric quantum Markov semigroups
• Computational mean-field games on manifolds
• Discrete versions of the transport equation and the Shepp-Olkin conjecture
• On uniform decay of the entropy for reaction-diffusion systems
• The gradient flow approach to hydrodynamic limits for the simple exclusion process
• Convergence to global equilibrium for Fokker-Planck equations on a graph and Talagrand-type inequalities
• Entropic Ricci curvature bounds for discrete interacting systems
• A gradient flow approach to large deviations for diffusion processes
• Quadratically regularized optimal transport on graphs
• Gradient and passive circuit structure in a class of non-linear dynamics on a graph
• Coarse-graining via EDP-convergence for linear fast-slow reaction systems
• Entropic approximation of Wasserstein gradient flows
• Geodesic convexity of the relative entropy in reversible Markov chains
• Gradient flow structures for discrete porous medium equations
• Gradient flows of the entropy for jump processes
• An analog of the 2-Wasserstein metric in non-commutative probability under which the fermionic Fokker-Planck equation is gradient flow for the entropy
• Vector and matrix optimal mass transport: theory, algorithm, and applications
• Entropic Ricci curvature for discrete spaces
• Wasserstein geometry of quantum states and optimal transport of matrix-valued measures
• Convergences of the squareroot approximation scheme to the Fokker–Planck operator
• Displacement convexity of entropy and related inequalities on graphs
• On the relation between gradient flows and the large-deviation principle, with applications to Markov chains and diffusion
• A gradient flow approach to linear Boltzmann equations
• On microscopic origins of generalized gradient structures
• Consistency and convergence for a family of finite volume discretizations of the Fokker-Planck operator
• Minimum entropy production, detailed balance and Wasserstein distance for continuous-time Markov processes
• Active Crowds
• Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation
• Anisothermal chemical reactions: Onsager-Machlup and macroscopic fluctuation theory
• Time discretizations of Wasserstein-Hamiltonian flows
• Evolutionary \(\Gamma\)-convergence of entropic gradient flow structures for Fokker-Planck equations in multiple dimensions
• Entropic Regularization of NonGradient Systems
• Macroscopic limit of the Becker-Döring equation via gradient flows
• Geodesics of minimal length in the set of probability measures on graphs
• Entropic curvature and convergence to equilibrium for mean-field dynamics on discrete spaces

This page was built for publication: Gradient flows of the entropy for finite Markov chains

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