×

zbMATH — the first resource for mathematics

Mean-field limits beyond ordinary differential equations. (English) Zbl 1346.68217
Bernardo, Marco (ed.) et al., Formal methods for the quantitative evaluation of collective adaptive systems. 16th international school on formal methods for the design of computer, communication, and software systems, SFM 2016, Bertinoro, Italy, June 20–24, 2016. Advanced lectures. Cham: Springer (ISBN 978-3-319-34095-1/pbk; 978-3-319-34096-8/ebook). Lecture Notes in Computer Science 9700, 61-82 (2016).
Summary: 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.
For the entire collection see [Zbl 1337.68006].

MSC:
68T42 Agent technology and artificial intelligence
34A60 Ordinary differential inclusions
34F05 Ordinary differential equations and systems with randomness
60J28 Applications of continuous-time Markov processes on discrete state spaces
68Q45 Formal languages and automata
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Software:
MRMC; PRISM; Bio-PEPA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersson, H., Britton, T.: Stochastic Epidemic Models and Their Statistical Analysis. Springer, Heidelberg (2000) · Zbl 0951.92021
[2] Aubin, J., Cellina, A.: Differential Inclusions. Springer, Heidelberg (1984) · Zbl 0538.34007
[3] 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 · Zbl 05113886
[4] 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)
[5] Billingsley, P.: Probability and Measure. English. Wiley, Hoboken (2012). ISBN: 9781118122372 1118122372
[6] Bortolussi, L., Gast, N.: Mean field approximation of imprecise population processes. QUANTICOL Technical report TR-QC-07-2015 (2015)
[7] 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
[8] Bortolussi, L.: Hybrid behaviour of Markov population models. In: Information and Computation (2015) · Zbl 1336.68177
[9] 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 2015 · Zbl 05757256
[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 · Zbl 1317.68108
[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) · Zbl 1465.68171
[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) · Zbl 06294360
[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) · Zbl 06465241
[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) · Zbl 1260.92020
[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 · Zbl 1272.68289
[16] Bortolussi, L., Policriti, A.: Hybrid dynamics of stochastic programs. Theor. Comput. Sci. 411(20), 2052–2077 (2010). ISSN: 0304-3975 · Zbl 1198.68175
[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 · Zbl 1173.68041
[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 · Zbl 1261.60073
[20] Darling, R., Norris, J.R., et al.: Differential equation approximations for Markov chains. Probab. Surv. 5, 37–79 (2008) · Zbl 1189.60152
[21] Davis, M.H.A.: Markov Models and Optimization. Chapman & Hall, London (1993) · Zbl 0780.60002
[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: 9781461436157 · Zbl 1244.60001
[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) · Zbl 1296.90019
[26] Galpin, V.: Spatial representations, analysis techniques. In: SFM (2016) · Zbl 06632412
[27] Galpin, V., Bortolussi, L., Hillston, J.: HYPE: hybrid modelling by composition of flows. Formal Aspects Comput. 25(4), 503–541 (2013) · Zbl 1298.68191
[28] Gast, N., Gaujal, B.: Markov chains with discontinuous drifts have differential inclusion limits. Perform. Eval. 69(12), 623–642 (2012)
[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)
[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) · Zbl 1349.68038
[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 · Zbl 1302.92070
[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 · Zbl 1216.68190
[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) · Zbl 1136.91349
[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) · Zbl 0191.47301
[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 2014 · Zbl 05940745
[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) · Zbl 1156.91321
[41] Le Boudec, J.-Y.: Performance Evaluation of Computer and Communication Systems. EPFL Press, Lausanne (2010) · Zbl 1246.68004
[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) · Zbl 05107720
[44] Norris, J.R.: Markov Chains. English. Cambridge University Press, Cambridge (1998). ISBN: 978-0-511-81063-3 0-511-81063-6 · Zbl 0938.60058
[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 2013
[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 · Zbl 1359.93084
[49] Tsitsiklis, J.N., Xu, K., et al.: On the power of (even a little) resource pooling. Stochast. Syst. 2(1), 1–66 (2012) · Zbl 1296.60253
[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) · Zbl 1099.92004
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.