Lazy random walks and optimal transport on graphs

DOI10.1214/15-AOP1012zbMATH Open1397.60109arXiv1308.0226OpenAlexW2964328909MaRDI QIDQ726796FDOQ726796

Authors: Christian Léonard 

Publication date: 14 July 2016

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: This paper is about the construction of displacement interpolations on a discrete metric graph. Our approach is based on the approximation of any optimal transport problem whose cost function is a distance on a discrete graph by a sequence of Schr"odinger problems associated with random walks whose jump frequencies tend down to zero. Displacement interpolations are defined as the limit of the time-marginal flows of the solutions to the Schr"odinger problems. This allows to work with these interpolations by doing stochastic calculus on the approximating random walks which are regular objects, and then to pass to the limit in a slowing down procedure. The main convergence results are based on Gamma-convergence of entropy minimization problems. As a by-product, we obtain new results about optimal transport on graphs.

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

Recommendations

• A transport process on graphs and its limiting distributions
• Random walks on graphs and approximation of \(L^2\)-invariants
• Random walks on dense graphs and graphons
• Optimal Transport on Networks
• scientific article; zbMATH DE number 1552103
• Random walks on graphs: ideas, techniques and results
• Optimal transport between random measures
• Optimal mass transport on metric graphs
• scientific article; zbMATH DE number 946659

zbMATH Keywords

optimal transport\(\Gamma\)-convergencerandom walks[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Schr%EF%BF%BD%EF%BF%BDdinger+problem&go=Go Schr��dinger problem]entropy minimizationdiscrete metric graphdisplacement interpolation

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Variational problems in a geometric measure-theoretic setting (49Q20) Sums of independent random variables; random walks (60G50) Methods involving semicontinuity and convergence; relaxation (49J45) Continuous-time Markov processes on discrete state spaces (60J27)

Cites Work

• Title not available (Why is that?)
• Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs
• Optimal Transport
• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• An introduction to \(\Gamma\)-convergence
• A convexity principle for interacting gases
• Ricci curvature for metric-measure spaces via optimal transport
• On the geometry of metric measure spaces. I
• On the geometry of metric measure spaces. II
• Title not available (Why is that?)
• The Monge problem in \(\mathbb R^d\)
• Ricci curvature of Markov chains on metric spaces
• Ricci curvature of finite Markov chains via convexity of the entropy
• Asymptotic development by \(\Gamma{}\)-convergence
• A gradient structure for reaction–diffusion systems and for energy-drift-diffusion systems
• Title not available (Why is that?)
• From the Schrödinger problem to the Monge-Kantorovich problem
• Gradient flows of the entropy for finite Markov chains
• Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality
• Concavity of entropy along binomial convolutions
• Contraction of measures on graphs
• Displacement convexity of entropy and related inequalities on graphs
• Viscosity Solutions of Minimization Problems
• Log-concavity and the maximum entropy property of the Poisson distribution
• Transport inequalities, gradient estimates, entropy and Ricci curvature
• A survey of the Schrödinger problem and some of its connections with optimal transport
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Riemannian interpolation inequality à la Borell, Brascamp and Lieb
• Mass transportation and rough curvature bounds for discrete spaces
• Existence of optimal transport maps for crystalline norms
• Title not available (Why is that?)
• Differential equations methods for the Monge-Kantorovich mass transfer problem
• Girsanov theory under a finite entropy condition
• Reciprocal processes. A measure-theoretical point of view
• A curved Brunn-Minkowski inequality on the discrete hypercube, or: what is the Ricci curvature of the discrete hypercube?
• Some properties of path measures
• Title not available (Why is that?)

Cited In (23)

• The Most Likely Evolution of Diffusing and Vanishing Particles: Schrödinger Bridges with Unbalanced Marginals
• Sequences of well-distributed vertices on graphs and spectral bounds on optimal transport
• Some recent developments in functional inequalities
• A transport process on graphs and its limiting distributions
• Absolutely continuous and BV-curves in 1-Wasserstein spaces
• Homogenisation of dynamical optimal transport on periodic graphs
• Schrödinger dynamics and optimal transport of measures
• Interpolating between random walks and optimal transportation routes: flow with multiple sources and targets
• Lazy random walks on pseudofractal scale-free web with a perfect trap
• Optimal control for diffusions on graphs
• Dynamical Schrödinger bridge problems on graphs
• Vector-valued optimal mass transport
• Nonexponential Sanov and Schilder theorems on Wiener space: BSDEs, Schrödinger problems and control
• A survey of the Schrödinger problem and some of its connections with optimal transport
• Entropic Ricci curvature for discrete spaces
• A second order equation for Schrödinger bridges with applications to the hot gas experiment and entropic transportation cost
• The Markov-quantile process attached to a family of marginals
• Stochastic control liaisons. Richard Sinkhorn meets Gaspard Monge on a Schrödinger bridge
• Propagation of chaos for mean field Schrödinger problems
• \(W_{1,+}\)-interpolation of probability measures on graphs
• Entropic curvature on graphs along Schrödinger bridges at zero temperature
• What is a stochastic Hamiltonian process on finite graph? An optimal transport answer
• Interpolation of probability measures on graphs

This page was built for publication: Lazy random walks and optimal transport on graphs

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