This article focuses on evaluating the probability that both components of a two-dimensional stochastic process will ever, but not necessarily at the same time, exceed some large level u. An important application is in determining the probability of large delays occurring in two correlated queues. Since exact analysis of this probability seems prohibitive, we focus on deriving asymptotics and on developing efficient simulations techniques. Large deviations theory is used to characterise logarithmic asymptotics. The second part of this article focuses on efficient simulation techniques. Using “nearest-neighbour random walk” as an example, we first show that a “naive” implementation of importance sampling, based on the decay rate, is not asymptotically efficient. A different approach, which we call partitioned importance sampling, is developed and shown to be asymptotically efficient. The results are illustrated through various simulation experiments.
Importance sampling, Large deviations, Logarithmic asymptotics
ACM Transactions on Modeling and Computer Simulation
Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

Cahen, E.J, Mandjes, M.R.H, & Zwart, A.P. (2018). Estimating large delay probabilities in two correlated queues. ACM Transactions on Modeling and Computer Simulation, 28(1). doi:10.1145/3158667