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 and 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[12]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[22]

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

[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.

[24]

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

[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.

[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.

[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.

[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.

[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.

[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.

[31]

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

[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.

[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.

[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.

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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[12]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[22]

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

[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.

[24]

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

[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.

[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.

[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.

[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.

[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.

[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.

[31]

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

[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.

[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.

[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.

[1]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Continuous Dynamical Systems, 2021, 41 (5) : 2071-2094. doi: 10.3934/dcds.2020353

2020 Impact Factor: 1.213

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy