American Institute of Mathematical Sciences

Advanced
March  2012, 7(1): 43-58. doi: 10.3934/nhm.2012.7.43

Differential equation approximations of stochastic network processes: An operator semigroup approach

András Bátkai 1, , Istvan Z. Kiss 2, , Eszter Sikolya 1, and  Péter L. Simon 1,

1. 

Loránd Eötvös University, Institute of Mathematics, Pázmány Péter Sétány 1C, H-1117 Budapest, Hungary, Hungary, Hungary
2. 

School of Mathematical and Physical Sciences, Department of Mathematics, University of Sussex, Falmer, Brighton BN1 9RF, United Kingdom

Received  July 2011 Revised  January 2012 Published  February 2012

The rigorous linking of exact stochastic models to mean-field approximations is studied. Starting from the differential equation point of view the stochastic model is identified by its master equation, which is a system of linear ODEs with large state space size ($N$). We derive a single non-linear ODE (called mean-field approximation) for the expected value that yields a good approximation as $N$ tends to infinity. Using only elementary semigroup theory we can prove the order $\mathcal{O}(1/N)$ convergence of the solution of the system to that of the mean-field equation. The proof holds also for cases that are somewhat more general than the usual density dependent one. Moreover, for Markov chains where the transition rates satisfy some sign conditions, a new approach using a countable system of ODEs for proving convergence to the mean-field limit is proposed.
Keywords: one-parameter operator semigroup, birth-and-death process, mean field approximation., Dynamic network.
Mathematics Subject Classification: Primary: 47D06; Secondary: 60J28, 92A1.
Citation: András Bátkai, Istvan Z. Kiss, Eszter Sikolya, Péter L. Simon. Differential equation approximations of stochastic network processes: An operator semigroup approach. Networks & Heterogeneous Media, 2012, 7 (1) : 43-58. doi: 10.3934/nhm.2012.7.43
References:
[1]

J. Banasiak, M. Lachowicz and M. Moszyński, Semigroups for generalized birth-and-death equations in $ \l^p$ spaces, Semigroup Forum, 73 (2006), 175-193. doi: 10.1007/s00233-006-0621-x.  Google Scholar

[2]

F. Ball and P. Neal, Network epidemic models with two levels of mixing, Math. Biosci., 212 (2008), 69-87. doi: 10.1016/j.mbs.2008.01.001.  Google Scholar

[3]

A. Bátkai, P. Csomós and G. Nickel, Operator splittings and spatial approximations for evolution equations, J. Evol. Equ., 9 (2009), 613-636. doi: 10.1007/s00028-009-0026-6.  Google Scholar

[4]

A. Bobrowski, "Functional Analysis for Probability and Stochastic Processes. An Introduction," Cambridge, 2005. Google Scholar

[5]

C. Chicone, "Ordinary Differential Equations with Applications," Second edition, Texts in Applied Mathematics, 34, Springer, New York, 2006.  Google Scholar

[6]

R. W. R. Darling and J. R. Norris, Differential equation approximations for Markov chains, Probab. Surv., 5 (2008), 37-79. doi: 10.1214/07-PS121.  Google Scholar

[7]

K.-J. Engel and R. Nagel, "One-Parameter Semigroups for Linear Evolution Equations," Graduate Texts in Math., 194, Springer-Verlag, New York, 2000.  Google Scholar

[8]

S. N. Ethier and T. G. Kurtz, "Markov Processes: Characterization and Convergence," John Wiley & Sons Ltd, USA, 2005. Google Scholar

[9]

G. Grimmett and D. Stirzaker, "Probability and Random Processes," Third edition, Oxford University Press, New York, 2001.  Google Scholar

[10]

T. Gross and B. Blasius, Adaptive coevolutionary networks: A review, J. Roy. Soc. Interface, 5 (2008), 259-271. doi: 10.1098/rsif.2007.1229.  Google Scholar

[11]

T. House and M. J. Keeling, Insights from unifying modern approximations to infections on networks, J. R. Soc. Interface, 8 (2011), 67-73. doi: 10.1098/rsif.2010.0179.  Google Scholar

[12]

T. Kato, On the semi-groups generated by Kolmogoroff's differential equations, J. Math. Soc. Japan, 6 (1954), 1-15. doi: 10.2969/jmsj/00610001.  Google Scholar

[13]

I. Z. Kiss, L. Berthouze, T. J. Taylor and P. L. Simon, Modelling approaches for simple dynamic networks and applications to disease transmission models,, Proc. Roy. Soc. A, ().   Google Scholar

[14]

T. G. Kurtz, Extensions of Trotter's operator semigroup approximation theorems, J. Functional Analysis, 3 (1969), 354-375. doi: 10.1016/0022-1236(69)90031-7.  Google Scholar

[15]

T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Prob., 7 (1970), 49-58. doi: 10.2307/3212147.  Google Scholar

[16]

J. Lindquist, J. Ma, P. van den Driessche and F. H. Willeboordse, Effective degree network disease models, J. Math. Biol., 62 (2011), 143-164. doi: 10.1007/s00285-010-0331-2.  Google Scholar

[17]

R. McVinish and P. K. Pollett, The deterministic limit of heterogeneous density dependent Markov chains,, Ann. Appl., ().   Google Scholar

[18]

P. L. Simon and I. Z. Kiss, From exact stochastic to mean-field ODE models: A case study of three different approaches to prove convergence results,, to appear., ().   Google Scholar

[19]

P. L. Simon, M. Taylor and I. Z. Kiss, Exact epidemic models on graphs using graph-automorphism driven lumping, J. Math. Biol., 62 (2011), 479-508. doi: 10.1007/s00285-010-0344-x.  Google Scholar

show all references

References:
[1]

J. Banasiak, M. Lachowicz and M. Moszyński, Semigroups for generalized birth-and-death equations in $ \l^p$ spaces, Semigroup Forum, 73 (2006), 175-193. doi: 10.1007/s00233-006-0621-x.  Google Scholar

[2]

F. Ball and P. Neal, Network epidemic models with two levels of mixing, Math. Biosci., 212 (2008), 69-87. doi: 10.1016/j.mbs.2008.01.001.  Google Scholar

[3]

A. Bátkai, P. Csomós and G. Nickel, Operator splittings and spatial approximations for evolution equations, J. Evol. Equ., 9 (2009), 613-636. doi: 10.1007/s00028-009-0026-6.  Google Scholar

[4]

A. Bobrowski, "Functional Analysis for Probability and Stochastic Processes. An Introduction," Cambridge, 2005. Google Scholar

[5]

C. Chicone, "Ordinary Differential Equations with Applications," Second edition, Texts in Applied Mathematics, 34, Springer, New York, 2006.  Google Scholar

[6]

R. W. R. Darling and J. R. Norris, Differential equation approximations for Markov chains, Probab. Surv., 5 (2008), 37-79. doi: 10.1214/07-PS121.  Google Scholar

[7]

K.-J. Engel and R. Nagel, "One-Parameter Semigroups for Linear Evolution Equations," Graduate Texts in Math., 194, Springer-Verlag, New York, 2000.  Google Scholar

[8]

S. N. Ethier and T. G. Kurtz, "Markov Processes: Characterization and Convergence," John Wiley & Sons Ltd, USA, 2005. Google Scholar

[9]

G. Grimmett and D. Stirzaker, "Probability and Random Processes," Third edition, Oxford University Press, New York, 2001.  Google Scholar

[10]

T. Gross and B. Blasius, Adaptive coevolutionary networks: A review, J. Roy. Soc. Interface, 5 (2008), 259-271. doi: 10.1098/rsif.2007.1229.  Google Scholar

[11]

T. House and M. J. Keeling, Insights from unifying modern approximations to infections on networks, J. R. Soc. Interface, 8 (2011), 67-73. doi: 10.1098/rsif.2010.0179.  Google Scholar

[12]

T. Kato, On the semi-groups generated by Kolmogoroff's differential equations, J. Math. Soc. Japan, 6 (1954), 1-15. doi: 10.2969/jmsj/00610001.  Google Scholar

[13]

I. Z. Kiss, L. Berthouze, T. J. Taylor and P. L. Simon, Modelling approaches for simple dynamic networks and applications to disease transmission models,, Proc. Roy. Soc. A, ().   Google Scholar

[14]

T. G. Kurtz, Extensions of Trotter's operator semigroup approximation theorems, J. Functional Analysis, 3 (1969), 354-375. doi: 10.1016/0022-1236(69)90031-7.  Google Scholar

[15]

T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Prob., 7 (1970), 49-58. doi: 10.2307/3212147.  Google Scholar

[16]

J. Lindquist, J. Ma, P. van den Driessche and F. H. Willeboordse, Effective degree network disease models, J. Math. Biol., 62 (2011), 143-164. doi: 10.1007/s00285-010-0331-2.  Google Scholar

[17]

R. McVinish and P. K. Pollett, The deterministic limit of heterogeneous density dependent Markov chains,, Ann. Appl., ().   Google Scholar

[18]

P. L. Simon and I. Z. Kiss, From exact stochastic to mean-field ODE models: A case study of three different approaches to prove convergence results,, to appear., ().   Google Scholar

[19]

P. L. Simon, M. Taylor and I. Z. Kiss, Exact epidemic models on graphs using graph-automorphism driven lumping, J. Math. Biol., 62 (2011), 479-508. doi: 10.1007/s00285-010-0344-x.  Google Scholar

[1]

Jacek Banasiak, Marcin Moszyński. Dynamics of birth-and-death processes with proliferation - stability and chaos. Discrete & Continuous Dynamical Systems, 2011, 29 (1) : 67-79. doi: 10.3934/dcds.2011.29.67
[2]

Jacek Banasiak, Mustapha Mokhtar-Kharroubi. Universality of dishonesty of substochastic semigroups: Shattering fragmentation and explosive birth-and-death processes. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 529-542. doi: 10.3934/dcdsb.2005.5.529
[3]

Xiaoyu Zheng, Peter Palffy-Muhoray. One order parameter tensor mean field theory for biaxial liquid crystals. Discrete & Continuous Dynamical Systems - B, 2011, 15 (2) : 475-490. doi: 10.3934/dcdsb.2011.15.475
[4]

Ciprian Preda. Discrete-time theorems for the dichotomy of one-parameter semigroups. Communications on Pure & Applied Analysis, 2008, 7 (2) : 457-463. doi: 10.3934/cpaa.2008.7.457
[5]

Manuela Giampieri, Stefano Isola. A one-parameter family of analytic Markov maps with an intermittency transition. Discrete & Continuous Dynamical Systems, 2005, 12 (1) : 115-136. doi: 10.3934/dcds.2005.12.115
[6]

Daniel Schnellmann. Typical points for one-parameter families of piecewise expanding maps of the interval. Discrete & Continuous Dynamical Systems, 2011, 31 (3) : 877-911. doi: 10.3934/dcds.2011.31.877
[7]

Stephen C. Preston, Alejandro Sarria. One-parameter solutions of the Euler-Arnold equation on the contactomorphism group. Discrete & Continuous Dynamical Systems, 2015, 35 (5) : 2123-2130. doi: 10.3934/dcds.2015.35.2123
[8]

Sung-Seok Ko. A nonhomogeneous quasi-birth-death process approach for an $ (s, S) $ policy for a perishable inventory system with retrial demands. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1415-1433. doi: 10.3934/jimo.2019009
[9]

Jun Hu, Oleg Muzician, Yingqing Xiao. Dynamics of regularly ramified rational maps: Ⅰ. Julia sets of maps in one-parameter families. Discrete & Continuous Dynamical Systems, 2018, 38 (7) : 3189-3221. doi: 10.3934/dcds.2018139
[10]

Thierry Paul, Mario Pulvirenti. Asymptotic expansion of the mean-field approximation. Discrete & Continuous Dynamical Systems, 2019, 39 (4) : 1891-1921. doi: 10.3934/dcds.2019080
[11]

Francesco Sanna Passino, Nicholas A. Heard. Modelling dynamic network evolution as a Pitman-Yor process. Foundations of Data Science, 2019, 1 (3) : 293-306. doi: 10.3934/fods.2019013
[12]

Zhenquan Zhang, Meiling Chen, Jiajun Zhang, Tianshou Zhou. Analysis of non-Markovian effects in generalized birth-death models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3717-3735. doi: 10.3934/dcdsb.2020254
[13]

Fabio Camilli, Francisco Silva. A semi-discrete approximation for a first order mean field game problem. Networks & Heterogeneous Media, 2012, 7 (2) : 263-277. doi: 10.3934/nhm.2012.7.263
[14]

Fabio Bagagiolo, Rosario Maggistro, Raffaele Pesenti. Origin-to-destination network flow with path preferences and velocity controls: A mean field game-like approach. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021007
[15]

Joachim Crevat. Mean-field limit of a spatially-extended FitzHugh-Nagumo neural network. Kinetic & Related Models, 2019, 12 (6) : 1329-1358. doi: 10.3934/krm.2019052
[16]

Hilla Behar, Alexandra Agranovich, Yoram Louzoun. Diffusion rate determines balance between extinction and proliferation in birth-death processes. Mathematical Biosciences & Engineering, 2013, 10 (3) : 523-550. doi: 10.3934/mbe.2013.10.523
[17]

Marita Thomas, Sven Tornquist. Discrete approximation of dynamic phase-field fracture in visco-elastic materials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (11) : 3865-3924. doi: 10.3934/dcdss.2021067
[18]

Diogo Gomes, Marc Sedjro. One-dimensional, forward-forward mean-field games with congestion. Discrete & Continuous Dynamical Systems - S, 2018, 11 (5) : 901-914. doi: 10.3934/dcdss.2018054
[19]

Genni Fragnelli, A. Idrissi, L. Maniar. The asymptotic behavior of a population equation with diffusion and delayed birth process. Discrete & Continuous Dynamical Systems - B, 2007, 7 (4) : 735-754. doi: 10.3934/dcdsb.2007.7.735
[20]

Jacques Henry. For which objective is birth process an optimal feedback in age structured population dynamics?. Discrete & Continuous Dynamical Systems - B, 2007, 8 (1) : 107-114. doi: 10.3934/dcdsb.2007.8.107

2020 Impact Factor: 1.213

Tools

Metrics

  • PDF downloads (50)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences