Nonlinear Markov processes in big networks

Quan-Lin Li

Special Matrices, Tome 4 (2016), p. 202-217 / Harvested from The Polish Digital Mathematics Library

Résumé

Big networks express multiple classes of large-scale networks in many practical areas such as computer networks, internet of things, cloud computation, manufacturing systems, transportation networks, and healthcare systems. This paper analyzes such big networks, and applies the mean-field theory and the nonlinear Markov processes to constructing a broad class of nonlinear continuous-time block-structured Markov processes, which can be used to deal with many practical stochastic systems. Firstly, a nonlinear Markov process is derived from a large number of big networks with weak interactions, where each big network is described as a continuous-time block-structured Markov process. Secondly, some effective algorithms are given for computing the fixed points of the nonlinear Markov process by means of the UL-type RG-factorization. Finally, the Birkhoff center, the locally stable fixed points, the Lyapunov functions and the relative entropy are developed to analyze stability or metastability of the system of weakly interacting big networks, and several interesting open problems are proposed with detailed interpretation. We believe that the methodology and results given in this paper can be useful and effective in the study of big networks.

Détail

Publié le : 2016-01-01

Zbl 1343.60115

EUDML-ID : urn:eudml:doc:277111

Bibliographie

[1] N. Antunes, C. Fricker, P. Robert, D. Tibi, Metastability of CDMA cellular systems. In: Proceedings of the 12th Annual International ACM Conference on Mobile Computing and Networking, (2006), pp 206–214.

[2] N. Antunes, C. Fricker, P. Robert, D. Tibi, Analysis of Loss Networks with Routing, The Annals of Applied Probability, 16(4) (2006) 2007–2026. [Crossref] | Zbl 1121.60100

[3] N. Antunes, C. Fricker, P. Robert, D. Tibi, Stochastic networks with multiple stable points, The Annals of Probability, 36(1) (2008) 255–278. [Crossref] | Zbl 1130.60086

[4] F. Baccelli, F.I. Karpelevich, M.Y. Kelbert, A.A. Puhalskii, A.N. Rybko, Y.M. Suhov, A mean-field limit for a class of queueing networks, Journal of Statistical Physics, 66(3–4) (1992) 803–825. [Crossref]

[5] F. Baccelli, A.N. Rybko, S. Shlosman, Queuing networks with varying topology–a mean-field approach, arXiv preprint: arXiv:1311.3898, (2013).

[6] J. Beltran, C. Landim, Tunneling and metastability of continuous time Markov chains, Journal of Statistical Physics, 140(6) (2010) 1065–1114. [Crossref] | Zbl 1223.60061

[7] J. Beltran, C. Landim, Tunneling and metastability of continuous time Markov chains II, the nonreversible case, Journal of Statistical Physics, 149(4) (2012) 598–618. [Crossref] | Zbl 1260.82063

[8] M. Benaim, On gradient like properties of population games, learning models and self reinforced processes, arXiv preprint: arXiv:1409.4091, (2014).

[9] M. Benaim, J.Y. Le Boudec, A class of mean-field interaction models for computer and communication systems, Performence Evalution, 65(11–12) (2008) 823–838.

[10] M. Benaim, J.Y. Le Boudec, On mean field convergence and stationary regime, arXiv preprint: arXiv:1111.5710, (2011).

[11] A. Bobbio, M. Gribaudo, M. Telek, Analysis of large scale interacting systems by mean field method. In: The Fifth International IEEE Conference on Quantitative Evaluation of Systems, (2008), pp 215–224.

[12] C. Bordenave, D. McDonald, A. Proutiere, A particle system in interaction with a rapidly varying environment: Mean-field limits and applications, Networks and Heterogeneous Media, 5(1) (2010) 31–62. | Zbl 1262.60092

[13] K.A. Borovkov, Propagation of chaos for queueing networks, Theory of Probability & Its Applications, 42(3) (1998) 385–394.

[14] A. Bovier, Markov processes and metastability, Lecture Notes TUB, (2003), pp 1–75.

[15] A. Bovier, Metastability: A potential theoretic approach. In: Proceedings oh the International Congress of Mathematicians: Invited Lectures, (2006), pp 499–518. | Zbl 1099.60052

[16] A. Bovier, M. Eckhoff, V. Gayrard, M. Klein, Metastability in stochastic dynamics of disorderedmean-field models, Probability Theory and Related Fields, 119(1) (2001) 99–161. | Zbl 1012.82015

[17] A. Bovier, M. Eckhoff, V. Gayrard, M. Klein, Metastability and low lying spectral in reversibleMarkov chains, Communications in Mathematical Physics, 228(2) (2002) 219–255. [Crossref] | Zbl 1010.60088

[18] A. Budhiraja, P. Dupuis, M. Fischer, K. Ramanan, Local stability of Kolmogorov forward equations for finite state nonlinear Markov processes, arXiv preprint: arXiv:1412.5555, (2014). | Zbl 1337.60240

[19] A. Budhiraja, P. Dupuis, M. Fischer, K. Ramanan, Limits of relative entropies associated with weakly interacting particle systems, arXiv preprint: arXiv:1412.5553, (2014). | Zbl 1321.60202

[20] A. Budhiraja, A.P. Majumder, Long time results for a weakly interacting particle system in discrete time, arXiv preprint: arXiv:1401.3423, (2014). | Zbl 1316.60142

[21] M.F. Chen, From Markov Chains to Non-equilibrium Particle Systems. World Scientific, (2004). | Zbl 1078.60003

[22] R.W.R. Darling, J.R. Norris, Differential equation approximations for Markov chains, Probability surveys, 5(1) (2008) 37–79. | Zbl 1189.60152

[23] D.A. Dawson, Critical dynamics and fluctuations for a mean-field model of cooperative behavior, Journal of Statistical Physics, 31(1) (1983) 29–85. [Crossref]

[24] D.A. Dawson, X. Zheng, Law of large numbers and central limit theorem for unbounded jump mean-field models, Advances in Applied Mathematics, 12(3) (1991) 293–326. | Zbl 0751.60080

[25] F. Delcoigne, G. Fayolle, Thermodynamical limit and propagation of chaos in polling systems,Markov Processes and Related Fields, 5(1) (1999) 89–124. | Zbl 0920.60072

[26] F. den Hollander, Metastability under stochastic dynamics, Stochastic Processes and their Applications, 114(1) (2004) 1–26. | Zbl 1075.60127

[27] R.L. Dobrushin, Queuing networks - without explicit solutions and without computer simulation. In: Conference on Applied Probability in Engineering, Computer and Communication Sciences: Keynote Lecture, Paris, (1993).

[28] N.G. Duffield, Local mean-field Markov processes: An application to message-switching networks, Probability Theory and Related Fields, 93(4) (1992) 485–505.

[29] N.G. Duffield, R.F. Werner, Local dynamics of mean-field quantum systems, Helvetica Physica Acta, 65(8) (1991) 1016–1054.

[30] P. Dupuis, M. Fischer, On the construction of Lyapunov functions for nonlinear Markov processes via relative entropy. Submitting for publication, (2011).

[31] S.N. Ethier, T.G. Kurtz, Markov Processes: Characterization and Convergence. John Wiley & Sons, (1986). | Zbl 0592.60049

[32] T.D. Frank, Nonlinear Markov processes, Physics Letters A, 372(25) (2008) 4553–4555. | Zbl 1221.60105

[33] M.I. Freidlin, A.D. Wentzell, Random Perturbations of Dynamic Systems. Springer, (1984). | Zbl 0679.60036

[34] C. Fricker, N. Gast, Incentives and redistribution in homogeneous bike-sharing systemswith stations of finite capacity, EURO Journal on Transportation and Logistics, Published Online: June 7, (2014), pp 1–31.

[35] C. Fricker, N. Gast, H. Mohamed. Mean field analysis for inhomogeneous bike sharing systems. In: DMTCS Proceedings, 1 (2012), pp 365–376. | Zbl 1296.90019

[36] A. Galves, E. Olivieri, M.E. Vares, Metastability for a class of dynamical systems subject to small random perturbations, The Annals of Probability, 15(4) (1987) 1288–1305. [Crossref] | Zbl 0709.60058

[37] N. Gast, B. Gaujal, A mean field model of work stealing in large-scale systems, ACM SIGMETRICS Performance Evaluation Review, 38(1) (2010) 13–24.

[38] N. Gast, B. Gaujal, A mean field approach for optimization in discrete time, Discrete Event Dynamic Systems, 21(1) (2011) 63–101. | Zbl 1233.90275

[39] N. Gast, B. Gaujal, J.Y. Le Boudec, Mean field for Markov decision processes: from discrete to continuous optimization, IEEE Transactions on Automatic Control, 57(9) (2012) 2266–2280. [Crossref]

[40] R.J. Gibbens, P.J. Hunt, F.P. Kelly, Bistability in communication networks. In: Disorder in Physical Systems: A Volume in Honour of John M. Hammersley, (Eds G. Grimmett and D. Welsh), Oxford University Press, (1990), pp 113–127. | Zbl 0721.60103

[41] C. Graham, Chaoticity on path space for a queueing network with selection of the shortest queue among several, Journal of Applied Probability, 37(1) (2000) 198–201. | Zbl 0961.60091

[42] C. Graham, Functional central limit theorems for a large network in which customers join the shortest of several queues, Probability Theory and Related Fields, 131(1) (2004) 97–120. | Zbl 1058.60077

[43] R.A. Hayden, A. Stefanek, J.T. Bradley, Fluid computation of passage-time distributions in large Markov models, Theoretical Computer Science, 413(1) (2012) 106–141. | Zbl 1234.68318

[44] P.J. Hunt, T.G. Kurtz, Large loss networks, Stochastic Processes and their Applications, 53(2) (1994) 363–378. | Zbl 0810.60087

[45] J. Jacod, A. Shiryaev, Limit Theorems for Stochastic Processes. Springer, (2003). | Zbl 1018.60002

[46] F.I. Karpelevich, A.N. Rybko, Thermodynamical limit for symmetric closed queuing networks, Translations of the American Mathematical Society, 198(2) (2000) 133–156. | Zbl 0961.60092

[47] F.P. Kelly, Loss networks, The Annals of Applied Probability, 1(3) (1991) 319–378. [Crossref] | Zbl 0743.60099

[48] C. Kipnis, C. Landim, Scaling Limits of Interacting Particle Systems. Springer, (1999). | Zbl 0927.60002

[49] V.N. Kolokoltsov, Nonlinear Markov Processes and Kinetic Equations. Cambridge University Press, (2010). | Zbl 1222.60003

[50] V.N. Kolokoltsov, Nonlinear Lévy and nonlinear Feller processes: An analytic introduction, arXiv preprint: arXiv:1103.5591, (2011).

[51] V.N. Kolokoltsov, J.J. Li,W. Yang, Mean field games and nonlinearMarkov processes, arXiv preprint: arXiv: 1112.3744, (2011).

[52] T.G. Kurtz, Solution of ordinary differential equations as limits of pure jumpMarkov processes, Journal of Applied Probability, 7(1) (1970) 49–58. [Crossref] | Zbl 0191.47301

[53] T.G. Kurtz, Limit theorems for sequences of jump Markov processes approximating ordinary differential processes, Journal of Applied Probability, 8(2) (1971) 344–356. [Crossref] | Zbl 0219.60060

[54] T.G. Kurtz, Strong approximation theorems for density dependent Markov chains, Stochastic Processes and Their Applications, 6(3) (1978) 223–240. | Zbl 0373.60085

[55] J.Y. Le Boudec, D. McDonald, J. Mundinger, A generic mean-field convergence result for systems of interacting objects. In: Proc. Conf. IEEE on the Quantitative Evaluation of Systems, (2007), pp 3–18.

[56] Q.L. Li, Constructive Computation in Stochastic Models with Applications: The RG-Factorizations. Springer, (2010). | Zbl 1208.60073

[57] Q.L. Li, Tail probabilities in queueing processes, Asia-Pacific Journal of Operational Research, 31(2) (2014) 1–31. | Zbl 1291.90072

[58] Q.L. Li, G.R. Dai, J.C.S. Lui, Y. Wang, The mean-field computation in a supermarket model with server multiple vacations, Discrete Event Dynamic Systems, 24(4) (2014) 473–522. | Zbl 1302.93197

[59] Q.L. Li, Y. Du, G.R. Dai, M. Wang, On a doubly dynamically controlled supermarket model with impatient customers, Computers & Operations Research, 55 (2014) 76–87. | Zbl 1348.90200

[60] Q.L. Li, J.C.S. Lui, Block-structured supermarket models, Discrete Event Dynamic Systems, Published Online: June 29, (2014), pp 1–36.

[61] Q.L. Li, F.F. Yang, Mean-field analysis for heterogeneous work stealing models. In: Information Technologies andMathematical Modelling: Queueing Theory and Applications, Springer, (2015), pp 28–40.

[62] T.M. Liggett, Interacting Particle Systems. Springer, (2005).

[63] M.J. Luczak, C. McDiarmid, On themaximumqueue length in the supermarket model, The Annals of Probability, 34(2) (2006) 493–527. [Crossref] | Zbl 1102.60083

[64] M.J. Luczak, C. McDiarmid, Asymptotic distributions and chaos for the supermarket model, Electronic Journal of Probability, 12(1) (2007) 75–99. | Zbl 1131.60005

[65] J.B. Martin, Point processes in fast Jackson networks, The Annals of Applied Probability, 11(3) (2001) 650–663 | Zbl 1021.90007

[66] J.B. Martin, Y.M. Suhov, Fast Jackson networks, The Annals of Applied Probability, 9(3) (1999) 854–870. | Zbl 0972.90008

[67] V.V. Marbukh, Investigation of a fully connected channel-switching network with many nodes and alternative routes, Automation & Remote Control, 44(12) (1984) 1601–1608. | Zbl 0542.94041

[68] M.D. Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, Ph.D. thesis, Department of Computer Science, University of California at Berkeley, USA, (1996).

[69] S.A. Muzychka, K.L. Vaninsky, A class of nonlinear random walks related to the Ornstein-Uhlenbeck process, Markov Processes and Related Fields, 17(2) (2011) 277–304. | Zbl 1235.60097

[70] E. Olivieri, M.E. Vares, Large Deviations and Metastability. Cambridge University Press, (2005).

[71] V.I. Oseledets, D.V. Khmelev, Stochastic transportation networks and stability of dynamical systems, Theory of Probability & Its Applications, 46(1) (2002) 154–161. | Zbl 1002.60090

[72] S.G. Peng, Nonlinear expectations and nonlinear Markov chains, Chinese Annals of Mathematics, 26(2) (2005) 159–184. | Zbl 1077.60045

[73] L.C.G. Rogers, D. Williams, Diffusions, Markov Processes, and Martingales, Vol. 1: Foundations. John Wiley & Sons, (1994). | Zbl 0826.60002

[74] A.N. Rybko, S. Shlosman, Poisson Hypothesis for information networks (a study in non-linear Markov processes), arXiv preprint: arXiv:0303010, (2003).

[75] T. Shiga, H. Tanaka, Central limit theorem for a system ofMarkovian particleswithmean field interactions, Probability Theory and Related Fields, 69(3) (1985) 439–459. | Zbl 0607.60095

[76] F. Spitzer, Interaction of Markov processes, Advances in Mathematics, 5(2) (1970) 246–290. | Zbl 0312.60060

[77] Y.M. Suhov, N.D. Vvedenskaya, Fast Jackson networks with dynamic routing, Problems of Information Transmission, 38(2) (2002) 136–153. | Zbl 1021.60072

[78] A. Sznitman, Topics in Propagation of Chaos. Springer-Verlag lecture notes in mathematics 1464, (1989), pp 165–251.

[79] D. Tibi, Metastability in communication networks, arXiv preprint: arXiv:1002.0796, (2010).

[80] S.R.E. Turner, Resource Pooling in Stochastic Networks, Ph.D. Thesis, Statistical Laboratory, Christ’s College, University of Cambridge, (1996).

[81] A.G. Turner, Convergence of Markov processes near saddle fixed points, The Annals of Probability, 35(3) (2007) 1141–1171. [Crossref] | Zbl 1134.60019

[82] K. Vaninsky, S. Myzuchka, A. Lukov, A multi-agent nonlinear Markov model of the order book, arXiv preprint: arXiv:1208.3083, (2012).

[83] N.D. Vvedenskaya, R.L. Dobrushin, F.I. Karpelevich, Queueing system with selection of the shortest of two queues: An asymptotic approach, Problems of Information Transmission, 32(1) (1996) 20–34. | Zbl 0898.60095

[84] N.D. Vvedenskaya, Y.M. Suhov, Dobrushin’s mean-field limit for a queue with dynamic routing, Markov Processes and Related Fields, 3(3) (1997) 493–526.

[85] W. Whitt, Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues. Springer, (2002). | Zbl 0993.60001

[86] S. Zachary, I. Ziedins, A refinement of the Hunt-Kurtz theory of large loss networks,with an application to virtual partitioning, The Annals of Applied Probability, 12(1) (2002) 1–22. | Zbl 1012.60083