Efficient rare-event simulation for the maximum of heavy-tailed random walks
From MaRDI portal
Publication:939072
change-of-measureheavy-tailsLyapunov boundsrandom walksrare-event simulationsingle-server queuestate-dependent importance sampling
Sums of independent random variables; random walks (60G50) Extreme value theory; extremal stochastic processes (60G70) Discrete-time Markov processes on general state spaces (60J05) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Analysis of algorithms (68W40)
Abstract: Let be a sequence of i.i.d. r.v.'s with negative mean. Set and define . We propose an importance sampling algorithm to estimate the tail of 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.
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
Cites work
- Applied Probability and Queues
- Efficient rare event simulation for heavy-tailed compound sums
- Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed \(G/G/1\) queue
- scientific article; zbMATH DE number 1221798 (Why is no real title available?)
- scientific article; zbMATH DE number 1026574 (Why is no real title available?)
- scientific article; zbMATH DE number 3088537 (Why is no real title available?)
- Importance sampling for sums of random variables with regularly varying tails
- Importance sampling in the Monte Carlo study of sequential tests
- Importance Sampling, Large Deviations, and Differential Games
- Improved algorithms for rare event simulation with heavy tails
- Introduction to rare event simulation.
- Large deviations results for subexponential tails, with applications to insurance risk
- Markov chains and stochastic stability
- Monte Carlo strategies in scientific computing
- On Probabilities of Large Deviations for Random Walks. I. Regularly Varying Distribution Tails
- On the inefficiency of state-independent importance sampling in the presence of heavy tails
- Rare events simulation for heavy-tailed distributions
- Simulating heavy tailed processes using delayed hazard rate twisting
- Stochastic simulation: Algorithms and analysis
Cited in
(45)- Importance sampling algorithms for first passage time probabilities in the infinite server queue
- Permutation p-value approximation via generalized Stolarsky invariance
- The sample size required in importance sampling
- Estimating tail probabilities of the ratio of the largest eigenvalue to the trace of a Wishart matrix
- Rare events in random geometric graphs
- Efficient importance sampling for binary contingency tables
- Total variation approximations and conditional limit theorems for multivariate regularly varying random walks conditioned on ruin
- Efficient rare event simulation for heavy-tailed systems via cross entropy
- Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed \(G/G/1\) queue
- Efficient simulation of finite horizon problems in queueing and insurance risk
- Editorial: rare-event simulation for queues
- Error rates and improved algorithms for rare event simulation with heavy Weibull tails
- On the inefficiency of state-independent importance sampling in the presence of heavy tails
- Rare-event simulation for stochastic recurrence equations with heavy-tailed innovations
- The convergence rate and asymptotic distribution of the bootstrap quantile variance estimator for importance sampling
- Importance Sampling for Failure Probabilities in Computing and Data Transmission
- Efficient simulation of light-tailed sums: An old-folk song sung to a faster new tune\dots
- Nonasymptotic performance analysis of importance sampling schemes for small noise diffusions
- Efficient importance sampling in ruin problems for multidimensional regularly varying random walks
- State-dependent importance sampling for regularly varying random walks
- Efficient simulation and conditional functional limit theorems for ruinous heavy-tailed random walks
- Efficient rare-event simulation for perpetuities
- Importance sampling for metastable and multiscale dynamical systems
- The efficient computation and the sensitivity analysis of finite-time ruin probabilities and the estimation of risk-based regulatory capital
- Asymptotics and fast simulation for tail probabilities of maximum of sums of few random variables
- Efficient rare event simulation for heavy-tailed compound sums
- On importance sampling with mixtures for random walks with heavy tails
- Moderate deviation principles for importance sampling estimators of risk measures
- A dichotomy for sampling barrier-crossing events of random walks with regularly varying tails
- Rare-event simulation of heavy-tailed random walks by sequential importance sampling and resampling
- Efficient Rare-Event Simulation for Multiple Jump Events in Regularly Varying Random Walks and Compound Poisson Processes
- Analysis of a splitting estimator for rare event probabilities in Jackson networks
- Efficient simulations for the exponential integrals of Hölder continuous Gaussian random fields
- Importance sampling of heavy-tailed iterated random functions
- State-independent importance sampling for random walks with regularly varying increments
- A cross-entropy scheme for mixtures
- Efficient Simulation of Random Walks Exceeding a Nonlinear Boundary
- A sequential Monte Carlo approach to computing tail probabilities in stochastic models
- Importance sampling for a simple Markovian intensity model using subsolutions
- Rare-event simulation for neural network and random forest predictors
- Efficient simulation of tail probabilities of sums of correlated lognormals
- Importance sampling in path space for diffusion processes with slow-fast variables
- Robust transient analysis of multi-server queueing systems and feed-forward networks
- Markov chain importance sampling with applications to rare event probability estimation
- Tail asymptotics for delay in a half-loaded \(\mathrm{GI}/\mathrm{GI}/2\) queue with heavy-tailed job sizes
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)
