American Institute of Mathematical Sciences

Advanced
June  2015, 10(2): 233-253. doi: 10.3934/nhm.2015.10.233

On gradient structures for Markov chains and the passage to Wasserstein gradient flows

Karoline Disser 1, and  Matthias Liero 2,

1. 

Weierstrass Institute, Mohrenstraße 39, 10117 Berlin, Germany
2. 

Weierstrass Institute, Mohrenstraße 39, 10117 Berlin, Germany

Received  March 2014 Revised  October 2014 Published  April 2015

We study the approximation of Wasserstein gradient structures by their finite-dimensional analog. We show that simple finite-volume discretizations of the linear Fokker-Planck equation exhibit the recently established entropic gradient-flow structure for reversible Markov chains. Then we reprove the convergence of the discrete scheme in the limit of vanishing mesh size using only the involved gradient-flow structures. In particular, we make no use of the linearity of the equations nor of the fact that the Fokker-Planck equation is of second order.
Keywords: evolutionary $\Gamma$-convergence, Markov chains., entropy/entropy-dissipation formulation, discrete gradient flow structures, Wasserstein gradient flow.
Mathematics Subject Classification: 35K10, 35K20, 37L05, 49M25, 60F99, 65M08, 60J27, 70G75, 82B3.
Citation: Karoline Disser, Matthias Liero. On gradient structures for Markov chains and the passage to Wasserstein gradient flows. Networks & Heterogeneous Media, 2015, 10 (2) : 233-253. doi: 10.3934/nhm.2015.10.233
References:
[1]

S. Adams, N. Dirr, M. A. Peletier and J. Zimmer, From a large-deviations principle to the Wasserstein gradient flow: A new micro-macro passage, Communications in Mathematical Physics, 307 (2011), 791-815. doi: 10.1007/s00220-011-1328-4.  Google Scholar

[2]

L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2005.  Google Scholar

[3]

S. Arnrich, A. Mielke, M. A. Peletier, G. Savaré and M. Veneroni, Passing to the limit in a Wasserstein gradient flow: From diffusion to reaction, Calc. Var. Part. Diff. Eqns., 44 (2012), 419-454. doi: 10.1007/s00526-011-0440-9.  Google Scholar

[4]

J.-D. Benamou and Y. Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Math., 84 (2000), 375-393. doi: 10.1007/s002110050002.  Google Scholar

[5]

M. Bessemoulin-Chatard, A finite volume scheme for convection-diffusion equations with nonlinear diffusion derived from the Scharfetter-Gummel scheme, Numer. Math., 121 (2012), 637-670. doi: 10.1007/s00211-012-0448-x.  Google Scholar

[6]

A. Bradji and J. Fuhrmann, Some abstract error estimates of a finite volume scheme for a nonstationary heat equation on general nonconforming multidimensional spatial meshes, Appl. Math., 58 (2013), 1-38. doi: 10.1007/s10492-013-0001-y.  Google Scholar

[7]

C. Chainais-Hillairet, M. Gisclon and A. Jüngel, A finite-volume scheme for the multidimensional quantum drift-diffusion model for semiconductors, Numer. Methods Partial Differential Equations, 27 (2011), 1483-1510. doi: 10.1002/num.20592.  Google Scholar

[8]

S.-N. Chow, W. Huang, Y. Li and H. Zhou, Fokker-Planck equations for a free energy functional or Markov process on a graph, Arch. Rational Mech. Anal., 203 (2012), 969-1008. doi: 10.1007/s00205-011-0471-6.  Google Scholar

[9]

M. Erbar and J. Maas, Ricci curvature of finite Markov chains via convexity of the entropy, Arch. Rational Mech. Anal., 206 (2012), 997-1038. doi: 10.1007/s00205-012-0554-z.  Google Scholar

[10]

M. Erbar and J. Maas, Gradient flow structures for discrete porous medium equations, Discrete Contin. Dyn. Syst., 34 (2014), 1355-1374. doi: 10.3934/dcds.2014.34.1355.  Google Scholar

[11]

R. Eymard, T. Gallouët and R. Herbin, The finite volume method, in Handbook of Numerical Analysis. Vol. VII, North Holland, Amsterdam, 2000, 713-1022.  Google Scholar

[12]

R. Eymard and J.-M. Hérard, eds., Finite Volumes for Complex Applications V, ISTE, London, 2008.  Google Scholar

[13]

J. Fořt, J. Fürst Jiří, H. R. Herbin and F. Hubert, eds., Finite Volumes for Complex Applications. VI. Problems & perspectives. Volume 1, 2, Springer Proceedings in Mathematics, 4, Springer, Heidelberg, 2011. doi: 10.1007/978-3-642-20671-9.  Google Scholar

[14]

J. Fuhrmann, A. Linke and H. Langmach, A numerical method for mass conservative coupling between fluid flow and solute transport, Appl. Numer. Math., 61 (2011), 530-553. doi: 10.1016/j.apnum.2010.11.015.  Google Scholar

[15]

K. Gärtner, Charge transport in semiconductors and a finite volume scheme, in Finite volumes for complex applications. VI. Problems & perspectives. Volume 1, 2, Springer Proc. Math., 4, Springer, Heidelberg, 2011, 513-522. doi: 10.1007/978-3-642-20671-9_54.  Google Scholar

[16]

N. Gigli, On the heat flow on metric measure spaces: Existence, uniqueness and stability, Calc. Var. Partial Differential Equations, 39 (2010), 101-120. doi: 10.1007/s00526-009-0303-9.  Google Scholar

[17]

N. Gigli and J. Maas, Gromov-Hausdorff convergence of discrete transportation metrics, SIAM J. Math. Anal., 45 (2013), 879-899. doi: 10.1137/120886315.  Google Scholar

[18]

D. Hilhorst, H. C. V. Do and Y. Wang, A finite volume method for density driven flows in porous media, in CEMRACS'11: Multiscale Coupling of Complex Models in Scientific Computing, ESAIM Proc., 38, EDP Sci., Les Ulis, 2012, 376-386. doi: 10.1051/proc/201238021.  Google Scholar

[19]

R. Jordan, D. Kinderlehrer and F. Otto, The variational formulation of the Fokker-Planck equation, SIAM J. Math. Analysis, 29 (1998), 1-17. doi: 10.1137/S0036141096303359.  Google Scholar

[20]

M. Liero, Passing from bulk to bulk-surface evolution in the Allen-Cahn equation, NoDEA Nonlinear Differential Equations Appl., 20 (2013), 919-942. doi: 10.1007/s00030-012-0189-7.  Google Scholar

[21]

M. Liero and A. Mielke, Gradient structures and geodesic convexity for reaction-diffusion systems, Phil. Trans. Royal Soc. A, 371 (2013), 20120346, 28pp. doi: 10.1098/rsta.2012.0346.  Google Scholar

[22]

M. Liero and U. Stefanelli, Weighted inertia-dissipation-energy functionals for semilinear equations, Boll. Unione Mat. Ital. (9), 6 (2013), 1-27.  Google Scholar

[23]

J. Maas, Gradient flows of the entropy for finite Markov chains, J. Funct. Anal., 261 (2011), 2250-2292. doi: 10.1016/j.jfa.2011.06.009.  Google Scholar

[24]

P. A. Markowich, The Stationary Semiconductor Device Equations, Computational Microelectronics, Springer-Verlag, Vienna, 1986. doi: 10.1007/978-3-7091-3678-2.  Google Scholar

[25]

D. Matthes and H. Osberger, Convergence of a variational Lagrangian scheme for a nonlinear drift diffusion equation, ESAIM Math. Model. Numer. Anal., 48 (2014), 697-726. doi: 10.1051/m2an/2013126.  Google Scholar

[26]

A. Mielke, A gradient structure for reaction-diffusion systems and for energy-drift-diffusion systems, Nonlinearity, 24 (2011), 1329-1346. doi: 10.1088/0951-7715/24/4/016.  Google Scholar

[27]

A. Mielke, Geodesic convexity of the relative entropy in reversible Markov chains, Calc. Var. Part. Diff. Eqns., 48 (2013), 1-31. doi: 10.1007/s00526-012-0538-8.  Google Scholar

[28]

A. Mielke, Thermomechanical modeling of energy-reaction-diffusion systems, including bulk-interface interactions, Discr. Cont. Dynam. Systems Ser. S, 6 (2013), 479-499. doi: 10.3934/dcdss.2013.6.479.  Google Scholar

[29]

A. Mielke, T. Roubíček and U. Stefanelli, $\Gamma$-limits and relaxations for rate-independent evolutionary problems, Calc. Var. Part. Diff. Eqns., 31 (2008), 387-416. doi: 10.1007/s00526-007-0119-4.  Google Scholar

[30]

A. Mielke and U. Stefanelli, Weighted energy-dissipation functionals for gradient flows, ESAIM Control Optim. Calc. Var., 17 (2011), 52-85. doi: 10.1051/cocv/2009043.  Google Scholar

[31]

L. Onsager, Reciprocal relations in irreversible processes, I+II, Physical Review, 37 (1931), 405-426; Part II, 38, 2265-2267. Google Scholar

[32]

F. Otto, Dynamics of labyrinthine pattern formation in magnetic fluids: A mean-field theory, Arch. Rational Mech. Anal., 141 (1998), 63-103. doi: 10.1007/s002050050073.  Google Scholar

[33]

F. Otto, The geometry of dissipative evolution equations: The porous medium equation, Comm. Partial Differential Equations, 26 (2001), 101-174. doi: 10.1081/PDE-100002243.  Google Scholar

[34]

E. Sandier and S. Serfaty, Gamma-convergence of gradient flows with applications to Ginzburg-Landau, Comm. Pure Appl. Math., 57 (2004), 1627-1672. doi: 10.1002/cpa.20046.  Google Scholar

show all references

References:
[1]

S. Adams, N. Dirr, M. A. Peletier and J. Zimmer, From a large-deviations principle to the Wasserstein gradient flow: A new micro-macro passage, Communications in Mathematical Physics, 307 (2011), 791-815. doi: 10.1007/s00220-011-1328-4.  Google Scholar

[2]

L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2005.  Google Scholar

[3]

S. Arnrich, A. Mielke, M. A. Peletier, G. Savaré and M. Veneroni, Passing to the limit in a Wasserstein gradient flow: From diffusion to reaction, Calc. Var. Part. Diff. Eqns., 44 (2012), 419-454. doi: 10.1007/s00526-011-0440-9.  Google Scholar

[4]

J.-D. Benamou and Y. Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Math., 84 (2000), 375-393. doi: 10.1007/s002110050002.  Google Scholar

[5]

M. Bessemoulin-Chatard, A finite volume scheme for convection-diffusion equations with nonlinear diffusion derived from the Scharfetter-Gummel scheme, Numer. Math., 121 (2012), 637-670. doi: 10.1007/s00211-012-0448-x.  Google Scholar

[6]

A. Bradji and J. Fuhrmann, Some abstract error estimates of a finite volume scheme for a nonstationary heat equation on general nonconforming multidimensional spatial meshes, Appl. Math., 58 (2013), 1-38. doi: 10.1007/s10492-013-0001-y.  Google Scholar

[7]

C. Chainais-Hillairet, M. Gisclon and A. Jüngel, A finite-volume scheme for the multidimensional quantum drift-diffusion model for semiconductors, Numer. Methods Partial Differential Equations, 27 (2011), 1483-1510. doi: 10.1002/num.20592.  Google Scholar

[8]

S.-N. Chow, W. Huang, Y. Li and H. Zhou, Fokker-Planck equations for a free energy functional or Markov process on a graph, Arch. Rational Mech. Anal., 203 (2012), 969-1008. doi: 10.1007/s00205-011-0471-6.  Google Scholar

[9]

M. Erbar and J. Maas, Ricci curvature of finite Markov chains via convexity of the entropy, Arch. Rational Mech. Anal., 206 (2012), 997-1038. doi: 10.1007/s00205-012-0554-z.  Google Scholar

[10]

M. Erbar and J. Maas, Gradient flow structures for discrete porous medium equations, Discrete Contin. Dyn. Syst., 34 (2014), 1355-1374. doi: 10.3934/dcds.2014.34.1355.  Google Scholar

[11]

R. Eymard, T. Gallouët and R. Herbin, The finite volume method, in Handbook of Numerical Analysis. Vol. VII, North Holland, Amsterdam, 2000, 713-1022.  Google Scholar

[12]

R. Eymard and J.-M. Hérard, eds., Finite Volumes for Complex Applications V, ISTE, London, 2008.  Google Scholar

[13]

J. Fořt, J. Fürst Jiří, H. R. Herbin and F. Hubert, eds., Finite Volumes for Complex Applications. VI. Problems & perspectives. Volume 1, 2, Springer Proceedings in Mathematics, 4, Springer, Heidelberg, 2011. doi: 10.1007/978-3-642-20671-9.  Google Scholar

[14]

J. Fuhrmann, A. Linke and H. Langmach, A numerical method for mass conservative coupling between fluid flow and solute transport, Appl. Numer. Math., 61 (2011), 530-553. doi: 10.1016/j.apnum.2010.11.015.  Google Scholar

[15]

K. Gärtner, Charge transport in semiconductors and a finite volume scheme, in Finite volumes for complex applications. VI. Problems & perspectives. Volume 1, 2, Springer Proc. Math., 4, Springer, Heidelberg, 2011, 513-522. doi: 10.1007/978-3-642-20671-9_54.  Google Scholar

[16]

N. Gigli, On the heat flow on metric measure spaces: Existence, uniqueness and stability, Calc. Var. Partial Differential Equations, 39 (2010), 101-120. doi: 10.1007/s00526-009-0303-9.  Google Scholar

[17]

N. Gigli and J. Maas, Gromov-Hausdorff convergence of discrete transportation metrics, SIAM J. Math. Anal., 45 (2013), 879-899. doi: 10.1137/120886315.  Google Scholar

[18]

D. Hilhorst, H. C. V. Do and Y. Wang, A finite volume method for density driven flows in porous media, in CEMRACS'11: Multiscale Coupling of Complex Models in Scientific Computing, ESAIM Proc., 38, EDP Sci., Les Ulis, 2012, 376-386. doi: 10.1051/proc/201238021.  Google Scholar

[19]

R. Jordan, D. Kinderlehrer and F. Otto, The variational formulation of the Fokker-Planck equation, SIAM J. Math. Analysis, 29 (1998), 1-17. doi: 10.1137/S0036141096303359.  Google Scholar

[20]

M. Liero, Passing from bulk to bulk-surface evolution in the Allen-Cahn equation, NoDEA Nonlinear Differential Equations Appl., 20 (2013), 919-942. doi: 10.1007/s00030-012-0189-7.  Google Scholar

[21]

M. Liero and A. Mielke, Gradient structures and geodesic convexity for reaction-diffusion systems, Phil. Trans. Royal Soc. A, 371 (2013), 20120346, 28pp. doi: 10.1098/rsta.2012.0346.  Google Scholar

[22]

M. Liero and U. Stefanelli, Weighted inertia-dissipation-energy functionals for semilinear equations, Boll. Unione Mat. Ital. (9), 6 (2013), 1-27.  Google Scholar

[23]

J. Maas, Gradient flows of the entropy for finite Markov chains, J. Funct. Anal., 261 (2011), 2250-2292. doi: 10.1016/j.jfa.2011.06.009.  Google Scholar

[24]

P. A. Markowich, The Stationary Semiconductor Device Equations, Computational Microelectronics, Springer-Verlag, Vienna, 1986. doi: 10.1007/978-3-7091-3678-2.  Google Scholar

[25]

D. Matthes and H. Osberger, Convergence of a variational Lagrangian scheme for a nonlinear drift diffusion equation, ESAIM Math. Model. Numer. Anal., 48 (2014), 697-726. doi: 10.1051/m2an/2013126.  Google Scholar

[26]

A. Mielke, A gradient structure for reaction-diffusion systems and for energy-drift-diffusion systems, Nonlinearity, 24 (2011), 1329-1346. doi: 10.1088/0951-7715/24/4/016.  Google Scholar

[27]

A. Mielke, Geodesic convexity of the relative entropy in reversible Markov chains, Calc. Var. Part. Diff. Eqns., 48 (2013), 1-31. doi: 10.1007/s00526-012-0538-8.  Google Scholar

[28]

A. Mielke, Thermomechanical modeling of energy-reaction-diffusion systems, including bulk-interface interactions, Discr. Cont. Dynam. Systems Ser. S, 6 (2013), 479-499. doi: 10.3934/dcdss.2013.6.479.  Google Scholar

[29]

A. Mielke, T. Roubíček and U. Stefanelli, $\Gamma$-limits and relaxations for rate-independent evolutionary problems, Calc. Var. Part. Diff. Eqns., 31 (2008), 387-416. doi: 10.1007/s00526-007-0119-4.  Google Scholar

[30]

A. Mielke and U. Stefanelli, Weighted energy-dissipation functionals for gradient flows, ESAIM Control Optim. Calc. Var., 17 (2011), 52-85. doi: 10.1051/cocv/2009043.  Google Scholar

[31]

L. Onsager, Reciprocal relations in irreversible processes, I+II, Physical Review, 37 (1931), 405-426; Part II, 38, 2265-2267. Google Scholar

[32]

F. Otto, Dynamics of labyrinthine pattern formation in magnetic fluids: A mean-field theory, Arch. Rational Mech. Anal., 141 (1998), 63-103. doi: 10.1007/s002050050073.  Google Scholar

[33]

F. Otto, The geometry of dissipative evolution equations: The porous medium equation, Comm. Partial Differential Equations, 26 (2001), 101-174. doi: 10.1081/PDE-100002243.  Google Scholar

[34]

E. Sandier and S. Serfaty, Gamma-convergence of gradient flows with applications to Ginzburg-Landau, Comm. Pure Appl. Math., 57 (2004), 1627-1672. doi: 10.1002/cpa.20046.  Google Scholar

[1]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355
[2]

Jonathan Zinsl. The gradient flow of a generalized Fisher information functional with respect to modified Wasserstein distances. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 919-933. doi: 10.3934/dcdss.2017047
[3]

Zheng Sun, José A. Carrillo, Chi-Wang Shu. An entropy stable high-order discontinuous Galerkin method for cross-diffusion gradient flow systems. Kinetic & Related Models, 2019, 12 (4) : 885-908. doi: 10.3934/krm.2019033
[4]

Wenqing Hu, Chris Junchi Li. A convergence analysis of the perturbed compositional gradient flow: Averaging principle and normal deviations. Discrete & Continuous Dynamical Systems, 2018, 38 (10) : 4951-4977. doi: 10.3934/dcds.2018216
[5]

Matthias Erbar, Max Fathi, Vaios Laschos, André Schlichting. Gradient flow structure for McKean-Vlasov equations on discrete spaces. Discrete & Continuous Dynamical Systems, 2016, 36 (12) : 6799-6833. doi: 10.3934/dcds.2016096
[6]

Samir Salem. A gradient flow approach of propagation of chaos. Discrete & Continuous Dynamical Systems, 2020, 40 (10) : 5729-5754. doi: 10.3934/dcds.2020243
[7]

Sylvia Serfaty. Gamma-convergence of gradient flows on Hilbert and metric spaces and applications. Discrete & Continuous Dynamical Systems, 2011, 31 (4) : 1427-1451. doi: 10.3934/dcds.2011.31.1427
[8]

Timothy Blass, Rafael De La Llave, Enrico Valdinoci. A comparison principle for a Sobolev gradient semi-flow. Communications on Pure & Applied Analysis, 2011, 10 (1) : 69-91. doi: 10.3934/cpaa.2011.10.69
[9]

Bertram Düring, Daniel Matthes, Josipa Pina Milišić. A gradient flow scheme for nonlinear fourth order equations. Discrete & Continuous Dynamical Systems - B, 2010, 14 (3) : 935-959. doi: 10.3934/dcdsb.2010.14.935
[10]

César J. Niche. Topological entropy of a magnetic flow and the growth of the number of trajectories. Discrete & Continuous Dynamical Systems, 2004, 11 (2&3) : 577-580. doi: 10.3934/dcds.2004.11.577
[11]

Alexander Mielke. Deriving amplitude equations via evolutionary $\Gamma$-convergence. Discrete & Continuous Dynamical Systems, 2015, 35 (6) : 2679-2700. doi: 10.3934/dcds.2015.35.2679
[12]

Matthias Liero, Alexander Mielke, Mark A. Peletier, D. R. Michiel Renger. On microscopic origins of generalized gradient structures. Discrete & Continuous Dynamical Systems - S, 2017, 10 (1) : 1-35. doi: 10.3934/dcdss.2017001
[13]

K.H. Wong, C. Myburgh, L. Omari. A gradient flow approach for computing jump linear quadratic optimal feedback gains. Discrete & Continuous Dynamical Systems, 2000, 6 (4) : 803-808. doi: 10.3934/dcds.2000.6.803
[14]

Dmitrii Rachinskii. Realization of arbitrary hysteresis by a low-dimensional gradient flow. Discrete & Continuous Dynamical Systems - B, 2016, 21 (1) : 227-243. doi: 10.3934/dcdsb.2016.21.227
[15]

Daniel J. Thompson. A criterion for topological entropy to decrease under normalised Ricci flow. Discrete & Continuous Dynamical Systems, 2011, 30 (4) : 1243-1248. doi: 10.3934/dcds.2011.30.1243
[16]

Gunhild A. Reigstad. Numerical network models and entropy principles for isothermal junction flow. Networks & Heterogeneous Media, 2014, 9 (1) : 65-95. doi: 10.3934/nhm.2014.9.65
[17]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345
[18]

Shui-Nee Chow, Wuchen Li, Haomin Zhou. Entropy dissipation of Fokker-Planck equations on graphs. Discrete & Continuous Dynamical Systems, 2018, 38 (10) : 4929-4950. doi: 10.3934/dcds.2018215
[19]

Rafael Ayala, Jose Antonio Vilches, Gregor Jerše, Neža Mramor Kosta. Discrete gradient fields on infinite complexes. Discrete & Continuous Dynamical Systems, 2011, 30 (3) : 623-639. doi: 10.3934/dcds.2011.30.623
[20]

James P. Kelly, Kevin McGoff. Entropy conjugacy for Markov multi-maps of the interval. Discrete & Continuous Dynamical Systems, 2021, 41 (5) : 2071-2094. doi: 10.3934/dcds.2020353

2020 Impact Factor: 1.213

Tools

Metrics

  • PDF downloads (88)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences