Efficient rare-event simulation for the maximum of heavy-tailed random walks

DOI10.1214/07-AAP485zbMATH Open1147.60315arXiv0808.2731OpenAlexW1985912219MaRDI QIDQ939072FDOQ939072

Authors: Jose Blanchet, Peter W. Glynn 

Publication date: 20 August 2008

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: Let $(X_n:ngeq0)$ be a sequence of i.i.d. r.v.'s with negative mean. Set $S_0=0$ and define $S_n=X_1+\mathrm{...}+X_n$. We propose an importance sampling algorithm to estimate the tail of $M=max{S}_n:ngeq0$ that is strongly efficient for both light and heavy-tailed increment distributions. Moreover, in the case of heavy-tailed increments and under additional technical assumptions, our estimator can be shown to have asymptotically vanishing relative variance in the sense that its coefficient of variation vanishes as the tail parameter increases. A key feature of our algorithm is that it is state-dependent. In the presence of light tails, our procedure leads to Siegmund's (1979) algorithm. The rigorous analysis of efficiency requires new Lyapunov-type inequalities that can be useful in the study of more general importance sampling algorithms.

Full work available at URL: https://arxiv.org/abs/0808.2731

Recommendations

• State-dependent importance sampling for regularly varying random walks
• Rare-event simulation of heavy-tailed random walks by sequential importance sampling and resampling
• Uniformly Efficient Importance Sampling for the Tail Distribution of Sums of Random Variables
• State-independent importance sampling for random walks with regularly varying increments
• Efficient rare event simulation for heavy-tailed compound sums

zbMATH Keywords

heavy-tailsrandom walksrare-event simulationsingle-server queuestate-dependent importance samplingchange-of-measureLyapunov bounds

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Extreme value theory; extremal stochastic processes (60G70) Analysis of algorithms (68W40) Sums of independent random variables; random walks (60G50) Discrete-time Markov processes on general state spaces (60J05)

Cites Work

• Title not available (Why is that?)
• Monte Carlo strategies in scientific computing
• Applied Probability and Queues
• Stochastic simulation: Algorithms and analysis
• Markov chains and stochastic stability
• Large deviations results for subexponential tails, with applications to insurance risk
• Title not available (Why is that?)
• Importance sampling in the Monte Carlo study of sequential tests
• Introduction to rare event simulation.
• Title not available (Why is that?)
• Importance Sampling, Large Deviations, and Differential Games
• Rare events simulation for heavy-tailed distributions
• Simulating heavy tailed processes using delayed hazard rate twisting
• Improved algorithms for rare event simulation with heavy tails
• Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed \(G/G/1\) queue
• On the inefficiency of state-independent importance sampling in the presence of heavy tails
• On Probabilities of Large Deviations for Random Walks. I. Regularly Varying Distribution Tails
• Importance sampling for sums of random variables with regularly varying tails
• Efficient rare event simulation for heavy-tailed compound sums

Cited In (45)

• Editorial: rare-event simulation for queues
• Efficient Simulation of Random Walks Exceeding a Nonlinear Boundary
• Asymptotics and fast simulation for tail probabilities of maximum of sums of few random variables
• Total variation approximations and conditional limit theorems for multivariate regularly varying random walks conditioned on ruin
• Efficient simulation of light-tailed sums: An old-folk song sung to a faster new tune\dots
• State-independent importance sampling for random walks with regularly varying increments
• Efficient rare event simulation for heavy-tailed systems via cross entropy
• Rare-event simulation of heavy-tailed random walks by sequential importance sampling and resampling
• A sequential Monte Carlo approach to computing tail probabilities in stochastic models
• Efficient simulation of tail probabilities of sums of correlated lognormals
• Efficient simulation and conditional functional limit theorems for ruinous heavy-tailed random walks
• Importance sampling algorithms for first passage time probabilities in the infinite server queue
• Robust transient analysis of multi-server queueing systems and feed-forward networks
• Analysis of a splitting estimator for rare event probabilities in Jackson networks
• Efficient simulation of finite horizon problems in queueing and insurance risk
• Efficient rare-event simulation for perpetuities
• Importance Sampling for Failure Probabilities in Computing and Data Transmission
• Estimating tail probabilities of the ratio of the largest eigenvalue to the trace of a Wishart matrix
• The efficient computation and the sensitivity analysis of finite-time ruin probabilities and the estimation of risk-based regulatory capital
• Error rates and improved algorithms for rare event simulation with heavy Weibull tails
• Rare-event simulation for stochastic recurrence equations with heavy-tailed innovations
• A dichotomy for sampling barrier-crossing events of random walks with regularly varying tails
• Efficient Rare-Event Simulation for Multiple Jump Events in Regularly Varying Random Walks and Compound Poisson Processes
• A cross-entropy scheme for mixtures
• Markov chain importance sampling with applications to rare event probability estimation
• Permutation \(p\)-value approximation via generalized Stolarsky invariance
• Nonasymptotic performance analysis of importance sampling schemes for small noise diffusions
• Importance sampling for a simple Markovian intensity model using subsolutions
• Efficient rare event simulation for heavy-tailed compound sums
• Efficient simulations for the exponential integrals of Hölder continuous Gaussian random fields
• Tail asymptotics for delay in a half-loaded \(\mathrm{GI}/\mathrm{GI}/2\) queue with heavy-tailed job sizes
• Importance sampling of heavy-tailed iterated random functions
• Rare-event simulation for neural network and random forest predictors
• Importance sampling for metastable and multiscale dynamical systems
• The convergence rate and asymptotic distribution of the bootstrap quantile variance estimator for importance sampling
• Efficient importance sampling for binary contingency tables
• Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed \(G/G/1\) queue
• On the inefficiency of state-independent importance sampling in the presence of heavy tails
• Moderate deviation principles for importance sampling estimators of risk measures
• On importance sampling with mixtures for random walks with heavy tails
• Rare events in random geometric graphs
• The sample size required in importance sampling
• Efficient importance sampling in ruin problems for multidimensional regularly varying random walks
• State-dependent importance sampling for regularly varying random walks
• Importance sampling in path space for diffusion processes with slow-fast variables

This page was built for publication: Efficient rare-event simulation for the maximum of heavy-tailed random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q939072)