Advertisement

Quasi-Stationary Distributions of Markov Chains Arising from Queueing Processes: A Survey

  • Masaaki Kijima
  • Naoki Makimoto
Chapter
Part of the International Series in Operations Research & Management Science book series (ISOR, volume 19)

Abstract

There are a variety of random processes that evanesce either by dying out or by exploding, yet the time it takes for this to occur is very long, and over any reasonable time, these processes reach some apparent equilibrium. For example, in some chemical processes, there are a number of reactions in which one or more species can become exhausted, yet these reactions appear to settle down quickly to a stable equilibrium (see, e.g., Parsons and Pollett [49] and Pollett [52]). The quasi-stationary distribution (QSD) is a stationary distribution conditioned to stay in some states of interest and has proved to be a potent tool in modeling and analyzing such phenomena. The idea can be traced back to Yaglom [69] (see Pollett and Stewart [53] for the history and references applied to a variety of contents).

Keywords

Markov Chain Decay Parameter Quasistationary Distribution Substochastic Matrix Transient Markov Chain 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. [1]
    Abate, J., and Whitt, W. Spectral theory for skip-free Markov chains. Prob. Eng. Inform. Sci. 3, 77–88, 1989.zbMATHCrossRefGoogle Scholar
  2. [2]
    Bean, N. G., Bright, L., Latouche, G., Pearce, C. E. M., Pollett, P. K., and Taylor, P. G. The quasistationary behaviour of quasi-birth-and-death processes. Ann. Appl. Prob., to appear.Google Scholar
  3. [3]
    Cavender, J. A. Quasi-stationary distributions of birth-and-death processes. Adv. Appl. Prob. 10, 570–586, 1978.MathSciNetzbMATHCrossRefGoogle Scholar
  4. [4]
    Chihara, T. S. An Introduction to Orthogonal Polynomials. Gordon & Breach, New York, 1978.zbMATHGoogle Scholar
  5. [5]
    Chung, K. L. Markov Chains with Stationary Transition Probabilities. Springer-Verlag, Berlin, 1960.zbMATHCrossRefGoogle Scholar
  6. [6]
    Daley, D. J. Quasi-stationary behavior of a left-continuous random walks. Ann. Math. Stat. 40, 532–539, 1969.MathSciNetzbMATHCrossRefGoogle Scholar
  7. [7]
    Darroch, J. N., and Seneta, E. On quasi-stationary distributions in absorbing discrete-time finite Markov chains. J. Appl. Prob. 2, 88–100, 1965.MathSciNetzbMATHCrossRefGoogle Scholar
  8. [8]
    Darroch, J. N., and Seneta, E. On quasi-stationary distributions in absorbing continuous-time finite Markov chains. J. Appl. Prob. 4, 192–196, 1967.MathSciNetzbMATHCrossRefGoogle Scholar
  9. [9]
    Feller, W. The birth and death processes as diffusion processes. J. Math. Pures Appl. 38, 301–345, 1959.MathSciNetzbMATHGoogle Scholar
  10. [10]
    Ferrari, P. A., Martinez, S., and Picco, P. Existence of non-trivial quasi-stationary distributions in the birth-death chain. Adv. Appl. Prob. 24, 795–813, 1992.MathSciNetzbMATHCrossRefGoogle Scholar
  11. [11]
    Ferrari, P. A., Kesten, H., Martinez, S., and Picco, P. Existence of quasi-stationary distributions: a renewal dynamic approach. Ann. Prob. 23, 501–521, 1995.MathSciNetzbMATHCrossRefGoogle Scholar
  12. [12]
    Gibson, D., and Seneta, E. Augmented truncations of infinite stochastic matrices. J. Appl. Prob. 24, 600–608, 1987.MathSciNetzbMATHCrossRefGoogle Scholar
  13. [13]
    Gibson, D., and Seneta, E. Monotone infinite stochastic matrices and their augmented truncations. Stoch. Proc. Appl. 24, 287–292, 1987.MathSciNetzbMATHCrossRefGoogle Scholar
  14. [14]
    Iglehart, D. L. Random walks with negative drift conditioned to stay positive. J. Appl. Prob. 11, 742–751, 1974.MathSciNetzbMATHCrossRefGoogle Scholar
  15. [15]
    Iglehart, D. L. Functional central limit theorems for random walks conditioned to stay positive. Ann. Prob. 2, 608–619, 1974.MathSciNetzbMATHCrossRefGoogle Scholar
  16. [16]
    Kao, P. Limiting diffusion for random walks with drift conditioned to stay positive. J. Appl. Prob. 15, 280–291, 1978.MathSciNetzbMATHCrossRefGoogle Scholar
  17. [17]
    Karlin, S., and McGregor, J. L. The differential equations of birth-and-death processes, and the Stieltjes moment problem. Trans. Am. Math. Soc. 85, 489–546, 1957.MathSciNetzbMATHCrossRefGoogle Scholar
  18. [18]
    Karlin, S., and McGregor, J. L. The classification of birth and death processes. Trans. Am. Math. Soc. 86, 366–400, 1957.MathSciNetzbMATHCrossRefGoogle Scholar
  19. [19]
    Karlin, S., and McGregor, J. L. Many server queueing processes with Poisson input and exponential service times. Pacific J. Math. 8, 87–118, 1958.MathSciNetzbMATHGoogle Scholar
  20. [20]
    Keilson, J. Markov Chain ModelsRarity and Exponentiality. Springer, New York, 1979.Google Scholar
  21. [21]
    Keilson, J., and Kester, A. Monotone matrices and monotone Markov processes. Stoch. Proc. Appl. 5, 231–241, 1977.MathSciNetzbMATHCrossRefGoogle Scholar
  22. [22]
    Keilson, J., and Ramaswamy, R. Convergence of quasi-stationary distributions in birth-death processes. Stoch. Proc. Appl. 18, 301–312, 1984.MathSciNetzbMATHCrossRefGoogle Scholar
  23. [23]
    Keilson, J., and Ramaswamy, R. The bivariate maximum process and quasista-tionary structure of birth-death processes. Stoch. Proc. Appl. 22, 27–36, 1986.MathSciNetzbMATHCrossRefGoogle Scholar
  24. [24]
    Kennedy D. P. Limiting diffusions for the conditioned M/G/1 queue. J. Appl. Prob. 11, 355–362, 1974.zbMATHCrossRefGoogle Scholar
  25. [25]
    Kesten, H. A ratio limit theorem for (sub) Markov chains on {1,2, ⋯} with bounded jumps. Adv. Appl. Prob. 27, 652–691, 1995.MathSciNetzbMATHCrossRefGoogle Scholar
  26. [26]
    Kijima, M. On the largest negative eigenvalue of the infinitesimal generator associated with M/M/n/n queues. Oper. Res. Lett. 9, 59–64, 1990.MathSciNetzbMATHCrossRefGoogle Scholar
  27. [27]
    Kijima, M. On the existence of quasi-stationary distributions in denumerable R-transient Markov chains. J. Appl. Prob. 29, 21–36, 1992.MathSciNetzbMATHCrossRefGoogle Scholar
  28. [28]
    Kijima, M. Evaluation of the decay parameter for some specialized birth-death processes. J. Appl. Prob. 29, 781–791, 1992.MathSciNetzbMATHCrossRefGoogle Scholar
  29. [29]
    Kijima, M. Quasi-stationary distributions of single server phase-type queues. Math. Oper. Res. 19, 423–437, 1993.MathSciNetCrossRefGoogle Scholar
  30. [30]
    Kijima, M. Quasi-limiting distributions of Markov chains that are skip-free to the left in continuous time. J. Appl. Prob. 30, 509–517, 1993.MathSciNetzbMATHCrossRefGoogle Scholar
  31. [31]
    Kijima, M. Bounds for the quasi-stationary distribution of some specialized Markov chains. Math. Comp. Modelling 22, 141–147, 1995.MathSciNetzbMATHCrossRefGoogle Scholar
  32. [32]
    Kijima, M. Markov Chains for Stochastic Modeling. Chapman & Hall, London, 1996.Google Scholar
  33. [33]
    Kijima, M., and Makimoto, N. Computation of the quasi-stationary distributions in M(n)/GI/1/K and GI/M(n)/1/K queues. Queueing Syst. 11, 255–272, 1992.MathSciNetzbMATHCrossRefGoogle Scholar
  34. [34]
    Kijima, M., and Makimoto, N. Computation of quasi-stationary distributions in Markovian queues. Proc. 16th Int. Conf. Computers and Industrial Eng. 1994, pp. 849–852.Google Scholar
  35. [35]
    Kijima, M., Nair, M. G., Pollett, P. K., and van Doom, E. A. Limiting conditional distributions for birth-death processes. Adv. Appl. Prob., to appear.Google Scholar
  36. [36]
    Kijima, M., and Seneta, E. Some results for quasi-stationary distributions of birth-death processes. J. Appl. Prob. 28, 503–511, 1991.MathSciNetzbMATHCrossRefGoogle Scholar
  37. [37]
    Kijima, M., and van Doorn, E. A. Weighted sums of orthogonal polynomials with positive zeros. J. Comp. Appl. Math. 65, 195–206, 1995.zbMATHCrossRefGoogle Scholar
  38. [38]
    Kingman, J. F. C. The exponential decay of Markov transition probabilities. Proc. London Math. Soc. 13, 337–358, 1963.MathSciNetzbMATHCrossRefGoogle Scholar
  39. [39]
    Kingman, J. F. C. A convexity property of positive matrices. Q. J. Math. Oxford 12, 283–284, 1963.MathSciNetCrossRefGoogle Scholar
  40. [40]
    Kyprianou, E. K. On the quasi-stationary distribution of the virtual waiting time in queues with Poisson arrivals. J. Appl. Prob. 8, 495–507, 1971.MathSciNetCrossRefGoogle Scholar
  41. [41]
    Kyprianou, E. K. On the quasi-stationary distributions of the GI/M/1 queue. J. Appl. Prob, 9, 117–128, 1972.MathSciNetzbMATHCrossRefGoogle Scholar
  42. [42]
    Kyprianou, E. K. The quasi-stationary distributions of queues in heavy traffic. J. Appl. Prob. 9, 821–831, 1972.MathSciNetzbMATHCrossRefGoogle Scholar
  43. [43]
    Ledermann, W., and Reuter, G. E. H. Spectral theory for the differential equations of simple birth and death processes. Phil. Trans R. Soc. London A, 246, 321–368, 1954.MathSciNetzbMATHCrossRefGoogle Scholar
  44. [44]
    Lucantoni, D. M., Meier-Hellstein, K. S., and Neuts, M. F. A single-server queue with server vacations and a class of non-renewal arrival processes. Adv. Appl. Prob. 22, 676–705, 1990.zbMATHCrossRefGoogle Scholar
  45. [45]
    Makimoto, N. Quasi-stationary distributions in a PH/PH/c queue. Stock. Models 9, 195–212, 1993.MathSciNetzbMATHCrossRefGoogle Scholar
  46. [46]
    Nair, M. G., and Pollett, P. K. On the relationship between μ-invariant measures and quasi-stationary distributions for continuous-time Markov chains. Adv. Appl. Prob. 25, 82–102, 1993.MathSciNetzbMATHCrossRefGoogle Scholar
  47. [47]
    Neuts, M. F. Matrix-Geometric Solutions in Stochastic ModelsAn Algorithmic Approach. Johns Hopkins University Press, Baltimore, 1981.Google Scholar
  48. [48]
    Neuts, M. F. Structured Stochastic Matrices of M/G/1 Type and Their Applications. Marcel Dekker, New York, 1989.zbMATHGoogle Scholar
  49. [49]
    Parsons, R. W., and Pollett, P. K. Quasistationary distributions for autocatalytic reactions. J. Stat. Phys. 46, 249–254, 1987.CrossRefGoogle Scholar
  50. [50]
    Pollak, M., and Siegmund, D. Convergence of quasi-stationary to stationary distributions for stochastically monotone Markov processes. J. Appl. Prob. 23, 215–220, 1986.MathSciNetzbMATHCrossRefGoogle Scholar
  51. [51]
    Pollett, P. K. On the equivalence of μ-invariant measures for the minimal process and its q-matrix. Stoch. Proc. Appl. 22, 203–221, 1986.MathSciNetzbMATHCrossRefGoogle Scholar
  52. [52]
    Pollett, P. K. On the problem of evaluating quasistationary distributions for open reaction schemes. J. Stat. Phys. 53, 1207–1215, 1988.MathSciNetzbMATHCrossRefGoogle Scholar
  53. [53]
    Pollett, P. K., and Stewart, D. E. An efficient procedure for computing quasi-stationary distributions of Markov chains with sparse transition structure. Adv. Appl. Prob. 26, 68–79, 1994.MathSciNetzbMATHCrossRefGoogle Scholar
  54. [54]
    Roberts, G. O. A comparison theorem for conditioned Markov processes. J. Appl. Prob. 28, 74–83, 1991.zbMATHCrossRefGoogle Scholar
  55. [55]
    Schweitzer, P. J. An Iterative Aggregation-Disaggregation Algorithm for Computing the Spectral Radius of a Non-negative Irreducible Matrix. Working paper QM-8433, Graduate School of Management, University of Rochester, Rochester, NY, 1984.Google Scholar
  56. [56]
    Seneta, E. Non-negative Matrices and Markov Chains, 2nd ed. Springer, New York, 1981.zbMATHGoogle Scholar
  57. [57]
    Seneta, E., and Vere-Jones, D. On quasi-stationary distributions in discrete-time Markov chains with a denumerable infinity of states. J. Appl. Prob. 3, 403–434, 1966.MathSciNetzbMATHCrossRefGoogle Scholar
  58. [58]
    Szegö, S. Orthogonal Polynomials. AMS Colloq. Publ., vol. 23. AMS, New York, 1959.zbMATHGoogle Scholar
  59. [59]
    van Doorn, E. A. Stochastic Monotonicity and Queueing Applications of Birth-death Processes. Springer, Berlin, 1981.CrossRefGoogle Scholar
  60. [60]
    van Doorn, E. A. Conditions for exponential ergodicity and bounds for the decay parameter of a birth-death process. Adv. Appl. Prob. 17, 514–530, 1985.zbMATHCrossRefGoogle Scholar
  61. [61]
    van Doom, E. A. Representations and bounds for zeros of orthogonal polynomials and eigenvalues of sign-symmetric tri-diagonal matrices. J. Approx. Theory 51, 254–266, 1987.MathSciNetCrossRefGoogle Scholar
  62. [62]
    van Doorn, E. A. Quasi-stationary distributions and convergence to quasista-tionarity of birth—death processes. Adv. Appl. Prob. 23, 683–700, 1991.zbMATHCrossRefGoogle Scholar
  63. [63]
    van Doorn, E. A., and Schrijner, P. Ratio limits and limiting conditional distributions for discrete-tome birth-death processes. J. Math. Anal. Appl. 190, 263–284, 1995.MathSciNetzbMATHCrossRefGoogle Scholar
  64. [64]
    van Doorn, E. A., and Schrijner, P. Geometric ergodicity and quasi-stationarity in discrete-time birth-death processes. J. Austral. Math Soc. B 37, 1–24, 1995.CrossRefGoogle Scholar
  65. [65]
    Vere-Jones, D. Geometric ergodicity in denumerable Markov chains. Q. J. Math. Oxford 2, 13, 7–28, 1962.MathSciNetzbMATHCrossRefGoogle Scholar
  66. [66]
    Vere-Jones, D. Ergodic properties of non-negative matrices-I. Pacific J. Math. 22, 361–386, 1967.MathSciNetzbMATHGoogle Scholar
  67. [67]
    Vere-Jones, D. Some limit theorems for evanescent processes. Austral. J. Stat. 11, 67–78, 1969.MathSciNetzbMATHCrossRefGoogle Scholar
  68. [68]
    Watkins, D. S. Fundamentals of Matrix Computations. John Wiley & Sons, New York, 1991.zbMATHGoogle Scholar
  69. [69]
    Yaglom, A. M. Certain limit theorems of the theory of branching processes. Dokl. Acad. Nauk SSSR 56, 795–798, 1947.MathSciNetzbMATHGoogle Scholar
  70. [70]
    Zeifman, A. I. Some estimates of the rate of convergence for birth and death processes. J. Appl. Prob. 28, 268–277, 1991.MathSciNetzbMATHCrossRefGoogle Scholar
  71. [71]
    Ziedins, L. Quasi-stationary distributions and one-dimensional circuit-switched networks. J. Appl. Prob. 24, 965–977, 1987.MathSciNetzbMATHCrossRefGoogle Scholar

Copyright information

© Springer Science+Business Media New York 1999

Authors and Affiliations

  • Masaaki Kijima
  • Naoki Makimoto

There are no affiliations available

Personalised recommendations