×

Efficient simulation for the maximum of infinite horizon discrete-time Gaussian processes. (English) Zbl 1219.65012

Summary: We consider the problem of estimating the probability that the maximum of a Gaussian process with negative mean and indexed by positive integers reaches a high level, say \(b\). In great generality such a probability converges to 0 exponentially fast in a power of \(b\). Under mild assumptions on the marginal distributions of the process and no assumption on the correlation structure, we develop an importance sampling procedure, called the target bridge sampler (TBS), which takes a polynomial (in \(b\)) number of function evaluations to achieve a small relative error. The procedure also yields samples of the underlying process conditioned on hitting \(b\) in finite time. In addition, we apply our method to the problem of estimating the tail of the maximum of a superposition of a large number, \(n\), of independent Gaussian sources. In this situation TBS achieves a prescribed relative error with a bounded number of function evaluations as \(n \nearrow \infty \). A remarkable feature of TBS is that it is not based on exponential changes of measure. Our numerical experiments validate the performance indicated by our theoretical findings.

MSC:

65C50 Other computational problems in probability (MSC2010)
65C05 Monte Carlo methods
60G15 Gaussian processes
60F10 Large deviations
60J65 Brownian motion
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Addie, R., Mannersalo, P. and Norros, I. (1999). Most probable paths and performance formulae for buffers with Gaussian input traffic. Europ. Trans. Telecommun. 13, 183-196.
[2] Adler, R. J. and Taylor, J. E. (2007). Random Fields and Geometry . Springer, New York. · Zbl 1149.60003 · doi:10.1007/978-0-387-48116-6
[3] Adler, R. J., Blanchet, J. and Liu, J. (2008). Efficient simulation for tail probabilities of Gaussian random fields. In Proc. 40th Conf. Winter Simul. , pp. 328-336.
[4] Adler, R. J., Blanchet, J. and Liu, J. (2010). Efficient Monte Carlo for large excursions of Gaussian random fields. Preprint. Available at http://arxiv.org/abs/1005.0812v3. · Zbl 1257.60001 · doi:10.1239/jap/1276784893
[5] Alzer, H. (1997). On some inequalities for the gamma and psi functions. Math. Comput. 66, 373-389. · Zbl 0854.33001 · doi:10.1090/S0025-5718-97-00807-7
[6] Asmussen, S. and Glynn, P. W. (2007). Stochastic Simulation: Algorithms and Analysis . Springer, New York. · Zbl 1126.65001
[7] Berman, S. M. (1992). Sojourns and Extremes of Stochastic Processes . Wadsworth & Brooks/Cole, Pacific Grove, CA. · Zbl 0809.60046
[8] Blanchet, J., Glynn, P. and Lam, H. (2009). Rare event simulation for a slotted time M/G/s model. Queueing Systems 63 , 33-57. · Zbl 1209.90105 · doi:10.1007/s11134-009-9154-5
[9] Boots, N. K. and Mandjes, M. (2002). Fast simulation of a queue fed by a superposition of many (heavy-tailed) sources. Prob. Eng. Inf. Sci . 16, 205-232. · Zbl 1007.65006 · doi:10.1017/S026996480216205X
[10] Brockwell, P. J. and Davis, R. A. (1991). Time Series: Theory and Methods , 2nd edn. Springer, New York. · Zbl 0709.62080
[11] Bucklew, J. A. and Radeke, R. (2003). On the Monte Carlo simulation of digital communication systems with Gaussian noise. IEEE Trans. Commun . 51, 267-274.
[12] Chang, J. T. and Peres, Y. (1997). Ladder heights, Gaussian random walks and the Riemann zeta function. Ann. Prob. 25, 787-802. · Zbl 0880.60070 · doi:10.1214/aop/1024404419
[13] Cody, W. J. (1969). Rational Chebyshev approximations for the error function. Math. Comput. 23, 631-637. · Zbl 0182.49403 · doi:10.2307/2004390
[14] Dȩbicki, K. (1999). A note on LDP for supremum of Gaussian processes over infinite horizon. Statist. Prob. Lett. 44, 211-219. · Zbl 0943.60040 · doi:10.1016/S0167-7152(99)00011-5
[15] Dȩbicki, K. and Mandjes, M. (2003). Exact overflow asymptotics for queues with many Gaussian inputs. J. Appl. Prob. 40, 704-720. · Zbl 1041.60036 · doi:10.1239/jap/1059060897
[16] Dieker, A. B. (2005). Extremes of Gaussian processes over an infinite horizon. Stoch. Process. Appl. 115, 207-248. · Zbl 1070.60035 · doi:10.1016/j.spa.2004.09.005
[17] Dieker, A. B. and Mandjes, M. (2006). Fast simulation of overflow probabilities in a queue with Gaussian input. ACM Trans. Model. Comput. Simul. 16, 1-33. · Zbl 1390.90208
[18] Duffield, N. G. and O’Connell, N. (1995). Large deviations and overflow probabilities for the general single-server queue, with applications. Math. Proc. Camb. Phil. Soc. 118, 363-374. · Zbl 0840.60087 · doi:10.1017/S0305004100073709
[19] Dupuis, P. and Wang, H. (2004). Importance sampling, large deviations, and differential games. Stoch. Stoch. Reports 76, 481-508. · Zbl 1076.65003
[20] Durrett, R. (2004). Probability: Theory and Examples , 3rd edn. Duxbury Press, Belmont, CA. · Zbl 1202.60001
[21] Giordano, S., Gubinelli, M. and Pagano, M. (2007). Rare events of Gaussian processes: a performance comparison between bridge Monte-Carlo and importance sampling. In Next Generation Teletraffic and Wired/Wireless Advanced Networking (Lecture Notes Comput. Sci. 4712 ), Springer, Berlin, pp. 269-280.
[22] Huang, C., Devetsikiotis, M., Lambadaris, I. and Kaye, A. R. (1999). Fast simulation of queues with long-range dependent traffic. Commun. Statist. Stoch. Models 15, 429-460. · Zbl 0930.60085 · doi:10.1080/15326349908807544
[23] Hüsler, J. and Piterbarg, V. (1999). Extremes of a certain class of Gaussian processes. Stoch. Process. Appl. 83, 257–271. · Zbl 0997.60057 · doi:10.1016/S0304-4149(99)00041-1
[24] Juneja, S. and Shahabuddin, P. (2006). Rare event simulation techniques: an introduction and recent advances. In Handbook on Simulation , eds S. Henderson and B. Nelson, North-Holland, Amsterdam, pp. 291-350.
[25] Likhanov, N. and Mazumdar, R. R. (1999). Cell loss asymptotics in buffers fed with a large number of independent stationary sources. J. Appl. Prob. 36, 86-96. · Zbl 0944.60097 · doi:10.1239/jap/1032374231
[26] Mandjes, M. (2007). Large Deviations for Gaussian Queues . John Wiley, Chichester. · Zbl 1125.60103
[27] Michna, Z. (1999). On tail probabilities and first passage times for fractional Brownian motion. Math. Meth. Operat. Res. 49, 335-354. · Zbl 0953.60016
[28] Norros, I. (1999). Busy periods of fractional Brownian storage: a large deviations approach. Adv. Performance Analysis 2, 1-19.
[29] Pickands, J., III (1969). Asymptotic properties of the maximum in a stationary Gaussian process. Trans. Amer. Math. Soc. 145, 75-86. · Zbl 0206.18901 · doi:10.2307/1995059
[30] Piterbarg, V. I. (1996). Asymptotic Methods in the Theory of Gaussian Processes and Fields . American Mathematical Society, Providence, RI. · Zbl 0841.60024
[31] Sadowsky, J. S. and Bucklew, J. A. (1990). On large deviations theory and asymptotically efficient Monte Carlo estimation. IEEE Trans. Inf. Theory 36, 579-588. · Zbl 0702.60029 · doi:10.1109/18.54903
[32] Traub, J. F. (2003). Information-based complexity. In Encyclopedia of Computer Science , 4th edn. John Wiley, Chichester, pp. 850-854.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.