How to Deal with the Curse of Dimensionality of Likelihood Ratios in Monte Carlo Simulation

R. Y. Rubinstein and P. W. Glynn

Stochastic Models, Vol. 25, 547-568 (2009)

In this work we show how to resolve, at least partially, the curse of dimensionality of likelihood ratios (LRs) while using importance sampling (IS) to estimate the performance of high-dimensional Monte Carlo simulation problems. The curse of dimensionality, which is better known as degeneracy properties of LR, is one of the central topics in Monte Carlo simulation. The current state-of-the art with IS can be summarized as follows: do not use IS in high dimensional problems because of the degeneracy properties of likelihood ratios. We present a simple method, called the screening method, which typically allows substantial reduction of the size of the LR before applying it. By doing so we not only automatically prevent the degeneracy of the IS estimators, but obtain substantial variance reduction at the same time. The main idea behind the screening algorithm is to identify (screen out) the most important parameters of the IS estimator, the so-called bottleneck parameter vector, which for typical simulation problems, are known to be of low dimension. As soon as the bottleneck parameter vector is identified, we replace the standard IS estimator with the new low-dimension alternative, where the size of the LR equals the size of the bottleneck parameter vector. Supportive numerical results are presented.