Estimating tail probabilities of heavy tailed distributions with asymptotically zero relative error |
| |
Authors: | S Juneja |
| |
Institution: | (1) Tata Institute of Fundamental Research, Mumbai, India |
| |
Abstract: | Efficient estimation of tail probabilities involving heavy tailed random variables is amongst the most challenging problems
in Monte-Carlo simulation. In the last few years, applied probabilists have achieved considerable success in developing efficient
algorithms for some such simple but fundamental tail probabilities. Usually, unbiased importance sampling estimators of such
tail probabilities are developed and it is proved that these estimators are asymptotically efficient or even possess the desirable
bounded relative error property. In this paper, as an illustration, we consider a simple tail probability involving geometric
sums of heavy tailed random variables. This is useful in estimating the probability of large delays in M/G/1 queues. In this setting we develop an unbiased estimator whose relative error decreases to zero asymptotically. The key
idea is to decompose the probability of interest into a known dominant component and an unknown small component. Simulation
then focuses on estimating the latter ‘residual’ probability. Here we show that the existing conditioning methods or importance
sampling methods are not effective in estimating the residual probability while an appropriate combination of the two estimates
it with bounded relative error. As a further illustration of the proposed ideas, we apply them to develop an estimator for
the probability of large delays in stochastic activity networks that has an asymptotically zero relative error.
|
| |
Keywords: | Bounded relative error Asymptotically zero relative error Complexity Rare event simulation Regular variation M/G/1 queue Subexponential distribution Importance sampling Conditional Monte-Carlo Control variate |
本文献已被 SpringerLink 等数据库收录! |
|