A refined mean field approximation of synchronous discrete-time population models
Gast N., Latella D., Massink M.
Dynamical Systems (math.DS) Modeling and Simulation Mean field approximation FOS: Electrical engineering FOS: Mathematics Hardware and Architecture Computer Networks and Communications [MATH.MATH-PR]Mathematics [math]/Probability [math.PR] Discrete time population models Mathematics - Dynamical Systems [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] electronic engineering Accuracy of approximation FOS: Computer and information sciences [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] Systems and Control (eess.SY) Computer Science - Performance [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF] Computer Science - Systems and Control Performance (cs.PF) Software information engineering
Mean field approximation is a popular method to study the behaviour of stochastic models composed of a large number of interacting objects. When the objects are asynchronous, the mean field approximation of a population model can be expressed as an ordinary differential equation. When the objects are (clock-) synchronous the mean field approximation is a discrete time dynamical system. We focus on the latter. We study the accuracy of mean field approximation when this approximation is a discrete-time dynamical system. We extend a result that was shown for the continuous time case and we prove that expected performance indicators estimated by mean field approximation are O(1/N)-accurate. We provide simple expressions to effectively compute the asymptotic error of mean field approximation, for finite time-horizon and steady-state, and we use this computed error to propose what we call a refined mean field approximation. We show, by using a few numerical examples, that this technique improves the quality of approximation compared to the classical mean field approximation, especially for relatively small population sizes.
Source: Performance evaluation 126 (2018): 1–21. doi:10.1016/j.peva.2018.05.002
Publisher: North-Holland, Amsterdam , Paesi Bassi
[2] Michel Benam and Jean-Yves Le Boudec. A class of mean eld interaction models for computer and communication systems. Perform. Eval., 65(11-12):823{838, 2008.
[3] Luca Bortolussi and Richard A. Hayden. Bounds on the deviation of discrete-time markov chains from their mean- eld model. Perform. Eval., 70(10):736{749, 2013.
[4] Luca Bortolussi, Jane Hillston, Diego Latella, and Mieke Massink. Continuous approximation of collective system behaviour: A tutorial. Perform. Eval., 70(5):317{349, 2013.
[5] Jean-Yves Le Boudec, David D. McDonald, and Jochen Mundinger. A generic mean eld convergence result for systems of interacting objects. In Fourth International Conference on the Quantitative Evaluation of Systems (QEST 2007), 17-19 September 2007, Edinburgh, Scotland, UK, pages 3{18. IEEE Computer Society, 2007.
[6] Anton Braverman, J. G. Dai, and Jiekun Feng. Steins method for steady-state di usion approximations: An introduction through the erlang-a and erlang-c models. Stochastic Systems, 6(2):301{366, 2016.
[7] Anton Braverman and Jim Dai. Steins method for steady-state di usion approximations of M=P h=n + M systems. The Annals of Applied Probability, 27(1):550{581, 2017.
[8] Marco Antonio Montes de Oca, Eliseo Ferrante, Alexander Scheidler, Carlo Pinciroli, Mauro Birattari, and Marco Dorigo. Majority-rule opinion dynamics with di erential latency: a mechanism for self-organized collective decision-making. Swarm Intelligence, 5(3-4):305{327, 2011.
[9] Nicolas Gast. Expected values estimated via mean- eld approximation are 1/n-accurate: Extended abstract. In Bruce E. Hajek, Sewoong Oh, Augustin Chaintreau, Leana Golubchik, and Zhi-Li Zhang, editors, Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Urbana-Champaign, IL, USA, June 05 - 09, 2017, page 50. ACM, 2017.
[10] Nicolas Gast and Gaujal Bruno. A mean eld model of work stealing in large-scale systems. SIGMETRICS Perform. Eval. Rev., 38(1):13{24, June 2010.
[11] Nicolas Gast and Bruno Gaujal. A mean eld approach for optimization in discrete time. Discrete Event Dynamic Systems, 21(1):63{101, 2011.
[12] Nicolas Gast and Bruno Gaujal. Markov chains with discontinuous drifts have di erential inclusion limits. Perform. Eval., 69(12):623{642, 2012.
[13] Nicolas Gast and Benny Van Houdt. A re ned mean eld approximation. Proc. ACM Meas. Anal. Comput. Syst., 1(2):33:1{33:28, December 2017.
[14] V. N. Kolokoltsov, J. Li, and W. Yang. Mean Field Games and Nonlinear Markov Processes. ArXiv e-prints, December 2011.
[15] Thomas G Kurtz. Solutions of Ordinary Di erential Equations as Limits of Pure Jump Markov Processes. Journal of Applied Probability, 7:49{58, 1970.
[16] Diego Latella, Michele Loreti, and Mieke Massink. On-the- y PCTL fast mean- eld approximated model-checking for self-organising coordination. Sci. Comput. Program., 110:23{50, 2015.
[17] L. Massoulie and M. Vojnovic. Coupon replication systems. SIGMETRICS Perform. Eval. Rev., 33(1):2{13, June 2005.
[18] Wouter Minnebo and Benny Van Houdt. A fair comparison of pull and push strategies in large distributed networks. IEEE/ACM Trans. Netw., 22(3):996{1006, 2014.
[19] Michael Mitzenmacher. The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Syst., 12(10):1094{1104, 2001.
[20] Alexander Scheidler. Dynamics of majority rule with di erential latencies. Phys. Rev. E, 83:031116{1 { 031116{4, Mar 2011.
[21] Charles Stein. Approximate computation of expectations. Lecture Notes-Monograph Series, 7:i{164, 1986.
[22] Peerapol Tinnakornsrisuphap and Armand M. Makowski. Limit behavior of ECN/RED gateways under a large number of TCP ows. In Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30 - April 3, 2003, pages 873{883. IEEE, 2003.
[23] John N. Tsitsiklis and Kuang Xu. On the power of (even a little) centralization in distributed processing. In Arif Merchant, Kimberly Keeton, and Dan Rubenstein, editors, SIGMETRICS 2011, Proceedings of the 2011 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, San Jose, CA, USA, 07-11 June 2011 (Co-located with FCRC 2011), pages 161{172. ACM, 2011.
[24] Benny Van Houdt. A mean eld model for a class of garbage collection algorithms in ashbased solid state drives. In Mor Harchol-Balter, John R. Douceur, and Jun Xu, editors, ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '13, Pittsburgh, PA, USA, June 17-21, 2013, pages 191{202. ACM, 2013.
[25] Nikita Dmitrievna Vvedenskaya, Roland L'vovich Dobrushin, and Fridrikh Izrailevich Karpelevich. Queueing system with selection of the shortest of two queues: An asymptotic approach. Problemy Peredachi Informatsii, 32(1):20{34, 1996.
[26] D.J Wilkinson. Stochastic Modelling for Systems Biology. Chapman & Hall, 2006.
[27] Lei Ying. On the approximation error of mean- eld models. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, SIGMETRICS '16, pages 285{297, New York, NY, USA, 2016. ACM.
[28] Lei Ying. Stein's method for mean eld approximations in light and heavy tra c regimes. POMACS, 1(1):12:1{12:27, 2017.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:392025,
title = {A refined mean field approximation of synchronous discrete-time population models},
author = {Gast N. and Latella D. and Massink M.},
publisher = {North-Holland, Amsterdam , Paesi Bassi},
doi = {10.1016/j.peva.2018.05.002 and 10.48550/arxiv.1807.08585},
journal = {Performance evaluation},
volume = {126},
pages = {1–21},
year = {2018}
}
0000-0002-3257-9059
