{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T15:37:26Z","timestamp":1759073846967,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["600708"],"award-info":[{"award-number":["600708"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2017,6,13]]},"abstract":"<jats:p>\n            Mean-field approximation is a powerful tool to study large-scale stochastic systems such as data-centers -- one example being the famous power of two-choice paradigm. It is shown in the literature that under quite general conditions, the empirical measure of a system of\n            <jats:italic>N<\/jats:italic>\n            interacting objects converges at rate\n            <jats:italic>O<\/jats:italic>\n            (1\u221a\n            <jats:italic>N<\/jats:italic>\n            ) to a deterministic dynamical system, called its mean-field approximation.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we revisit the accuracy of mean-field approximation by focusing on expected values. We show that, under almost the same general conditions, the expectation of any performance functional converges at rate O(1\/\n            <jats:italic>N<\/jats:italic>\n            ) to its mean-field approximation. Our result applies for finite and infinite-dimensional mean-field models. We also develop a new perturbation theory argument that shows that the result holds for the stationary regime if the dynamical system is asymptotically exponentially stable. We provide numerical experiments that demonstrate that this rate of convergence is tight and that illustrate the necessity of our conditions. As an example, we apply our result to the classical two-choice model. By combining our theory with numerical experiments, we claim that, as the load rho goes to 1, the average queue length of a two-choice system with\n            <jats:italic>N<\/jats:italic>\n            servers is log\n            <jats:sub>2<\/jats:sub>\n            1\/(1--\u03c1) + 1\/(2\n            <jats:italic>N<\/jats:italic>\n            (1-\u03c1) +\n            <jats:italic>O<\/jats:italic>\n            (1\/\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ).\n          <\/jats:p>","DOI":"10.1145\/3084454","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T18:28:08Z","timestamp":1521829688000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Expected Values Estimated via Mean-Field Approximation are 1\/N-Accurate"],"prefix":"10.1145","volume":"1","author":[{"given":"Nicolas","family":"Gast","sequence":"first","affiliation":[{"name":"Inria, Grenoble, France"}]}],"member":"320","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01055703"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2008.03.005"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2013.08.012"},{"key":"e_1_2_1_4_1","unstructured":"Henri Cartan. 1977. Cours de calcul diff\u00e9rentiel. Hermann.  Henri Cartan. 1977. Cours de calcul diff\u00e9rentiel. Hermann."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825241"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492101.1555363"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1870178.1870191"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Jaap Eldering. 2013. Normally Hyperbolic Invariant Manifolds-the Noncompact Case (Atlantis Series in Dynamical Systems vol 2). Berlin: Springer.  Jaap Eldering. 2013. Normally Hyperbolic Invariant Manifolds-the Noncompact Case (Atlantis Series in Dynamical Systems vol 2). Berlin: Springer.","DOI":"10.2991\/978-94-6239-003-4"},{"key":"e_1_2_1_9_1","unstructured":"Patrick Eschenfeldt and David Gamarnik. 2016. Supermarket queueing system in the heavy traffic regime. Short queue dynamics. arXiv preprint arXiv:1610.03522 (2016).  Patrick Eschenfeldt and David Gamarnik. 2016. Supermarket queueing system in the heavy traffic regime. Short queue dynamics. arXiv preprint arXiv:1610.03522 (2016)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811099.1811042"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2012.07.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745850"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200015345"},{"key":"e_1_2_1_14_1","unstructured":"Vassili N Kolokoltsov Jiajie Li and Wei Yang. 2011. Mean field games and nonlinear Markov processes. arXiv preprint arXiv:1112.3744 (2011).  Vassili N Kolokoltsov Jiajie Li and Wei Yang. 2011. Mean field games and nonlinear Markov processes. arXiv preprint arXiv:1112.3744 (2011)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/3212147"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(78)90020-0"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2011.07.015"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Malwina J Luczak and Colin McDiarmid. 2007. Asymptotic distributions and chaos for the supermarket model. arXiv preprint arXiv:0712.2091 (2007).  Malwina J Luczak and Colin McDiarmid. 2007. Asymptotic distributions and chaos for the supermarket model. arXiv preprint arXiv:0712.2091 (2007).","DOI":"10.1214\/EJP.v12-391"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2270445"},{"key":"e_1_2_1_20_1","unstructured":"Michael David Mitzenmacher. 1996. The Power of Two Random Choices in Randomized Load Balancing. Ph.D. Dissertation. PhD thesis Graduate Division of the University of California at Berkley.  Michael David Mitzenmacher. 1996. The Power of Two Random Choices in Randomized Load Balancing. Ph.D. Dissertation. PhD thesis Graduate Division of the University of California at Berkley."},{"key":"e_1_2_1_21_1","unstructured":"Charles Stein. 1986. Approximate computation of expectations. Lecture Notes-Monograph Series 7 (1986) i--164.  Charles Stein. 1986. Approximate computation of expectations. Lecture Notes-Monograph Series 7 (1986) i--164."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2007116.2007131"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964800005088"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494232.2465543"},{"key":"e_1_2_1_25_1","first-page":"20","article-title":"Queueing system with selection of the shortest of two queues: An asymptotic approach","volume":"32","author":"Vvedenskaya Nikita Dmitrievna","year":"1996","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901463"},{"key":"e_1_2_1_27_1","unstructured":"Lei Ying. 2016. On the Rate of Convergence of the Power-of-Two-Choices to its Mean-Field Limit. CoRR abs\/1605.06581 (2016). http:\/\/arxiv.org\/abs\/1605.06581  Lei Ying. 2016. On the Rate of Convergence of the Power-of-Two-Choices to its Mean-Field Limit. CoRR abs\/1605.06581 (2016). http:\/\/arxiv.org\/abs\/1605.06581"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084454","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084454","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:22Z","timestamp":1750217422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084454"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,6,13]]}},"alternative-id":["10.1145\/3084454"],"URL":"https:\/\/doi.org\/10.1145\/3084454","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2017,6,13]]},"assertion":[{"value":"2017-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}