Efficient rare-event simulation for the maximum of heavy-tailed random walks
From MaRDI portal
Publication:939072
heavy-tailsrandom walksrare-event simulationsingle-server queuestate-dependent importance samplingchange-of-measureLyapunov bounds
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)
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
- 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?)
- 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
- Importance Sampling, Large Deviations, and Differential Games
- Importance sampling for sums of random variables with regularly varying tails
- Importance sampling in the Monte Carlo study of sequential tests
- 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)- Editorial: rare-event simulation for queues
- Asymptotics and fast simulation for tail probabilities of maximum of sums of few random variables
- Efficient Simulation of Random Walks Exceeding a Nonlinear Boundary
- 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
- Efficient simulation of finite horizon problems in queueing and insurance risk
- Analysis of a splitting estimator for rare event probabilities in Jackson networks
- 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
- Error rates and improved algorithms for rare event simulation with heavy Weibull tails
- The efficient computation and the sensitivity analysis of finite-time ruin probabilities and the estimation of risk-based regulatory capital
- Rare-event simulation for stochastic recurrence equations with heavy-tailed innovations
- Markov chain importance sampling with applications to rare event probability estimation
- A dichotomy for sampling barrier-crossing events of random walks with regularly varying tails
- Permutation p-value approximation via generalized Stolarsky invariance
- Efficient Rare-Event Simulation for Multiple Jump Events in Regularly Varying Random Walks and Compound Poisson Processes
- A cross-entropy scheme for mixtures
- 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
- Importance sampling in path space for diffusion processes with slow-fast variables
- Efficient importance sampling in ruin problems for multidimensional regularly varying random walks
- State-dependent importance sampling for regularly varying random walks
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)
