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

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

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.
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.  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.  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.  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, 34 (2006).   Google Scholar

[6]

R. W. R. Darling and J. R. Norris, Differential equation approximations for Markov chains,, Probab. Surv., 5 (2008), 37.  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 (2000).   Google Scholar

[8]

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

[9]

G. Grimmett and D. Stirzaker, "Probability and Random Processes,", Third edition, (2001).   Google Scholar

[10]

T. Gross and B. Blasius, Adaptive coevolutionary networks: A review,, J. Roy. Soc. Interface, 5 (2008), 259.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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, 34 (2006).   Google Scholar

[6]

R. W. R. Darling and J. R. Norris, Differential equation approximations for Markov chains,, Probab. Surv., 5 (2008), 37.  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 (2000).   Google Scholar

[8]

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

[9]

G. Grimmett and D. Stirzaker, "Probability and Random Processes,", Third edition, (2001).   Google Scholar

[10]

T. Gross and B. Blasius, Adaptive coevolutionary networks: A review,, J. Roy. Soc. Interface, 5 (2008), 259.  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.  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.  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.  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.  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.  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.  doi: 10.1007/s00285-010-0344-x.  Google Scholar

[1]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[2]

P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178

[3]

Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial & Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111

[4]

Laura Aquilanti, Simone Cacace, Fabio Camilli, Raul De Maio. A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2020033

[5]

Theresa Lange, Wilhelm Stannat. Mean field limit of ensemble square root filters - discrete and continuous time. Foundations of Data Science, 2021  doi: 10.3934/fods.2021003

[6]

Daniele Bartolucci, Changfeng Gui, Yeyao Hu, Aleks Jevnikar, Wen Yang. Mean field equations on tori: Existence and uniqueness of evenly symmetric blow-up solutions. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3093-3116. doi: 10.3934/dcds.2020039

[7]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025

[8]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026

[9]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

[10]

Xianbo Sun, Zhanbo Chen, Pei Yu. Parameter identification on Abelian integrals to achieve Chebyshev property. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020375

[11]

Guangjun Shen, Xueying Wu, Xiuwei Yin. Stabilization of stochastic differential equations driven by G-Lévy process with discrete-time feedback control. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 755-774. doi: 10.3934/dcdsb.2020133

[12]

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011

[13]

Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389

[14]

Elvio Accinelli, Humberto Muñiz. A dynamic for production economies with multiple equilibria. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021002

[15]

Jiaquan Liu, Xiangqing Liu, Zhi-Qiang Wang. Sign-changing solutions for a parameter-dependent quasilinear equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020454

[16]

Chongyang Liu, Meijia Han, Zhaohua Gong, Kok Lay Teo. Robust parameter estimation for constrained time-delay systems with inexact measurements. Journal of Industrial & Management Optimization, 2021, 17 (1) : 317-337. doi: 10.3934/jimo.2019113

[17]

Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint state-parameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 65-84. doi: 10.3934/dcds.2009.23.65

[18]

Xing-Bin Pan. Variational and operator methods for Maxwell-Stokes system. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3909-3955. doi: 10.3934/dcds.2020036

[19]

Ole Løseth Elvetun, Bjørn Fredrik Nielsen. A regularization operator for source identification for elliptic PDEs. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021006

[20]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

2019 Impact Factor: 1.053

Metrics

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

[Back to Top]