Book contents
- Frontmatter
- Contents
- The asymptotic speed and shape of a particle system
- On doubly stochastic population processes
- On limit theorems for occupation times
- The Martin boundary of two dimensional Ornstein-Uhlenbeck processes
- Green's and Dirichlet spaces for a symmetric Markov transition function
- On a theorem of Kabanov, Liptser and Širjaev
- Oxford Commemoration Ball
- Invariant measures and the q-matrix
- The appearance of a multivariate exponential distribution in sojourn times for birth-death and diffusion processes
- Three unsolved problems in discrete Markov theory
- The electrostatic capacity of an ellipsoid
- Stationary one-dimensional Markov random fields with a continuous state space
- A uniform central limit theorem for partial-sum processes indexed by sets
- Multidimensional randomness
- Some properties of a test for multimodality based on kernel density estimates
- Criteria for rates of convergence of Markov chains, with application to queueing and storage theory
- Competition and bottle-necks
- Contributors
Criteria for rates of convergence of Markov chains, with application to queueing and storage theory
Published online by Cambridge University Press: 05 April 2013
- Frontmatter
- Contents
- The asymptotic speed and shape of a particle system
- On doubly stochastic population processes
- On limit theorems for occupation times
- The Martin boundary of two dimensional Ornstein-Uhlenbeck processes
- Green's and Dirichlet spaces for a symmetric Markov transition function
- On a theorem of Kabanov, Liptser and Širjaev
- Oxford Commemoration Ball
- Invariant measures and the q-matrix
- The appearance of a multivariate exponential distribution in sojourn times for birth-death and diffusion processes
- Three unsolved problems in discrete Markov theory
- The electrostatic capacity of an ellipsoid
- Stationary one-dimensional Markov random fields with a continuous state space
- A uniform central limit theorem for partial-sum processes indexed by sets
- Multidimensional randomness
- Some properties of a test for multimodality based on kernel density estimates
- Criteria for rates of convergence of Markov chains, with application to queueing and storage theory
- Competition and bottle-necks
- Contributors
Summary
ABSTRACT
This paper first presents a review of the connections between various rate of convergence results for Markov chains (including normal Harris ergodicity, geometric ergodicity and sub-geometric rates for a variety of rate functions ψ), and finiteness of appropriate moments of hitting times on small sets. We then present a series of criteria, analogous to Foster's criterion for ergodicity, which imply the finiteness of these moments and hence the rate of convergence of the Markov chain.
These results are applied to random walk on [0, ∞), and we deduce for example that this chain converges at rate ψ(n) = nα (log n)β if the increment variable has finite moment of order nα+1 (log n)β. Similar results hold for more general storage models.
Introduction
It is not always possible to pinpoint the beginnings of a major research area, and yet there can be little doubt that for the bulk of the vast quantity of mathematics known as queueing theory one can trace both the types of problems and the methods of solution to the single fundamental paper of David Kendall [8]. In that paper he introduced the idea of analysing queueing systems using embedded Markov chains, and the interplay between Markov chain theory and queueing theory has since been of vital importance in the development of both areas.
One of the most immediate, simplest and most elegant products of this interplay was the discovery by F.G. Foster (then a student of Kendall) of a criterion for positive recurrence of Markov chains, ensuring that these chains would have stationary distributions.
- Type
- Chapter
- Information
- Probability, Statistics and Analysis , pp. 260 - 276Publisher: Cambridge University PressPrint publication year: 1983
- 57
- Cited by