Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T18:49:15.694Z Has data issue: false hasContentIssue false
  • English
  • Français

Random walks in a queueing network environment

Part of: Markov processes

Published online by Cambridge University Press:  21 June 2016

M. Gannon ,
E. Pechersky ,
Y. Suhov  and
A. Yambartsev
M. Gannon*
Affiliation:
University of Sao Paulo
E. Pechersky*
Affiliation:
University of Sao Paulo and IITP, Moscow
Y. Suhov*
Affiliation:
IITP, Moscow, University of Sao Paulo, University of Cambridge, and Penn State University
A. Yambartsev*
Affiliation:
University of Sao Paulo and Oregon State University
*
* Postal address: IME, University of Sao Paulo (USP), Sao Paulo 05508-090, SP, Brazil.
* Postal address: IME, University of Sao Paulo (USP), Sao Paulo 05508-090, SP, Brazil.
**** Postal address: Statistical Laboratory, DPMMS, University of Cambridge, Cambridge CB3 0WB, UK. Email address: yms@statslab.cam.ac.uk
* Postal address: IME, University of Sao Paulo (USP), Sao Paulo 05508-090, SP, Brazil.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We propose a class of models of random walks in a random environment where an exact solution can be given for a stationary distribution. The environment is cast in terms of a Jackson/Gordon–Newell network although alternative interpretations are possible. The main tool is the detailed balance equations. The difference compared to earlier works is that the position of the random walk influences the transition intensities of the network environment and vice versa, creating strong correlations. The form of the stationary distribution is closely related to the well-known product formula.

Keywords

Continuous-time Markov processqueueing networkJackson networksimple exclusionzero rangereversibilitystationary probabilityproduct formula

MSC classification

Primary: 60J27: Continuous-time Markov processes on discrete state spaces
Secondary: 60J28: Applications of continuous-time Markov processes on discrete state spaces

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 2 , June 2016 , pp. 448 - 462
Copyright
Copyright © Applied Probability Trust 2016 

References

[1]Baskett, F., Chandy, K. M., Muntz, R. R. and Palacios, F. G. (1975).Open, closed and mixed networks of queues with different classes of customers.J. Assoc. Comput. Mach. 22, 248–260.Google Scholar
[2]Černý, J. and Wassmer, T. (2014).Randomly trapped random walks on Zd. Preprint. Available at http://arxiv.org/abs/1406.0363v4.Google Scholar
[3]Dobrushin, R. L. (1971).Markov processes with a large number of locally interacting components: existence of a limit process and its ergodicity.Problems Information Transmission 7, 149–164.Google Scholar
[4]Dobrushin, R. L. (1971).Markov processes with many locally interacting components – the reversible case and some generalizations.Problems Information Transmission 7, 235–241.Google Scholar
[5]Economou, A. (2005).Generalized product-form stationary distributions for Markov chains in random environments with queueing applications.Adv. Appl. Prob. 37, 185–211.CrossRefGoogle Scholar
[6]Evans, M. R. and Hanney, T. (2005).Nonequilibrium statistical mechanics of the zero-range process and related models.J. Phys. A 38, R195–R240.CrossRefGoogle Scholar
[7]Gordon, W. J. and Newell, G. F. (1967).Closed queuing systems with exponential servers.Operat. Res. 15, 254–265.Google Scholar
[8]Grosskinsky, S., Schütz, G. M. and Spohn, H. (2003).Condensation in the zero range process: stationary and dynamical properties.J. Statist. Phys. 113, 389–410.CrossRefGoogle Scholar
[9]Ignatiouk-Robert, I. and Tibi, D. (2012).Explicit Lyapunov functions and estimates of the essential spectral radius for Jackson networks. Preprint. Available at http://arxiv.org/abs/1206.3066v1.Google Scholar
[10]Jackson, J. R. (1957).Networks of waiting lines.Operat. Res. 5, 518–521.Google Scholar
[11]Jackson, J. R. (1963).Jobshop-like queueing systems.Manag. Sci. 10, 131–142.CrossRefGoogle Scholar
[12]Kelly, F. P. (2011).Reversibility and Stochastic Networks.Cambridge University Press.Google Scholar
[13]Liggett, T. M. (1985).Interacting Particle Systems.Springer, New York.CrossRefGoogle Scholar
[14]Liggett, T. M. (1999).Stochastic Interacting Systems: Contact, Voter and Exclusion.Springer, Berlin.CrossRefGoogle Scholar
[15]Liggett, T. M. (2010).Continuous Time Markov Processes: An Introduction.American Mathematical Society, Providence, RI.CrossRefGoogle Scholar
[16]Malyshev, V. A. (2009).On mathematical models of the service networks.J. Automation Remote Control 70, 1947–1953.CrossRefGoogle Scholar
[17]Nelson, R. D. (1993).The mathematics of product form queuing networks.ACM Comput. Surveys 25, 339–369.Google Scholar
[18]Serfozo, R. F. (1992).Reversibility and compound birth--death and migration processes. In Queueing and Related Models, Oxford University Press, pp.65–89.Google Scholar
[19]Serfozo, R. F. (1999).Introduction to Stochastic Networks.Springer, New York.Google Scholar
[20]Spitzer, F. (1970).Interaction of Markov processes.Adv. Math. 5, 246–290.Google Scholar
[21]Sznitman, A.-S. (2002).Lectures on random motions in random media. In Ten Lectures on Random Media (DMV Seminar 32), Birkhäuser, Basel, pp.1–51.Google Scholar
[22]Zhu, Y. (1994).Markovian queueing networks in a random environment.Operat. Res. Lett. 15, 11–17.Google Scholar