Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-22T00:36:47.387Z Has data issue: false hasContentIssue false
  • English
  • Français

Hitting-time and occupation-time bounds implied by drift analysis with applications

Published online by Cambridge University Press:  01 July 2016

Bruce Hajek
Bruce Hajek*
Affiliation:
University of Illinois
*
∗Postal address: Coordinated Science Laboratory, University of Illinois, 1101 West Springfield Ave., Urbana, IL 61801, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

Bounds of exponential type are derived for the first-hitting time and occupation times of a real-valued random sequence which has a uniform negative drift whenever the sequence is above a fixed level. The only other assumption on the random sequence is that the increments satisfy a uniform exponential decay condition. The bounds provide a flexible technique for proving stability of processes frequently encountered in the control of queues.

Two applications are given. First, exponential-type bounds are derived for a GI/G/1 queue when the service distribution is exponential type. Secondly, geometric ergodicity is established for a certain Markov chain in which arises in the decentralized control of a multi-access, packet-switched broadcast channel.

Keywords

GEOMETRIC ERGODICITYSTOCHASTIC INEQUALITIESMARTINGALE INEQUALITIESGI/G/1 QUEUESRANDOM ACCESS
Type
Research Article
Information
Advances in Applied Probability , Volume 14 , Issue 3 , September 1982 , pp. 502 - 525
Copyright
Copyright © Applied Probability Trust 1982 

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

This work was supported by U.S. Navy contract N00014–80-C-0802.

References

Breiman, L. (1968) Probability. Addison-Wesley, Reading, MA.Google Scholar
Cheong, C. K. and Heathcote, C. R. (1965) On the rate of convergence of waiting times. J. Austral. Math. Soc. 5, 365–373.CrossRefGoogle Scholar
Doob, J. L. (1953) Stochastic Processes. Wiley, New York.Google Scholar
Hajek, B. and Van Loon, T. (1982) Decentralized dynamic control of a multi-access broadcast channel. IEEE Trans. Automatic Control 27,Google Scholar
Kamae, T., Krengel, U., and O'Brien, G. L. (1977) Stochastic inequalities on partially ordered spaces. Ann. Prob. 5, 899–912.CrossRefGoogle Scholar
Kemeny, J. G., Snell, J. L. and Knapp, A. W. (1976) Denumberable Markov Chains. Springer-Verlag, New York.Google Scholar
Kingman, J. F. C. (1970) Inequalities in the theory of queues. J. R. Statist. Soc. B32, 102–110.Google Scholar
Kingman, J. F. C. (1974) A martingale inequality in the theory of queues. Proc. Camb. Phil. Soc. 59, 359–361.Google Scholar
Lai, T. L. (1974) Martingales and boundary crossing probabilities for Markov processes. Ann. Prob. 6, 1152–1167.Google Scholar
Lamperti, J. (1960) Criteria for the recurrence or transience of stochastic processes, I. J. Math. Anal. Appl. 1, 314–330.CrossRefGoogle Scholar
Lamperti, J. (1963) Criteria for stochastic processes II: passage-time moments. J. Math. Anal. Appl. 7, 127–145.Google Scholar
Malysev, V. A. (1972) Classification of two-dimensional positive random walks and almost linear semimartingales. Soviet Math. 13, 136–139.Google Scholar
Meyer, P. A. (1966) Probability and Potentials. Blaisdell, Waltham, MA. Massachusetts.Google Scholar
Miller, H. D. (1966) Geometric ergodicity in a class of denumerable Markov chains. Z. Wahrscheinlichkeitsth. 4, 354–373.Google Scholar
Neuts, M. F. and Teugels, J. L. (1969) Exponential ergodicity of the M/G/1 queue. SIAM J. Appl. Math. 17, 921–929.Google Scholar
Nummelin, E. and Tweedie, R. L. (1978) Geometric ergodicity and R-positivity for general Markov chains. Ann. Prob. 6, 404–420.Google Scholar
Pakes, A. G. (1969) Some conditions for ergodicity and recurrence of Markov chains. Operat. Res. 17, 1058–1061.Google Scholar
Ross, S. M. (1974) Bounds on the delay distribution in GI/G/1 queues. J. Appl. Prob. 11, 417–421.Google Scholar
Teugels, J. L. (1967) Exponential decay in renewal theorems. Bull. Soc. Math. Belg. 19, 259–276.Google Scholar
Tuominen, P. and Tweedie, R. L. (1979) Exponential ergodicity in Markovian queueing and dam models. J. Appl. Prob. 16, 867–880.Google Scholar
Tweedie, R. L. (1976) Criteria for classifying general Markov chains. Adv. Appl. Prob. 8, 737–771.Google Scholar
Wald, A. (1944) On cumulative sums of random variables. Ann. Math. Statist. 15, 283–296.Google Scholar