Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-05T10:15:15.077Z Has data issue: false hasContentIssue false

On ergodicity and recurrence properties of a Markov chain by an application to an open jackson network

Published online by Cambridge University Press:  01 July 2016

Arie Hordijk
Affiliation:
University of Leiden
Flora Spieksma*
Affiliation:
University of Leiden
*
The research of this author was supported by the Netherlands Organisation for Scientific Research N.W.O.

Abstract

This paper gives an overview of recurrence and ergodicity properties of a Markov chain. Two new notions for ergodicity and recurrence are introduced. They are called μ -geometric ergodicity and μ -geometric recurrence respectively. The first condition generalises geometric as well as strong ergodicity. Our key theorem shows that μ -geometric ergodicity is equivalent to weak μ -geometric recurrence. The latter condition is verified for the time-discretised two-centre open Jackson network. Hence, the corresponding two-dimensional Markov chain is μ -geometrically and geometrically ergodic, but not strongly ergodic. A consequence of μ -geometric ergodicity with μ of product-form is the convergence of the Laplace-Stieltjes transforms of the marginal distributions. Consequently all moments converge.

Type
Research Article
Copyright
Copyright © Applied Probability Trust 1992 

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.)

Footnotes

Postal address for both authors: Department of Mathematics and Computer Science, University of Leiden, Niels Bohrweg 1, 2333CA Leiden, The Netherlands.

References

Asmussen, S. (1987) Applied Probability and Queues. Wiley, New York.Google Scholar
Chan, K. S. (1989) A note on the geometric ergodicity of a Markov chain. Adv. Appl. Prob. 21, 702704.Google Scholar
Chung, K. L. (1967) Markov Chains with Stationary Transition Probabilities. Springer-Verlag, Berlin.Google Scholar
Dekker, R. (1985) Denumerable Markov decision chains: optimal policies for small interest rates. Unpublished doctorial dissertation, University of Leiden (available on request from the author).Google Scholar
Dekker, R. and Hordijk, A. (1988) Average, sensitive and Blackwell optimal policies in denumerable Markov decision chains with unbounded rewards. Math. Operat. Res. 13, 395421.Google Scholar
Dekker, R. and Hordijk, A. (1989) Recurrence conditions for average and Blackwell optimality in denumerable state Markov decision chains. Math. Operat. Res. To appear.Google Scholar
Dekker, R., Hordijk, A. and Spieksma, F. M. (1991) On the relation between recurrence and ergodicity conditions in denumerable Markov decision chains. Submitted for publication.Google Scholar
Federgruen, A., Hordijk, A. and Tijms, H. C. (1978a) Recurrence conditions in denumerable state Markov decision processes. In Dynamic Programming and its Applications, ed. Puterman, M. L. pp. 322. Academic Press, New York.Google Scholar
Federgruen, A., Hordijk, A. and Tijms, H. C. (1978b) A note on simultaneous recurrence conditions on a set of denumerable stochastic matrices. J. Appl. Prob. 15, 842847.CrossRefGoogle Scholar
Foster, F. G. (1953) On the stochastic matrices associated with certain queueing processes. Ann. Math. Statist 24, 355360.Google Scholar
Hajek, B. (1982) Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Prob. 14, 502525.Google Scholar
Hordijk, A. (1974) Dynamic Programming and Markov Potential Theory. Mathematical Centre Tract 51, Amsterdam.Google Scholar
Hordijk, A. and Spieksma, F. M. (1991) On the convergence of successive approximation under strong recurrence conditions.Google Scholar
Huang, C. and Isaacson, D. (1976) Ergodicity using mean visit times. J. London Math. Soc. B 14, 570576.Google Scholar
Isaacson, D. (1979) A characterization of geometric ergodicity. Z. Wahrscheinlichkeitsth. 49, 267273.CrossRefGoogle Scholar
Isaacson, D. and Tweedie, R. L. (1978) Criteria for strong ergodicity of Markov chains. J. Appl. Prob. 15, 8795.CrossRefGoogle Scholar
Isaacson, D. and Luecke, G. R. (1978) Strongly ergodic Markov chains and rates of convergence using spectral conditions. Stoch. Proc. Appl. 7, 113121.Google Scholar
Kelly, F. P. (1979) Reversibility and Stochastic Networks. Wiley, New York.Google Scholar
Kendall, D. G. (1959) Unitary dilations of Markov transition operators, and the corresponding integral representations for transition-probability matrices. In Probability and Statistics, ed. Grenander, U., pp. 139161. Almqvist and Wiksell, Stockholm; Wiley, New York.Google Scholar
Kendall, D. G. (1960) Geometric ergodicity and the theory of queues. In Mathematical Methods in the Social Sciences, 1959 , ed. Arrow, K. J., Karlin, S. and Suppes, P., pp. 176195. Stanford University Press.Google Scholar
Lasserre, J. B. (1988) Conditions for existence of average and Blackwell optimal stationary policies in denumerable Markov decision processes. J. Math. Anal. Appl. 136, 479490.Google Scholar
Neveu, J. (1965) Mathematical Foundations of the Calculus of Probability. Holden-Day, San Francisco.Google Scholar
Nummelin, E. (1984) General Irreducible Markov Chains and Non-negative Operators. Cambridge University Press.Google Scholar
Nummelin, E. and Tuominen, F. (1982) Geometric ergodicity of Harris recurrent Markov chains with applications to renewal theory. Stoch. Proc. Appl. 12, 187202.Google Scholar
Nummelin, E. and Tweedie, R. (1978) Geometric ergodicity and R-positivity for general Markov chains. Ann. Prob. 6, 404420.Google Scholar
Popov, N. N. (1977) Conditions for geometric ergodicity of countable Markov chains. Soviet Math. Dokl. 18, 676679.Google Scholar
Spieksma, F. M. (1990) Geometrically Ergodic Markov Chains and the Optimal Control of Queues. Unpublished doctoral dissertation, University of Leiden (available on request from the author).Google Scholar
Spieksma, F. M. (1991a) Geometric ergodicity of the ALOHA-system and a coupled processors model. Prob. Eng. Inf. Sci. 5, 1542.CrossRefGoogle Scholar
Spieksma, F. M. (1991b) The existence of sensitive optimal policies in two multi-dimensional queueing models. Ann. Operat. Res. 28, 273296.Google Scholar
Spieksma, F. M. (1991C). A recurrence type characterisation of µ-exponential ergodicity, with queueing applications. Submitted for publication.Google Scholar
Szpankowski, W. (1988) Stability conditions for multi-dimensional queueing systems with computer applications. Operat. Res. 36, 944957.CrossRefGoogle Scholar
Szpankowski, W. (1990) Towards computable stability criteria for some multidimensional stochastic processes. In Stochastic Analysis of Computer and Communication Systems, ed. Takagi, H., pp 131172. North-Holland, Amsterdam.Google Scholar
Thomas, L. C. (1980) Connectedness conditions for denumerable state Markov decision processes. In Recent Developments in Markov Decision Processes, ed. Hartley, R., Thomas, L. C. and White, D. J., pp. 181204. Academic Press, New York.Google Scholar
Tuominen, P. and Tweedie, R. L. (1979a) Exponential decay and ergodicity of general Markov processes and their discrete skeletons. Adv. Appl. Prob. 11, 784803.Google Scholar
Tuominen, P. and Tweedie, R. L. (1979b) Exponential ergodicity in Markovian queueing and dam models. J. Appl. Prob. 16, 867880.Google Scholar
Tweedie, R. L. (1976) Criteria for classifying general Markov chains. Adv. Appl. Prob. 8, 737771.Google Scholar
Tweedie, R. L. (1981) Criteria for ergodicity, exponential ergodicity and strong ergodicity of Markov processes. J. Appl. Prob. 18, 122130.CrossRefGoogle Scholar
Tweedie, R. L. (1983a) Criteria for rates of convergence of Markov chains, with applications to queueing and storage theory. In Papers in Probability, Statistics and Analysis ed. Kingman, J. F. C. and Reuter., G. E. H. pp. 260276. Cambridge University Press, London.Google Scholar
Tweedie, R. L. (1983b) The existence of moments for stationary Markov chains. J. Appl. Prob. 20, 191196.CrossRefGoogle Scholar
Vere-Jones, D. (1962) Geometric ergodicity in denumerable Markov chains. Quart. J. Math. Oxford 13, 728.Google Scholar
Zum, H. (1985) The optimality equations in multichain denumerable state Markov decision processes with the average cost criterion: the bounded cost case. Statistics and Decisions 3, 143165.Google Scholar