Nonlinear Markov processes in big networks
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.
-  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.
-  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]
-  N. Antunes, C. Fricker, P. Robert, D. Tibi, Stochastic networks with multiple stable points, The Annals of Probability, 36(1) (2008) 255–278. [Crossref]
-  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]
-  F. Baccelli, A.N. Rybko, S. Shlosman, Queuing networks with varying topology–a mean-field approach, arXiv preprint: arXiv:1311.3898, (2013).
-  J. Beltran, C. Landim, Tunneling and metastability of continuous time Markov chains, Journal of Statistical Physics, 140(6) (2010) 1065–1114. [Crossref]
-  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]
-  M. Benaim, On gradient like properties of population games, learning models and self reinforced processes, arXiv preprint: arXiv:1409.4091, (2014).
-  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.
-  M. Benaim, J.Y. Le Boudec, On mean field convergence and stationary regime, arXiv preprint: arXiv:1111.5710, (2011).
-  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.
-  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.
-  K.A. Borovkov, Propagation of chaos for queueing networks, Theory of Probability & Its Applications, 42(3) (1998) 385–394.
-  A. Bovier, Markov processes and metastability, Lecture Notes TUB, (2003), pp 1–75.
-  A. Bovier, Metastability: A potential theoretic approach. In: Proceedings oh the International Congress of Mathematicians: Invited Lectures, (2006), pp 499–518.
-  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.
-  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]
-  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).
-  A. Budhiraja, P. Dupuis, M. Fischer, K. Ramanan, Limits of relative entropies associated with weakly interacting particle systems, arXiv preprint: arXiv:1412.5553, (2014).
-  A. Budhiraja, A.P. Majumder, Long time results for a weakly interacting particle system in discrete time, arXiv preprint: arXiv:1401.3423, (2014).
-  M.F. Chen, From Markov Chains to Non-equilibrium Particle Systems. World Scientific, (2004).
-  R.W.R. Darling, J.R. Norris, Differential equation approximations for Markov chains, Probability surveys, 5(1) (2008) 37–79.
-  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]
-  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.
-  F. Delcoigne, G. Fayolle, Thermodynamical limit and propagation of chaos in polling systems,Markov Processes and Related Fields, 5(1) (1999) 89–124.
-  F. den Hollander, Metastability under stochastic dynamics, Stochastic Processes and their Applications, 114(1) (2004) 1–26.
-  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).
-  N.G. Duffield, Local mean-field Markov processes: An application to message-switching networks, Probability Theory and Related Fields, 93(4) (1992) 485–505.
-  N.G. Duffield, R.F. Werner, Local dynamics of mean-field quantum systems, Helvetica Physica Acta, 65(8) (1991) 1016–1054.
-  P. Dupuis, M. Fischer, On the construction of Lyapunov functions for nonlinear Markov processes via relative entropy. Submitting for publication, (2011).
-  S.N. Ethier, T.G. Kurtz, Markov Processes: Characterization and Convergence. John Wiley & Sons, (1986).
-  T.D. Frank, Nonlinear Markov processes, Physics Letters A, 372(25) (2008) 4553–4555.
-  M.I. Freidlin, A.D. Wentzell, Random Perturbations of Dynamic Systems. Springer, (1984).
-  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.
-  C. Fricker, N. Gast, H. Mohamed. Mean field analysis for inhomogeneous bike sharing systems. In: DMTCS Proceedings, 1 (2012), pp 365–376.
-  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]
-  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.
-  N. Gast, B. Gaujal, A mean field approach for optimization in discrete time, Discrete Event Dynamic Systems, 21(1) (2011) 63–101.
-  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]
-  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.
-  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.
-  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.
-  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.
-  P.J. Hunt, T.G. Kurtz, Large loss networks, Stochastic Processes and their Applications, 53(2) (1994) 363–378.
-  J. Jacod, A. Shiryaev, Limit Theorems for Stochastic Processes. Springer, (2003).
-  F.I. Karpelevich, A.N. Rybko, Thermodynamical limit for symmetric closed queuing networks, Translations of the American Mathematical Society, 198(2) (2000) 133–156.
-  F.P. Kelly, Loss networks, The Annals of Applied Probability, 1(3) (1991) 319–378. [Crossref]
-  C. Kipnis, C. Landim, Scaling Limits of Interacting Particle Systems. Springer, (1999).
-  V.N. Kolokoltsov, Nonlinear Markov Processes and Kinetic Equations. Cambridge University Press, (2010).
-  V.N. Kolokoltsov, Nonlinear Lévy and nonlinear Feller processes: An analytic introduction, arXiv preprint: arXiv:1103.5591, (2011).
-  V.N. Kolokoltsov, J.J. Li,W. Yang, Mean field games and nonlinearMarkov processes, arXiv preprint: arXiv: 1112.3744, (2011).
-  T.G. Kurtz, Solution of ordinary differential equations as limits of pure jumpMarkov processes, Journal of Applied Probability, 7(1) (1970) 49–58. [Crossref]
-  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]
-  T.G. Kurtz, Strong approximation theorems for density dependent Markov chains, Stochastic Processes and Their Applications, 6(3) (1978) 223–240.
-  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.
-  Q.L. Li, Constructive Computation in Stochastic Models with Applications: The RG-Factorizations. Springer, (2010).
-  Q.L. Li, Tail probabilities in queueing processes, Asia-Pacific Journal of Operational Research, 31(2) (2014) 1–31.
-  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.
-  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.
-  Q.L. Li, J.C.S. Lui, Block-structured supermarket models, Discrete Event Dynamic Systems, Published Online: June 29, (2014), pp 1–36.
-  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.
-  T.M. Liggett, Interacting Particle Systems. Springer, (2005).
-  M.J. Luczak, C. McDiarmid, On themaximumqueue length in the supermarket model, The Annals of Probability, 34(2) (2006) 493–527. [Crossref]
-  M.J. Luczak, C. McDiarmid, Asymptotic distributions and chaos for the supermarket model, Electronic Journal of Probability, 12(1) (2007) 75–99.
-  J.B. Martin, Point processes in fast Jackson networks, The Annals of Applied Probability, 11(3) (2001) 650–663
-  J.B. Martin, Y.M. Suhov, Fast Jackson networks, The Annals of Applied Probability, 9(3) (1999) 854–870.
-  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.
-  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).
-  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.
-  E. Olivieri, M.E. Vares, Large Deviations and Metastability. Cambridge University Press, (2005).
-  V.I. Oseledets, D.V. Khmelev, Stochastic transportation networks and stability of dynamical systems, Theory of Probability & Its Applications, 46(1) (2002) 154–161.
-  S.G. Peng, Nonlinear expectations and nonlinear Markov chains, Chinese Annals of Mathematics, 26(2) (2005) 159–184.
-  L.C.G. Rogers, D. Williams, Diffusions, Markov Processes, and Martingales, Vol. 1: Foundations. John Wiley & Sons, (1994).
-  A.N. Rybko, S. Shlosman, Poisson Hypothesis for information networks (a study in non-linear Markov processes), arXiv preprint: arXiv:0303010, (2003).
-  T. Shiga, H. Tanaka, Central limit theorem for a system ofMarkovian particleswithmean field interactions, Probability Theory and Related Fields, 69(3) (1985) 439–459.
-  F. Spitzer, Interaction of Markov processes, Advances in Mathematics, 5(2) (1970) 246–290.
-  Y.M. Suhov, N.D. Vvedenskaya, Fast Jackson networks with dynamic routing, Problems of Information Transmission, 38(2) (2002) 136–153.
-  A. Sznitman, Topics in Propagation of Chaos. Springer-Verlag lecture notes in mathematics 1464, (1989), pp 165–251.
-  D. Tibi, Metastability in communication networks, arXiv preprint: arXiv:1002.0796, (2010).
-  S.R.E. Turner, Resource Pooling in Stochastic Networks, Ph.D. Thesis, Statistical Laboratory, Christ’s College, University of Cambridge, (1996).
-  A.G. Turner, Convergence of Markov processes near saddle fixed points, The Annals of Probability, 35(3) (2007) 1141–1171. [Crossref]
-  K. Vaninsky, S. Myzuchka, A. Lukov, A multi-agent nonlinear Markov model of the order book, arXiv preprint: arXiv:1208.3083, (2012).
-  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.
-  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.
-  W. Whitt, Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues. Springer, (2002).
-  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.