  We develop importance sampling based efficient simulation techniques for
three commonly encountered rare event probabilities associated with random
walks having i.i.d. regularly varying increments; namely, 1) the large
deviation probabilities, 2) the level crossing probabilities, and 3) the level
crossing probabilities within a regenerative cycle. Exponential twisting based
state-independent methods, which are effective in efficiently estimating these
probabilities for light-tailed increments are not applicable when the
increments are heavy-tailed. To address the latter case, more complex and
elegant state-dependent efficient simulation algorithms have been developed in
the literature over the last few years. We propose that by suitably decomposing
these rare event probabilities into a dominant and further residual components,
simpler state-independent importance sampling algorithms can be devised for
each component resulting in composite unbiased estimators with desirable
efficiency properties. When the increments have infinite variance, there is an
added complexity in estimating the level crossing probabilities as even the
well known zero-variance measures have an infinite expected termination time.
We adapt our algorithms so that this expectation is finite while the estimators
remain strongly efficient. Numerically, the proposed estimators perform at
least as well, and sometimes substantially better than the existing
state-dependent estimators in the literature.
