Importance sampling of heavy-tailed iterated random functions

We consider the stationary solution Z of the Markov chain {Z_n}_nϵℕ defined by Z_n+1=ψ_n+1(Z_n), where {ψ_n}_{nϵ ℕ} is a sequence of independent and identically distributed random Lipschitz functions. We estimate the probability of the event {Z>x} when x is large, and develop a state-dependent importance sampling estimator under a set of assumptions on ψ_n such that, for large x, the event {Z>x} is governed by a single large jump. Under natural conditions, we show that our estimator is strongly efficient. Special attention is paid to a class of perpetuities with heavy tails.