zbMATH — the first resource for mathematics

Simulation-based computation of the workload correlation function in a Lévy-driven queue. (English) Zbl 1213.60147
Summary: We consider a single-server queue with Lévy input, and, in particular, its workload process \((Q_t)_{t\geq 0}\), focusing on its correlation structure. With the correlation function defined as \(r(t):= \mathrm{cov}(Q_{0}, Q_t) / \mathrm{var} \, Q_{0}\) (assuming that the workload process is stationary at time 0), we first study its transform \(\int _{0}^{\infty }r(t)\mathrm{e}^{-\vartheta t}\,dt\), both for when the Lévy process has positive jumps and when it has negative jumps. These expressions allow us to prove that \(r(\cdot)\) is positive, decreasing, and convex, relying on the machinery of completely monotone functions. For the light-tailed case, we estimate the behavior of \(r(t)\) for large \(t\). We then focus on techniques to estimate \(r(t)\) by simulation. Naive simulation techniques require roughly \((r(t))^{-2}\) runs to obtain an estimate of a given precision, but we develop a coupling technique that leads to substantial variance reduction (the required number of runs being roughly \((r(t))^{-1})\). If this is augmented with importance sampling, it even leads to a logarithmically efficient algorithm.

60K25 Queueing theory (aspects of probability theory)
60G51 Processes with independent increments; Lévy processes
Full Text: DOI
[1] Abate, J. and Whitt, W. (1994). Transient behavior of the M/G/1 workload process. Operat. Res. 42 , 750-764. JSTOR: · Zbl 0833.90042
[2] Abate, J. and Whitt, W. (1997). Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Systems 25 , 173-233. · Zbl 0894.60088
[3] Asmussen, S. (2003). Applied Probability and Queues , 2nd edn. Springer, New York. · Zbl 1029.60001
[4] Asmussen, S. and Glynn, P. W. (2007). Stochastic Simulation: Algorithms and Analysis . Springer, New York. · Zbl 1126.65001
[5] Beneš, V. E. (1957). On queues with Poisson arrivals. Ann. Math. Statist. 28 , 670-677. · Zbl 0085.34704
[6] Bernstein, S. N. (1929). Sur les fonctions absolument monotones. Acta Math. 52 , 1-66. · JFM 55.0142.07
[7] Dȩbicki, K., Es-Saghouani, A. and Mandjes, M. (2010). Transient asymptotics of Lévy-driven queues. J. Appl. Prob. 47 , 109-129. · Zbl 1190.60087
[8] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications , 2nd edn. Springer, New York. · Zbl 0896.60013
[9] Devroye, L. (1986). Nonuniform Random Variate Generation . Springer, Berlin. · Zbl 0593.65005
[10] Doney, R. A. (2005). Some excursion calculations for spectrally one-sided Lévy processes. In Séminaire de Probabilités XXXVIII (Lecture Notes Math. 1857 ), Springer, Berlin, pp. 5-15. · Zbl 1068.60073
[11] Ensor, K. and Glynn, P. (2000). Simulating the maximum of a random walk. J. Statist. Planning Infer. 85 , 127-135. · Zbl 0974.60030
[12] Es-Saghouani, A. and Mandjes, M. (2008). On the correlation structure of a Lévy-driven queue. J. Appl. Prob. 45 , 940-952. · Zbl 1154.60348
[13] Feller, W. (1971). An Introduction to Probability Theory and Its Applications , Vol. II, 2nd edn. John Wiley, New York. · Zbl 0219.60003
[14] Kella, O., Boxma, O. J. and Mandjes, M. (2006). A Lévy process reflected at a Poisson age process. J. Appl. Prob. 43 , 221-230. · Zbl 1104.60052
[15] Kyprianou, A. E. (2006). Introductory Lectures on Fluctuations of Lévy Processes with Applications . Springer, Berlin. · Zbl 1104.60001
[16] Mandjes, M. (2007). Large Deviations for Gaussian Queues . John Wiley, Chichester. · Zbl 1125.60103
[17] Morse, P. M. (1955). Stochastic properties of waiting lines. Operat. Res. 3 , 255-261.
[18] Ott, T. J. (1977). The covariance function of the virtual waiting-time process in an M/G/1 queue. Adv. Appl. Prob. 9 , 158-168. JSTOR: · Zbl 0382.60101
[19] Pistorius, M. R. (2004). On exit and ergodicity of the spectrally one-sided Lévy process reflected at its infimum. J. Theoret. Prob. 17 , 183-220. · Zbl 1049.60042
[20] Reynolds, J. F. (1975). The covariance structure of queues and related processes–a survey of recent work. Adv. Appl. Prob. 7 , 383-415. JSTOR: · Zbl 0349.60096
[21] Williams, D. (1991). Probability with Martingales . Cambridge University Press. · Zbl 0722.60001
[22] Zolotarev, V. M. (1964). The first passage time of a level and the behaviour at infinity for a class of processes with independent increments. Theoret. Prob. Appl. 9 , 653-661. · Zbl 0149.12903
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.