Importance sampling of heavy-tailed iterated random functions

We consider a stochastic recurrence equation of the form $Z_{n+1} = A_{n+1} Z_n+B_{n+1}$,where$$\mathbb{E}$[\log A_1]<0$,$$\mathbb{E}$[\log^+ B_1]<\infty$and${(A_n,B_n)}{n\in$\mathbb{N}$}$ is an i.i.d. sequence of positive random vectors. The stationary distribution of this Markov chain can be represented as the distribution of the random variable $Z \triangleq \sum{n=0}^\infty B_{n+1}\prod_{k=1}^nA_k$. Such random variables can be found in the analysis of probabilistic algorithms or financial mathematics, where $Z$ would be called a stochastic perpetuity. If one interprets $-\log A_n$ as the interest rate at time $n$, then $Z$ is the present value of a bond that generates $B_n$ unit of money at each time point $n$. We are interested in estimating the probability of the rare event $\{Z>x\}$, when $x$ is large; we provide a consistent simulation estimator using state-dependent importance sampling for the case, where $\log A_1$ is heavy-tailed and the so-called Cram'{e}r condition is not satisfied. Our algorithm leads to an estimator for $P(Z>x)$. We show that under natural conditions, our estimator is strongly efficient. Furthermore, we extend our method to the case, where $\{Z_n{\}}_{n\in \mathbb{N}}$ is defined via the recursive formula $Z_{n+1}={\mathrm{\Psi }}_{n+1}(Z_n)$ and $\{{\mathrm{\Psi }}_n{\}}_{n\in \mathbb{N}}$ is a sequence of i.i.d. random Lipschitz functions.