Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-25T08:01:53.308Z Has data issue: false hasContentIssue false
  • English
  • Français

Large deviations, moderate deviations, and queues with long-range dependent input

Part of: Stochastic processes Special processes Limit theorems Operations research and management science

Published online by Cambridge University Press:  01 July 2016

Cheng-Shang Chang ,
David D. Yao  and
Tim Zajic
Cheng-Shang Chang*
Affiliation:
National Tsing Hua University
David D. Yao*
Affiliation:
Columbia University
Tim Zajic*
Affiliation:
University of Minnesota
*
∗ Postal address: Department of Electrical Engineering, National Tsing Hua University, Hsinchu 30043, Taiwan, R.O.C.
∗∗ Postal address: Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027-6699, USA.
∗∗∗ Postal address: School of Mathematics, University of Minnesota, 514 Vincent Hall, 206 Church St. SE, Minneapolis, MN 55455, USA. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Long-range dependence has been recently asserted to be an important characteristic in modeling telecommunications traffic. Inspired by the integral relationship between the fractional Brownian motion and the standard Brownian motion, we model a process with long-range dependence, Y, as a fractional integral of Riemann-Liouville type applied to a more standard process X—one that does not have long-range dependence. When X takes the form of a sample path process with bounded stationary increments, we provide a criterion for X to satisfy a moderate deviations principle (MDP). Based on the MDP of X, we then establish the MDP for Y. Furthermore, we characterize, in terms of the MDP, the transient behavior of queues when fed with the long-range dependent input process Y. In particular, we identify the most likely path that leads to a large queue, and demonstrate that unlike the case where the input has short-range dependence, the path here is nonlinear.

Keywords

Sample path large deviations and moderate deviationslong-range dependenceweak convergencequeues

MSC classification

Primary: 60F10: Large deviations 60K25: Queueing theory 90B22: Queues and service
Secondary: 60G18: Self-similar processes
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 31 , Issue 1 , March 1999 , pp. 254 - 278
Copyright
Copyright © Applied Probability Trust 1999 

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

Anantharam, V. (1989). How large delays build up in a GI/G/1 queue. Queueing Systems 5, 345–368.CrossRefGoogle Scholar
Barbe, P. and Broniatowski, M. (1998). Note on functional large deviation principle for fractional ARIMA processes. Statistical Inference for Stochastic Processes 1, 17–27.Google Scholar
Beran, J. (1994). Statistics for Long-Memory Processes. Chapman and Hall, New York.Google Scholar
Billingsley, P. (1968). Convergence of Probability Measures. Wiley, New York.Google Scholar
Chang, C. S. (1994). Stability, queue length and delay of deterministic and stochastic queueing networks. IEEE Trans. Automat. Control 39, 913–931.CrossRefGoogle Scholar
Chang, C. S. (1995). Sample path large deviations and intree networks. Queueing Systems 20, 7–36.Google Scholar
Chang, C. S. and Thomas, J. S. (1995). Effective bandwidth in high speed digital networks. IEEE J. Sel. Area Commun. 13, 1091–1100.CrossRefGoogle Scholar
Cox, D. R. (1984). Long-range dependence: a review. In Statistics: An Appraisal. ed. David, H. A. and David, H. T. Iowa State University Press, Ames, Iowa, pp. 55–74.Google Scholar
Dembo, A. (1996). Moderate deviations for martingales with bounded jumps. Electron. Commun. Prob. 1, 11–17.CrossRefGoogle Scholar
Dembo, A. and Zajic, T. (1995) Large deviations from empirical mean and measure to partial sums processes. Stoch. Proc. Appl. 57, 191–224.Google Scholar
Dembo, A. and Zeitouni, O. (1992). Large Deviations Techniques and Applications. Jones and Barlett, Boston.Google Scholar
Duffield, N. G. and O'Connell, N. (1995). Large deviations and overflow probabilities for the general single-server queue, with applications. Math. Proc. Cam. Philos. Soc. 118, 363–374.CrossRefGoogle Scholar
Ellis, R. (1984). Large deviations for a general class of random vectors. Ann. Prob. 12, 1–12.CrossRefGoogle Scholar
Gao, F. Q. (1996). Moderate deviations for martingales and mixing random processes. Stoch. Proc. Appl. 61, 263–275.Google Scholar
Gärtner, J., (1977). On large deviations from invariant measure. Theory Prob. Appl. 22, 24–39.Google Scholar
Glynn, P. W. and Whitt, W. (1994). Logarithmic asymptotics for steady-state tail probabilities in a single-server queue. In Studies in Applied Probability, ed. Galambos, J. and Gani, J. (J. Appl. Prob. 31A). Applied Probability Trust, Sheffield, UK, pp. 131–156.Google Scholar
Glynn, P. W. and Whitt, W. (1994). Large deviations behavior of counting processes and their inverses. Queueing Systems 17, 107–128.Google Scholar
Harrison, J. M. (1985). Brownian Motion and Stochastic Flow Systems. Wiley, New York.Google Scholar
Ibragimov, I. and Rozanov, Y (1978). Gaussian Random Processes. Springer, New York.Google Scholar
Jiang, T., Wang, X. and Rao, M. (1992). Moderate deviations for some weakly dependent random processes. Statist. Prob. Lett. 15, 71–76.CrossRefGoogle Scholar
Kober, H. (1940). On fractional integrals and derivatives. Quart. J. Math. Oxford Ser. 11, 193–211.Google Scholar
Leland, W. E., Taqqu, M.-S., Willinger, W. and Wilson, D. V. (1994). On the self-similar nature of ethernet traffic. IEEE/ACM Trans. Networking 2, 1–15.CrossRefGoogle Scholar
Lévy, P., (1953). Random functions: general theory with special reference to Laplacian random functions. Univ. California Publ. Statist. 1, 331–390.Google Scholar
Mandelbrot, B. B. and van Ness, J. (1968). Fractional Brownian motions, fractional noises and applications. SIAM Rev. 10, 422–437.CrossRefGoogle Scholar
Mogulskii, A. A. (1976). Large deviations for trajectories of multidimensional random walk. Theory Prob. Appl. 21, 300–315.CrossRefGoogle Scholar
Norros, I. (1994). A storage model with self-similar input. Queueing Systems 16, 387–396.Google Scholar
Rosenblatt, M. (1976). Fractional integrals of stationary processes and the central limit theorem. J. Appl. Prob. 13, 723–732.Google Scholar
Royden, H. L. (1968). Real Analysis. Macmillan, New York.Google Scholar
Samko, S., Kilbas, A. and Marchev, O. (1993). Fractional Integrals and Derivatives: Theory and Applications. Gordon & Breach, London.Google Scholar
Schied, A. (1997). Moderate deviations and functional LIL for super-Brownian motion. Stoch. Proc. Appl. 72, 11–25.Google Scholar
Shwartz, A. and Weiss, A. (1995). Large Deviations for Performance Analysis. Chapman & Hall, London.Google Scholar
Sigman, K. and Yao, D. D. (1994). Finite moments for inventory processes. Ann. Prob., 4, 765–778.Google Scholar
Whitt, W. (1993). Tail probability with statistical multiplexing and effective bandwidths in multi-class queues. Telecommun. Systems 2, 71–107.Google Scholar
Willinger, W. (1994). Traffic modeling for high-speed networks: theory versus practice. Stochastic Networks, ed. Kelly, F. and Williams, R. IMA Volume in Mathematics and Its Applications. Springer, New York.Google Scholar
Wong, E. and Hajek, B. (1984). Stochastic Processes in Engineering Systems. Springer, New York.Google Scholar
Wu, L. (1995). Moderate deviations of dependent random variables related to CLT. Ann. Prob. 23, 420–445.Google Scholar