Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-26T08:20:25.904Z Has data issue: false hasContentIssue false
  • English
  • Français

Correlation formulas for Markovian network processes in a random environment

Part of: Special processes Markov processes

Published online by Cambridge University Press:  24 March 2016

Hans Daduna  and
Ryszard Szekli
Hans Daduna*
Affiliation:
Hamburg University
Ryszard Szekli*
Affiliation:
Wrocław University
*
* Postal address: Department of Mathematics, University of Hamburg, Bundesstrasse 55, 20146 Hamburg, Germany. Email address: [email protected]
** Postal address: Mathematical Institute, Wrocław University, pl. Grunwaldzki 2/4, 50-384 Wrocław, Poland.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider Markov processes, which describe, e.g. queueing network processes, in a random environment which influences the network by determining random breakdown of nodes, and the necessity of repair thereafter. Starting from an explicit steady-state distribution of product form available in the literature, we note that this steady-state distribution does not provide information about the correlation structure in time and space (over nodes). We study this correlation structure via one-step correlations for the queueing-environment process. Although formulas for absolute values of these correlations are complicated, the differences of correlations of related networks are simple and have a nice structure. We therefore compare two networks in a random environment having the same invariant distribution, and focus on the time behaviour of the processes when in such a network the environment changes or the rules for travelling are perturbed. Evaluating the comparison formulas we compare spectral gaps and asymptotic variances of related processes.

Keywords

Product-form networkspace-time correlationspectral gapasymptotic variancePeskun ordering

MSC classification

Primary: 60K25: Queueing theory
Secondary: 60J25: Continuous-time Markov processes on general state spaces 60K37: Processes in random environments
Type
Research Article
Information
Advances in Applied Probability , Volume 48 , Issue 1 , March 2016 , pp. 176 - 198
Copyright
Copyright © Applied Probability Trust 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Balsamo, S. and Marin, A. (2013). Separable solutions for Markov processes in random environments. Europ. J. Operat. Res. 229, 391–403. CrossRefGoogle Scholar
[2]Balsamo, S., de Nitto Personé, V. and Onvural, R. (2001). Analysis of Queueing Networks with Blocking. Kluwer, Boston, MA. Google Scholar
[3]Chen, M.-F. (2004). From Markov Chains to Non-Equilibrium Particle Systems, 2nd edn. World Scientific, River Edge, NJ. Google Scholar
[4]Daduna, H. and Szekli, R. (2008). Impact of routeing on correlation strength in stationary queueing network processes. J. Appl. Prob. 45, 846–878. Google Scholar
[5]Daduna, H. and Szekli, R. (2013). Correlation formulas for Markovian network processes in a random environment. Preprint 2013-05, Department of Mathematics, University of Hamburg. Google Scholar
[6]Daduna, H. and Szekli, R. (2015). Correlation formulas for networks with finite capacity. Preprint, Department of Mathematics, University of Hamburg (in preparation). Google Scholar
[7]Economou, A. (2005). Generalized product-form stationary distributions for Markov chains in random environments with queueing applications. Adv. Appl. Prob. 37, 185–211. Google Scholar
[8]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.3066. Google Scholar
[9]Jackson, J. R. (1957). Networks of waiting lines. Operat. Res. 5, 518–521. Google Scholar
[10]Liggett, T. M. (1989). Exponential L 2 convergence of attractive reversible nearest particle systems. Ann. Prob. 17, 403–432. CrossRefGoogle Scholar
[11]Lorek, P. and Szekli, R. (2015). Computable bounds on the spectral gap for unreliable Jackson networks. Adv. Appl. Prob. 47, 402–424. Google Scholar
[12]Mira, A. and Geyer, C. J. (1999). Ordering Monte Carlo Markov chains. Tech. Rep., School of Statistics, University of Minnesota. Google Scholar
[13]Perros, H. G. (1990). Approximation algorithms for open queueing networks with blocking. In Stochastic Analysis of Computer and Communication Systems, North-Holland, Amsterdam, pp. 451–498. Google Scholar
[14]Peskun, P. H. (1973). Optimum Monte-Carlo sampling using Markov chains. Biometrika 60, 607–612. CrossRefGoogle Scholar
[15]Sauer, C. (2006). Stochastic product form networks with unreliable nodes: analysis of performance and availability. Doctoral Thesis, Department of Mathematics, University of Hamburg. Google Scholar
[16]Sauer, C. and Daduna, H. (2003). Availability formulas and performance measures for separable degradable networks. Econom. Quality Control 18, 165–194. Google Scholar
[17]Tierney, L. (1998). A note on Metropolis–Hastings kernels for general state spaces. Ann. Appl. Prob. 8, 1–9. CrossRefGoogle Scholar
[18]Van Dijk, N. M. (1988). On Jackson's product form with 'jump-over' blocking. Operat. Res. Lett. 7, 233–235. CrossRefGoogle Scholar
[19]Van Dijk, N. M. (2011). On practical product form characterizations. In Queueing Networks (Internat. Ser. Operat. Res. Manag. Sci. 154), Springer, New York, pp. 1–83. Google Scholar
[20]Van Doorn, E. A. (2002). Representations for the rate of convergence of birth–death processes. Theory Prob. Math. Statist. 65, 37–43. Google Scholar
[21]Zhu, Y. (1994). Markovian queueing networks in a random environment. Operat. Res. Lett. 15, 11–17. CrossRefGoogle Scholar