Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T03:24:10.513Z Has data issue: false hasContentIssue false
  • English
  • Français

Transient behavior of regulated Brownian motion, I: Starting at the origin

Published online by Cambridge University Press:  01 July 2016

Joseph Abate  and
Ward Whitt
Joseph Abate*
Affiliation:
AT & T Bell Laboratories
Ward Whitt*
Affiliation:
AT & T Bell Laboratories
*
∗Postal address: AT & T Bell Laboratories, LC2W-E06, 184 Liberty Corner Road, Warren, NJ 07060, USA.
∗∗ Postal address: AT & T Bell Laboratories, MH2C-178, Murray Hill, NJ 07974, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

A natural model for stochastic flow systems is regulated or reflecting Brownian motion (RBM), which is Brownian motion on the positive real line with constant negative drift and constant diffusion coefficient, modified by an impenetrable reflecting barrier at the origin. As a basis for understanding how stochastic flow systems approach steady state, this paper provides relatively simple descriptions of the moments of RBM as functions of time. In Part I attention is restricted to the case in which RBM starts at the origin; then the moment functions are increasing. After normalization by the steady-state limits, these moment c.d.f.&s (cumulative distribution functions) coincide with gamma mixtures of inverse Gaussian c.d.f.&s. The first moment c.d.f. thus coincides with the first-passage time to the origin starting in steady state with the exponential stationary distribution. From this probabilistic characterization, it follows that the kth-moment c.d.f is the k-fold convolution of the first-moment c.d.f. As a consequence, it is easy to see that the (k + 1)th moment approaches its steady-state limit more slowly than the kth moment. It is also easy to derive the asymptotic behavior as t →∞. The first two moment c.d.f.&s have completely monotone densities, supporting approximation by hyperexponential (H2) c.d.f.&s (mixtures of two exponentials). The H2 approximations provide easily comprehensible descriptions of the first two moment c.d.f.&s suitable for practical purposes. The two exponential components of the H2 approximation yield simple exponential approximations in different regimes. On the other hand, numerical comparisons show that the limit related to the relaxation time does not predict the approach to steady state especially well in regions of primary interest. In Part II (Abate and Whitt (1987a)), moments of RBM with non-zero initial conditions are treated by representing them as the difference of two increasing functions, one of which is the moment function starting at the origin studied here.

Keywords

APPROACH TO STEADY STATERELAXATION TIMESDIFFUSION PROCESSESQUEUESSTOCHASTIC FLOW SYSTEMSFIRST-PASSAGE TIMESINVERSE GAUSSIAN DISTRIBUTIONCOMPLETE MONOTONICITY
Type
Research Article
Information
Advances in Applied Probability , Volume 19 , Issue 3 , September 1987 , pp. 560 - 598
Copyright
Copyright © Applied Probability Trust 1987 

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.)

References

Abate, J. and Whitt, W. (1987a) Transient behavior of regulated Brownian motion, II: non-zero initial conditions. Adv. Appl. Prob. 19, 599–631.Google Scholar
Abate, J. and Whitt, W. (1987b) Transient behavior of the M/M/1 queue: Starting at the origin. Queueing Systems 2.Google Scholar
Abate, J. and Whitt, W. (1987C) Approximate transient behavior of the GI/G/1 queue.Google Scholar
Abate, J. and Whitt, W. (1988) Transient behavior of the M/M/1 queue via Laplace transforms. Adv. Appl. Prob. 20 (1).Google Scholar
Abramowitz, M. and Stegun, I. A. (1972) Handbook of Mathematical Functions. Dover, New York.Google Scholar
Baker, G. A. Jr. (1975) Essentials of Padé Approximants. Academic Press, New York.Google Scholar
Blanc, J. P. C. (1985) The relaxation time of two queueing systems in series. Commun. Statist.-Stochastic Models 1, 1–16.Google Scholar
Borovkov, A. A. (1965) Some limit theorems in the theory of mass service, II. Theory. Prob. Appl. 10, 375–400.CrossRefGoogle Scholar
Borovkov, A. A. (1984) Asymptotic Methods in Queueing Theory. Wiley, New York.Google Scholar
Chandrasekhar, S. (1943) Stochastic problems in physics and astronomy. Rev. Mod. Phys. 15, 1–89 (in Selected Papers on Noise and Stochastic Processes, ed. Wax, N., Dover, New York, 1954, pp. 3-91).Google Scholar
Coffman, E. G. and Reiman, M. I. (1984) Diffusion approximations for computer/communications systems. In Mathematical Computer Performance and Reliability, ed. Iazeolla, G., Courtois, P. J. and Hordijk, A., Elsevier, Amsterdam, 33–53.Google Scholar
Cohen, J. W. (1982) The Single Server Queue, 2nd edn. North-Holland, Amsterdam.Google Scholar
Cox, D. R. (1962) Renewal Theory. Methuen, London.Google Scholar
Cox, D. R. and Miller, H. D. (1965) The Theory of Stochastic Processes Wiley, New York.Google Scholar
Davies, B. and Martin, B. (1979) Numerical inversion of the Laplace transform. J. Comp. Phys. 33, 1–32.Google Scholar
Davis, D. (1960) The build-up time of waiting lines. Nav. Res. Log. Qtrly. 2, 185–193.Google Scholar
Doetsch, G. (1974) Introduction to the Theory and Application of the Laplace Transformation Springer-Verlag, New York.Google Scholar
Doney, R. A. (1984) Letter to the Editor. J. Appl. Prob. 21, 673–674.Google Scholar
Dubner, H. and Abate, J. (1968) Numerical inversion of Laplace transforms by relating them to the finite Fourier cosine transform. J. ACM 15, 115–123.CrossRefGoogle Scholar
Feller, W. (1968) An Introduction to Probability Theory and its Applications, Vol. II, 3rd edn. Wiley, New York.Google Scholar
Feller, W. (1971) An Introduction to Probability Theory and Its Applications, Vol. II, 2nd edn. Wiley, New York.Google Scholar
Flores, C. (1985) Diffusion approximations for computer communications networks. In Computer Communications, Proc. Symp. Appl. Math. 31, American Math. Society, Providence, 83–124.Google Scholar
Gaver, D. P. Jr. (1966) Observing stochastic processes and approximate transform inversion. Operat. Res. 14, 444–459.Google Scholar
Gaver, D. P. Jr. (1968) Diffusion approximations and models for certain congestion problems. J. Appl. Prob. 5, 607–623.Google Scholar
Harrison, J. M. (1985) Brownian Motion and Stochastic Flow Systems Wiley, New York.Google Scholar
Iglehart, D. L. and Whitt, W. (1970a) Multiple channel queues in heavy traffic, I. Adv. Appl. Prob. 2, 150–177.CrossRefGoogle Scholar
Iglehart, D. L. and Whitt, W. (1970b) Multiple channel queues in heavy traffic II: sequences, networks and batches. Adv. Appl. Prob. 2, 355–369.Google Scholar
Johnson, N. L. and Kotz, S. (1970). Distributions In Statistics, Continuous Univariate Distributions I, Wiley, New York.Google Scholar
Karlin, S. and Taylor, H. M. (1975) A First Course in Stochastic Processes, 2nd edn. Academic Press, New York.Google Scholar
Keilson, J. (1979) Markov Chain Models–Rarity and Exponentiality Springer-Verlag, New York.Google Scholar
Keilson, J. and Kester, A. (1977) Monotone matrices and monotone Markov processes. Stoch. Proc. Appl. 5, 231–241.Google Scholar
Kelly, F. P. (1979) Reversibility and Stochastic Networks Wiley, New York.Google Scholar
Kleinrock, L. (1976) Queueing Systems, Vol. 2: Computer Applications Wiley, New York.Google Scholar
Lee, I. (1985) Stationary Markovian Queueing Systems: An Approximation for the Transient Expected Queue Length, M. S. dissertation, Department of Electrical Engineering and Computer Science, MIT, Cambridge.Google Scholar
Lee, I. and Roth, E. (1986) Stationary Markovian queueing systems: an approximation for the transient expected queue length.Google Scholar
Luke, Y. L. (1969) The Special Functions and Their Approximants Academic Press, New York.Google Scholar
Magnus, W., Oberhettinger, F. and Soni, R. P. (1966) Formulas and Theorems for the Special Functions of Mathematical Physics Springer-Verlag, New York.CrossRefGoogle Scholar
Mitchell, J. C. (1985) Lost-sales inventory systems with a service objective, I: stationary demand, linear procurement costs and fixed lead times.Google Scholar
Newell, G. F. (1982) Applications of Queueing Theory, 2nd edn Chapman and Hall, London.Google Scholar
Oberhettinger, F. and Badii, L. (1973) Tables of Laplace Transforms Springer-Verlag, New York.CrossRefGoogle Scholar
Odoni, A. R. and Roth, E. (1983) An empirical investigation of the transient behavior of stationary queueing systems. Operat. Res. 31, 432–455.Google Scholar
Phatarfod, R. M., Speed, T. P. and Walker, A. M. (1971) A note on random walks. J. Appl. Prob. 8, 198–201.Google Scholar
Piessens, R. and Huysmans, R. (1984) Algorithm 619. Automatic numerical inversion of the Laplace transform. ACM Trans. Math. Softw. 10, 348–353.Google Scholar
Roth, E. (1981) An Investigation of the Transient Behavior of Stationary Queueing Systems, Ph.D. Dissertation, M.I.T., Cambridge.Google Scholar
Stehfest, H. (1970) Algorithm 368. Numerical inversion of Laplace transforms. Comm. ACM 13, 47–49 (erratum 13, 624).Google Scholar
Stone, C. (1963) Limit theorems for random walks, birth and death processes, and diffusion processes. Illinois J. Math. 7, 638–660.Google Scholar
Stoyan, D. (1983) In Comparison Methods for Queues and Other Stochastic Models, ed. Daley, D. J.. Wiley, Chichester.Google Scholar
Sumita, U. (1984) On conditional passage time structure of birth-death processes. J. Appl. Prob. 21, 10–21.CrossRefGoogle Scholar
Takács, L. (1967) Combinatorial Methods in the Theory of Stochastic Processes Wiley, New York.Google Scholar
Van Doorn, E. (1980) Stochastic Monotonicity and Queueing Applications of Birth-Death Processes. Lecture Notes in Statistics 4, Springer-Verlag, New York.Google Scholar
Veillon, F. (1974) Algorithm 486. Numerical inversion of Laplace transform. Comm. ACM 17, 587–589.Google Scholar
Whitt, W. (1982) Approximating a point process by a renewal process, I: two basic methods. Operat. Res. 30, 125–147.Google Scholar
Whitt, W. (1984) On approximations for queues, III: mixtures of exponential distributions. AT & T Bell Lab. Tech. J. 63, 163–175.Google Scholar
Whitt, W. (1985) The renewal-process stationary-excess operator. J. Appl. Prob. 22, 156–167.Google Scholar