Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-20T12:22:49.219Z Has data issue: false hasContentIssue false
  • English
  • Français

Poisson's equation for the recurrent M/G/1 queue

Part of: Stochastic processes Limit theorems Markov processes

Published online by Cambridge University Press:  01 July 2016

Peter W. Glynn
Peter W. Glynn*
Affiliation:
Stanford University
*
* Postal address: Department of Operations Research, Stanford University, Stanford, CA 94305–4022, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper shows how to calculate solutions to Poisson's equation for the waiting time sequence of the recurrent M/G/l queue. The solutions are used to construct martingales that permit us to study additive functionals associated with the waiting time sequence. These martingales provide asymptotic expressions, for the mean of additive functionals, that reflect dependence on the initial state of the process. In addition, we show how to explicitly calculate the scaling constants that appear in the central limit theorems for additive functionals of the waiting time sequence.

Keywords

ADDITIVE FUNCTIONALMARTINGALESCENTRAL LIMIT THEOREMS

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 60G42: Martingales with discrete parameter 60F05: Central limit and other weak theorems
Type
Research Article
Information
Advances in Applied Probability , Volume 26 , Issue 4 , December 1994 , pp. 1044 - 1062
Copyright
Copyright © Applied Probability Trust 1994 

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

Research supported by the U.S. Army Research Office under Contract DAAL-03-88-K-0063, and a grant of the Natural Sciences of Engineering Research Council of Canada.

References

Asmussen, S. and Bladt, M. (1993) Poisson's equation for queues driven by a Markovian marked point process. Technical Report, Aalborg University, Denmark.Google Scholar
Athreya, K. B. and Ney, P. (1978) A new approach to the limit theory of recurrent Markov chains. Trans. Amer. Math. Soc. 245, 493–501.Google Scholar
Billingsley, P. (1968) Convergence of Probability Measures. Wiley, New York.Google Scholar
Billingsley, P. (1979) Probability and Measure. Wiley, New York.Google Scholar
Blomqvist, N. (1967) The covariance function of the M/G1 1 queueing system. Skand. Aktuarietidskr. 50. 157–164.Google Scholar
Breiman, L. (1968) Probability. Addison-Wesley, Reading, MA.Google Scholar
Daley, D. J. (1968) The serial correlation coefficients of waiting times in a stationary single server queue. J. Austral. Math. Soc. 8, 683–699.Google Scholar
Ethier, S. N. and Kurtz, T. G. (1986) Markov Processes: Characterization and Convergence. Wiley, New York.Google Scholar
Feller, W. (1971) An Introduction to Probability Theory and its Applications, Vol. II. Wiley, New York.Google Scholar
Heathcote, C. R. and Winer, P. (1969) An approximation for the moments of waiting times. Operat. Res. 17, 175–196.Google Scholar
Heyman, D. P. and Sobel, M. (1982) Stochastic Models in Operations Research, McGraw-Hill, New York.Google Scholar
Karlin, S. and Taylor, H. M. (1981) A Second Course in Stochastic Processes. Academic Press, New York.Google Scholar
Kiefer, J. and Wolfowitz, J. (1956) On the characteristics of the general queueing process with applications to random walks. Ann. Math. Statist. 27, 147–161.Google Scholar
Maigret, N. (1978) Théorème de limite centrale functionnel pour une chaîne de Markov récurrente au sens de Harris et positive. Ann. Inst. H. Poincaré B 14, 425–440.Google Scholar
Neveu, J. (1972) Potentiel Markovien récurrente des chaînes de Harris. Ann. Inst. Fourier, Grenoble 22, 7–130.Google Scholar
Niemi, S. and Nummelin, E. (1982) Central limit theorems for Markov random walks. Commentationes Physico-Mathematicae 54, Societas Scientiarum Fennica, Helsinki.Google Scholar
Nummelin, E. (1985) On the Poisson equation in the potential theory of a single kernel. Technical Report. Department of Mathematics, University of Helsinki, Iceland.Google Scholar
Orey, S. (1971) Lecture Notes on Limit Theorems for Markov Chain Transition Probabilities. Van Nostrand Reinhold, London.Google Scholar
Pagurek, G. and Woodside, C. M. (1979) The sum of serial correlations of waiting and system times in GI/G/1 queues. Operat. Res. 27, 755–766.Google Scholar
Revuz, D. (1984) Markov Chains. North-Holland, Amsterdam.Google Scholar
Tweedie, R. L. (1983) The existence of moments for stationary Markov chains J. Appl. Prob. 20, 191–196.Google Scholar