Computable exponential convergence rates for stochastically ordered Markov processes. (English) Zbl 0863.60093

Summary: Let \(\{\Phi_t\), \(t\geq 0\}\) be a Markov process on the state space \([0,\infty)\) that is stochastically ordered in its initial state. Examples of such processes include server workloads in queues, birth-and-death processes, storage and insurance risk processes and reflected diffusions. We consider the existence of a limiting probability measure \(\pi\) and an exponential “convergence rate” \(\alpha > 0\) such that \[ \lim_{t\to \infty}e^{\alpha t}\sup_A |P_x[\Phi_t\in A]-\pi(A)|=0 \] for every initial state \(\Phi_0\equiv x\). The goal of this paper is to identify the largest exponential convergence rate \(\alpha\), or at least to find computationally reasonable bounds for such a “best” \(\alpha\). Coupling techniques are used to derive such results in terms of (i) the moment-generating function of the first passage time into state \(\{0\}\) and (ii) solutions to drift inequalities involving the generator of the process. The results give explicit bounds for total variation convergence of the process; convergence rates for \(E_x[f(\Phi_t)]\) to \(\int f(y)\pi(dy)\) for an unbounded function \(f\) are also found. We prove that frequently the bounds obtained are the best possible. Applications are given to dam models and queues where first passage time distributions are tractable, and to one-dimensional reflected diffusions where the generator is the more appropriate tool. An extension of the results to a multivariate setting and an analysis of a tandem queue are also included.


60K25 Queueing theory (aspects of probability theory)
60J25 Continuous-time Markov processes on general state spaces
Full Text: DOI


[1] ABATE, J. and WHITT, W. 1987. Transient behavior of regulated Brownian motion. I. Starting at the origin. Adv. in Appl. Probab. 19 560 598. Z. AFANAS’EVA, L. G. 1985. On periodic distribution of waiting-time process. In Stability Problems for Stochastic Models. Lecture Notes in Math. 155 1 20. Springer, New York. Z. JSTOR: · Zbl 0628.60083
[2] ASMUSSEN, S. 1987. Applied Probability and Queues. Wiley, New York. Z. · Zbl 0624.60098
[3] BACCELLI, F. and FOSS, S. 1994. Ergodicity of Jackson-ty pe queueing networks. QUESTA 17 5 72. Z. · Zbl 0826.60081
[4] BROCKWELL, P. J., RESNICK, S. I. and TWEEDIE, R. L. 1982. Storage processes with general release rule and additive inputs. Adv. in Appl. Probab. 14 392 433. Z. JSTOR: · Zbl 0482.60087
[5] COHEN, J. W. 1982. The Single Server Queue, rev. ed. North-Holland, Amsterdam. Z. · Zbl 0481.60003
[6] DAVIS, M. H. A. 1993. Markov Models and Optimization. Chapman and Hall, London. Z. · Zbl 0780.60002
[7] DOWN, D., MEy N, S. P. and TWEEDIE, R. L. 1995. Exponential and uniform ergodicity of Markov processes. Ann. Probab. 23 1671 1691. Z. · Zbl 0852.60075
[8] HEATHCOTE, C. R. 1967. Complete exponential convergence and related topics. J. Appl. Probab. 4 1 40. Z. JSTOR: · Zbl 0153.47502
[9] ICHIHARA, K. and KUNITA, H. 1974. A classification of the second order degenerate elliptic operators and its probabilistic characterization. Z. Wahrsch. Verw. Gebiete 30 235 254. Z. · Zbl 0326.60097
[10] KALASHNIKOV, V. 1994. Topics on Regenerative Processes. CRC Press, London. Z. · Zbl 0872.60063
[11] KAMAE, T., KRENGEL, U. and O’BRIEN, G. L. 1977. Stochastic inequalities on partially ordered spaces. Ann. Probab. 5 899 912. Z. · Zbl 0371.60013
[12] KELLA, O. and WHITT, W. 1992. Useful martingales for stochastic storage processes with Levy ínput. J. Appl. Probab. 29 396 403. Z. JSTOR: · Zbl 0761.60065
[13] LINDVALL, T. 1992. Lectures on the Coupling Method. Wiley, New York. Z. · Zbl 0850.60019
[14] LUND, R. B. 1994. A dam with seasonal input. J. Appl. Probab. 31 526 541. Z. JSTOR: · Zbl 0803.60091
[15] LUND, R. B. 1995. A comparison of convergence rates for three models in the theory of dams. J. Appl. Probab. To appear. Z. JSTOR: · Zbl 0876.60078
[16] LUND, R. B. and TWEEDIE, R. L. 1995. Geometric convergence rates for stochastically ordered Markov chains. Math. Oper. Res. To appear. Z. JSTOR: · Zbl 0847.60053
[17] MEy N, S. P. and DOWN, D. 1994. Stability of generalized Jackson networks. Ann. Appl. Probab. 4 124 148. Z. · Zbl 0807.68015
[18] MEy N, S. P. and TWEEDIE, R. L. 1993a. Stability of Markovian processes. II. Continuous-time processes and sampled chains. Adv. in Appl. Probab. 25 487 517. Z. JSTOR: · Zbl 0781.60052
[19] MEy N, S. P. and TWEEDIE, R. L. 1993b. Stability of Markovian processes. III: Foster Ly apunov criteria for continuous-time processes. Adv. in Appl. Probab. 25 518 548. Z. JSTOR: · Zbl 0781.60053
[20] MEy N, S. P. and TWEEDIE, R. L. 1993c. Markov Chains and Stochastic Stability. Springer, London. Z.
[21] MORSE, P. M. 1958. Queues, Inventories and Maintenance. Wiley, New York. Z.
[22] PRABHU, N. U. 1980. Stochastic Storage Models. Springer, New York. Z. · Zbl 0453.60094
[23] ROSENKRANTZ, W. A. 1983. Calculation of the Laplace transform of the length of the busy period for the M G 1 queue via martingales. Ann. Probab. 11 817 818. · Zbl 0513.60093
[24] SHANTHIKUMAR, J. G. and YAO, D. D. 1989. Stochastic monotonicity in general queueing networks. J. Appl. Probab. 26 413 417. Z. JSTOR: · Zbl 0686.60099
[25] STOy AN, D. 1983. Comparison Methods for Queues and Other Stochastic Models. Wiley, New York. Z. · Zbl 0536.60085
[26] THORISSON, H. 1983. The coupling of regenerative processes. Adv. in Appl. Probab. 15 531 561. Z. JSTOR: · Zbl 0512.60080
[27] TUOMINEN, P. and TWEEDIE, R. L. 1979. Exponential ergodicity in Markovian queueing and dam models. J. Appl. Probab. 16 867 880. Z. JSTOR: · Zbl 0422.60074
[28] VAN DOORN, E. A. 1981. Stochastic Monotonicity and Queueing Applications of Birth Death Processes. Lecture Notes in Statist. 4. Springer, New York. Z. · Zbl 0454.60069
[29] VAN DOORN, E. A. 1985. Conditions for the exponential ergodicity and bounds for the decay parameter of a birth death process. J. Appl. Probab. 17 514 530. Z. JSTOR: · Zbl 0597.60080
[30] VERAVERBEKE, N. and TEUGELS, J. L. 1975. The exponential rate of convergence of the distribution of a maximum of a random walk. J. Appl. Probab. 12 279 288. Z. JSTOR: · Zbl 0307.60061
[31] VERAVERBEKE, N. and TEUGELS, J. L. 1976. The exponential rate of convergence of the distribution of a maximum of a random walk. II. J. Appl. Probab. 13 733 740. Z. JSTOR: · Zbl 0353.60072
[32] ZEIFMAN, A. I. 1991. Some estimates of the rate of convergence for birth and death processes. J. Appl. Probab. 28 268 277. JSTOR: · Zbl 0738.60088
[33] ATHENS, GEORGIA 30602-1952 1308 WEST MAIN STREET E-mail: lund@stat.uga.edu URBANA, ILLINOIS 61801 E-mail: mey n@Fourier.csl.uiuc.edu R. L. TWEEDIE DEPARTMENT OF STATISTICS COLORADO STATE UNIVERSITY FORT COLLINS, COLORADO 80523 E-mail: tweedie@stat.colostate.edu
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.