Abstract
The key issue in importance sampling is the choice of the alternative sampling distribution, which is often chosen from the exponential tilt family of the underlying distribution. However, when the problem exhibits certain kind of nonconvexity, it is very likely that a single exponential change of measure will never attain asymptotic optimality and can lead to erroneous estimates. In this paper we introduce an explicit iterative scheme which combines the traditional cross-entropy method and the EM algorithm to find an efficient alternative sampling distribution in the form of mixtures. We also study the applications of this scheme to the estimation of rainbow option prices.
Introduction
In Monte Carlo simulations, estimating the probability of rare events—such as extreme market fluctuations or specific asset price thresholds—is computationally expensive. Standard Monte Carlo methods require a massive number of samples to achieve accuracy for events with very low probabilities. Importance Sampling (IS) addresses this by "tilting" the sampling distribution to make the rare event more frequent, then re-weighting the results to maintain unbiasedness.
While traditional IS often relies on a single exponentially tilted distribution, this approach fails when the rare event is "non-convex." In such cases, the event can occur through multiple, distinct scenarios (e.g., either Asset A crashes or Asset B spikes). A single distribution can only target one of these modes, leading to significant variance and potentially biased estimates. This paper proposes a robust iterative scheme to find an optimal mixture of distributions that covers all relevant modes of the rare event.
Methodology: The CE-EM Framework
The primary challenge with using mixture distributions in IS is that finding the optimal parameters (weights and tilting factors) usually lacks a closed-form solution. The authors resolve this by integrating two statistical frameworks:
- Cross-Entropy (CE) Method: This is an iterative procedure designed to minimize the Kullback-Leibler (KL) divergence between the sampling distribution and the theoretically optimal zero-variance distribution.
- Expectation-Maximization (EM) Algorithm: By treating the specific mixture component from which a sample is drawn as a "latent variable," the authors derive explicit update rules.
This synergy allows the algorithm to update each component of the mixture independently during each iteration, avoiding complex multi-dimensional optimizations. To prevent "mixture collapse"—where multiple components converge to the same point—the authors suggest three initialization strategies:
- Random Perturbation: Introducing small differences in initial parameters.
- Rarity Parameter Sequence: Gradually increasing the rarity of the target event to guide the algorithm from a common event to the rare one.
- Analytical Approximation: Using mathematical insights from the model to set initial drifts.
Experimental Evaluation
The algorithm was tested against several complex benchmarks in computational finance:
- Toy Model: A two-tail probability estimation ($P(X \ge a \text{ or } X \le b)$) to test the ability to capture disconnected regions.
- Asian Options: Path-dependent options where the payoff is based on the arithmetic mean of asset prices.
- Rainbow Options: Multi-asset derivatives, including "outperformance" and "pyramid" options, involving up to four dimensions.
- CEV Model: Digital options under the Constant Elasticity of Variance model, which utilizes non-linear stochastic differential equations.
Key Results and Insights
The performance of the scheme was evaluated using the Variance Ratio (the variance of standard Monte Carlo divided by the variance of the proposed method).
- High Efficiency: In the CEV model for digital options, the method achieved a variance reduction of up to 545x for the rarest events. For 4-asset Rainbow options, the reduction reached 143x for outperformance options and 232x for pyramid options.
- Robustness to Non-Convexity: In the two-tail toy problem, the mixture method successfully identified both modes, whereas single-tilt methods failed to converge or produced biased results.
- Asymptotic Optimality: The empirical relative error remained consistently low (often below 0.5%) even as the target event became increasingly rare, indicating the scheme's stability.
Conclusion and Future Work
The combination of Cross-Entropy and EM provides a powerful, explicit framework for importance sampling with mixtures. It effectively handles non-convex rare events that traditional single-distribution methods cannot.
However, some challenges remain. Users must still manually specify the number of mixture components ($m$), though the authors provide heuristics based on the payoff function's geometry. Additionally, while the "pilot samples" used for parameter updates are computationally cheaper than the final simulation, they do introduce additional implementation complexity. Future research may focus on automating the selection of $m$ and further refining the initialization process for high-dimensional problems.
Summary updated