Top

Published in:

2016 | OriginalPaper | Chapter

Mean-Field Limits Beyond Ordinary Differential Equations

Authors : Luca Bortolussi, Nicolas Gast

Published in: Formal Methods for the Quantitative Evaluation of Collective Adaptive Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study the limiting behaviour of stochastic models of populations of interacting agents, as the number of agents goes to infinity. Classical mean-field results have established that this limiting behaviour is described by an ordinary differential equation (ODE) under two conditions: (1) that the dynamics is smooth; and (2) that the population is composed of a finite number of homogeneous sub-populations, each containing a large number of agents. This paper reviews recent work showing what happens if these conditions do not hold. In these cases, it is still possible to exhibit a limiting regime at the price of replacing the ODE by a more complex dynamical system. In the case of non-smooth or uncertain dynamics, the limiting regime is given by a differential inclusion. In the case of multiple population scales, the ODE is replaced by a stochastic hybrid automaton.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Dependability of Adaptable and Evolvable Distributed Systems

next chapter Modelling and Analysis of Collective Adaptive Systems with CARMA and its Tools

In fact, Lipschitz continuity is satisfied only locally, but this enough for mean field convergence to work.

A sequence of distributions is \(\pi ^N\) tight if their probability does not escape to infinity, i.e. for each \(\epsilon \) there is a compact set K such that \(\pi ^N(K)\ge 1-\epsilon \) for each N.

G is upper-hemicontinuous if for all \(x,y\in \mathbb {R}^d\), \(x_n\in \mathbb {R}^d\), \(y_n\in F(x_n)\), \(\lim _{n\rightarrow \infty }x_n=x\) and \(\lim _{n\rightarrow \infty }y_n=y\), then \(y\in F(x)\).

In fact, weak convergence holds for \((\mathbf {z},\mathbf {y})\) as processes in the Skorokhod space of cadlag functions, see [8]. For a definition of weak convergence, see [5].

In [8], weights are introduced to solve non-determinism between instantaneous transitions. Furthermore, the possibility of seeing a chain of instantaneous events firing is taken into account. Termination of this chain is discussed in [15] (where it is proved undecidable for countable state spaces), and in [27], where sufficient and testable conditions for termination are given.

Andersson, H., Britton, T.: Stochastic Epidemic Models and Their Statistical Analysis. Springer, Heidelberg (2000)CrossRefMATH

Aubin, J., Cellina, A.: Differential Inclusions. Springer, Heidelberg (1984)CrossRefMATH

Baier, C., et al.: Model-checking algorithms for continuous-time Markov chains. IEEE Trans. Softw. Eng. 29(6), 524–541 (2003). http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1205180 CrossRef

Benaim, M., Le Boudec, J.-Y.: A class of mean field interaction models for computer and communication systems. Perform. Eval. 65(11), 823–838 (2008)CrossRef

Billingsley, P.: Probability and Measure. English. Wiley, Hoboken (2012). ISBN: 9781118122372 1118122372MATH

Bortolussi, L., Gast, N.: Mean field approximation of imprecise population processes. QUANTICOL Technical report TR-QC-07-2015 (2015)

Bortolussi, L., et al.: Continuous approximation of collective systems behaviour: a tutorial. Perform. Eval. 70(5), 317–349 (2013). ISSN: 0166-5316, doi:10.1016/j.peva.2013.01.001, http://www.sciencedirect.com/science/article/pii/S0166531613000023

Bortolussi, L.: Hybrid behaviour of Markov population models. In: Information and Computation (2015)

Bortolussi, L.: Limit behavior of the hybrid approximation of stochastic process algebras. In: Al-Begain, K., Fiems, D., Knottenbelt, W.J. (eds.) ASMTA 2010. LNCS, vol. 6148, pp. 367–381. Springer, Heidelberg (2010). http://link.springer.com/chapter/10.1007/978-3-642-13568-2_26. Accessed 11 June 2015CrossRef

10.

Bortolussi, L., Hillston, J.: Model checking single agent behaviours by uid approximation. Inf. Comput. 242, 183–226 (2015). ISSN: 0890-5401, doi:10.1016/j.ic.2015.03.002

11.

Bortolussi, L., Lanciani, R.: Fluid model checking of timed properties. In: Sankaranarayanan, S., Vicario, E. (eds.) FORMATS 2015. LNCS, vol. 9268, pp. 172–188. Springer, Heidelberg (2015)CrossRef

12.

Bortolussi, L., Lanciani, R.: Model checking Markov population models by central limit approximation. In: Joshi, K., Siegle, M., Stoelinga, M., DArgenio, P.R. (eds.) QEST 2013. LNCS, vol. 8054, pp. 123–138. Springer, Heidelberg (2013)CrossRef

13.

Bortolussi, L., Lanciani, R.: Stochastic approximation of global reachability probabilities of Markov population models. In: Horvath, A., Wolter, K. (eds.) EPEW 2014. LNCS, vol. 8721, pp. 224–239. Springer, Heidelberg (2014)

14.

Bortolussi, L., Policriti, A.: Dynamical systems and stochastic programming: to ordinary differential equations and back. In: Priami, C., Back, R.-J., Petre, I. (eds.) Transactions on Computational Systems Biology XI. LNCS, vol. 5750, pp. 216–267. Springer, Heidelberg (2009)CrossRef

15.

Bortolussi, L., Policriti, A.: (Hybrid) automata, (stochastic) programs: the hybrid automata lattice of a stochastic program. J. Logic Comput. 23, 761–798 (2013). http://dx.doi.org/10.1093/logcom/exr045 MathSciNetCrossRefMATH

16.

Bortolussi, L., Policriti, A.: Hybrid dynamics of stochastic programs. Theor. Comput. Sci. 411(20), 2052–2077 (2010). ISSN: 0304-3975MathSciNetCrossRefMATH

17.

Chaintreau, A., Le Boudec, J.-Y., Ristanovic, N.: The age of gossip: spatial mean field regime. In: Proceedings of the ACM SIGMETRICS, vol. 37, issue 1, pp. 109–120. ACM (2009)

18.

Ciocchetta, F., Hillston, J.: Bio-PEPA: a framework for the modelling and analysis of biological systems. Theor. Comput. Sci. 410(33), 00185, 3065–3084 (2009). http://www.sciencedirect.com/science/article/pii/S0304397509001662. Accessed 25 Nov 2013

19.

Crudu, A., et al.: Convergence of stochastic gene networks to hybrid piecewise deterministic processes. Ann. Appl. Probab. 22(5), 00015, 1822–1859 (2012). http://projecteuclid.org/euclid.aoap/1350067987. Accessed 05 Nov 2013

20.

Darling, R., Norris, J.R., et al.: Differential equation approximations for Markov chains. Probab. Surv. 5, 37–79 (2008)MathSciNetCrossRefMATH

21.

Davis, M.H.A.: Markov Models and Optimization. Chapman & Hall, London (1993)CrossRefMATH

22.

Doncel, J., Gast, N., Gaujal, B.: Mean-Field Games with Explicit Interactions. Working paper or preprint, February 2016. https://hal.inria.fr/hal-01277098

23.

Durrett, R.: Essentials of Stochastic Processes. Springer, Heidelberg (2012). ISBN: 9781461436157CrossRefMATH

24.

Fricker, C., Gast, N.: Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity. EURO J. Trans. Logistics, 1–31 (2014)

25.

Fricker, C., Gast, N., Mohamed, H.: Mean field analysis for inhomogeneous bike sharing systems. DMTCS Proc. 01, 365–376 (2012)MathSciNetMATH

26.

Galpin, V.: Spatial representations, analysis techniques. In: SFM (2016)

27.

Galpin, V., Bortolussi, L., Hillston, J.: HYPE: hybrid modelling by composition of flows. Formal Aspects Comput. 25(4), 503–541 (2013)MathSciNetCrossRefMATH

28.

Gast, N., Gaujal, B.: Markov chains with discontinuous drifts have differential inclusion limits. Perform. Eval. 69(12), 623–642 (2012)CrossRef

29.

Gast, N., Gaujal, B.: Mean field limit of non-smooth systems and differential inclusions. ACM SIGMETRICS Perform. Eval. Rev. 38(2), 30–32 (2010)CrossRef

30.

Gast, N., Le Boudec, J.-Y., Tomozei, D.-C.: Impact of demand-response on the efficiency, prices in real-time electricity markets. In: Proceedings of the 5th International Conference on Future Energy Systems, pp. 171–182. ACM (2014)

31.

Gast, N., Van Houdt, B.: Transient and steady-state regime of a family of list-based cache replacement algorithms. In: ACM SIGMETRICS 2015 (2015)

32.

Hasenauer, J., et al.: Method of conditional moments (MCM) for the chemical master equation: a unified framework for the method of moments and hybrid stochastic-deterministic models. J. Math. Biol. 69, 687–735 (2013). ISSN: 0303-6812, 1432–1416, doi:10.1007/s00285-013-0711-5, http://link.springer.com/10.1007/s00285-013-0711-5. Accessed 31 July 2014

33.

Henzinger, T., Jobstmann, B., Wolf, V.: Formalisms for specifying Markovian population models. Int. J. Found. Comput. Sci. 22(04), 823–841 (2011). http://www.worldscience.com/doi/abs/10.1142/S0129054111008441 MathSciNetCrossRefMATH

34.

Hu, L., Le Boudec, J.-Y., Vojnoviae, M.: Optimal channel choice for collaborative ad-hoc dissemination. In: 2010 Proceedings of the IEEE INFOCOM, pp. 1–9. IEEE (2010)

35.

Huang, M., Malhame, R.P., Caines, P.E., et al.: Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle. Commun. Inf. Syst. 6(3), 221–252 (2006)MathSciNetMATH

36.

Katoen, J.-P., Khattri, M., Zapreevt, I.S.: A Markov reward model checker. In: Second International Conference on the Quantitative Evaluation of Systems, pp. 243–244 (2005). Accessed 18 Jan 2014

37.

Kurtz, T.: Solutions of ordinary differential equations as limits of pure jump Markov processes. J. Appl. Probab. 7, 49–58 (1970)MathSciNetCrossRefMATH

38.

Kwiatkowska, M., Norman, G., Parker, D.: PRISM 4.0: verification of probabilistic real-time systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 585–591. Springer, Heidelberg (2011). http://link.springer.com/chapter/10.1007/978- 3-642-22110-1_47. Accessed 18 Jan 2014CrossRef

39.

Krn, M., et al.: Stochasticity in gene expression: from theories to phenotypes. Nat. Rev. Genet. 6(6), 451–464 (2005). ISSN: 1471-0056, 1471–0064, doi:10.1038/nrg1615, http://www.nature.com/doifinder/10.1038/nrg1615. Accessed 09 Feb 2016

40.

Lasry, J.-M., Lions, P.-L.: Mean field games. Jpn. J. Math. 2(1), 229–260 (2007)MathSciNetCrossRefMATH

41.

Le Boudec, J.-Y.: Performance Evaluation of Computer and Communication Systems. EPFL Press, Lausanne (2010)MATH

42.

Loreti, M.: Modeling and analysis of collective adaptive systems with CARMA and its tools. In: SFM (2016)

43.

Mitzenmacher, M.: The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Syst. 12(10), 1094–1104 (2001)CrossRef

44.

Norris, J.R.: Markov Chains. English. Cambridge University Press, Cambridge (1998). ISBN: 978-0-511-81063-3 0-511-81063-6

45.

Pahle, J.: Biochemical simulations: stochastic, approximate stochastic and hybrid approaches. Briefings Bioinform. 10(1), 53–64 (2008). ISSN: 1467-5463, 1477–4054, doi:10.1093/bib/bbn050, http://bib.oxfordjournals.org/cgi/doi/10./bib/bbn050. Accessed 14 July 2014

46.

Todorov, E.: Optimal control theory. In: Bayesian Brain: Probabilistic Approaches to Neural Coding, pp. 269–298 (2006)

47.

Tribastone, M., Gilmore, S., Hillston, J.: Scalable differential analysis of process algebra models. IEEE Trans. Softw. Eng. 38(1), 205–219 (2012). http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5567115. Accessed 24 Nov 2013CrossRef

48.

Tschaikowski, M., Tribastone, M.: Approximate reduction of heterogenous nonlinear models with differential hulls. IEEE Trans. Autom. Control 61(4), 1099–1104 (2016). doi:10.1109/TAC.2015.2457172 CrossRef

49.

Tsitsiklis, J.N., Xu, K., et al.: On the power of (even a little) resource pooling. Stochast. Syst. 2(1), 1–66 (2012)MathSciNetCrossRefMATH

50.

Van Houdt, B.: A mean field model for a class of garbage collection algorithms in flash-based solid state drives. In: Proceedings of the ACM SIGMETRICS, SIGMETRICS 2013, Pittsburgh, PA, USA, pp. 191–202. ACM (2013). ISBN: 978-1-4503-1900-3, doi:10.1145/2465529.2465543, http://doi.acm.org/10.1145/2465529.2465543

51.

Wilkinson, D.: Stochastic Modelling for Systems Biology. Chapman & Hall, Florida (2006)MATH

52.

Yang, T., Mehta, P.G., Meyn, S.P.: A mean-field control-oriented approach to particle filtering. In: American Control Conference (ACC), pp. 2037–2043. IEEE (2011)

53.

Ying, L.: On the rate of convergence of mean-field models: Stein’s method meets the perturbation theory. arXiv preprint arXiv:1510.00761 (2015)

Title: Mean-Field Limits Beyond Ordinary Differential Equations
Authors: Luca Bortolussi
Nicolas Gast
Publisher: Springer International Publishing
Book: Formal Methods for the Quantitative Evaluation of Collective Adaptive Systems
Print ISBN: 978-3-319-34095-1

Electronic ISBN: 978-3-319-34096-8

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-34096-8_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner