  Estimating the probability that a sum of random variables (RVs) exceeds a
given threshold is a well-known challenging problem. Closed-form expression of
the sum distribution is usually intractable and presents an open problem. A
crude Monte Carlo (MC) simulation is the standard technique for the estimation
of this type of probability. However, this approach is computationally
expensive especially when dealing with rare events (i.e events with very small
probabilities). Importance Sampling (IS) is an alternative approach which
effectively improves the computational efficiency of the MC simulation. In this
paper, we develop a general framework based on IS approach for the efficient
estimation of the probability that the sum of independent and not necessarily
identically distributed heavy-tailed RVs exceeds a given threshold. The
proposed IS approach is based on constructing a new sampling distribution by
twisting the hazard rate of the original underlying distribution of each
component in the summation. A minmax approach is carried out for the
determination of the twisting parameter, for any given threshold. Moreover,
using this minmax optimal choice, the estimation of the probability of interest
is shown to be asymptotically optimal as the threshold goes to infinity. We
also offer some selected simulation results illustrating first the efficiency
of the proposed IS approach compared to the naive MC simulation. The
near-optimality of the minmax approach is then numerically analyzed.
