We study the large deviation behavior of iterated random functions of the form

V(n) = F_n(V(n-1)),

where {F_n} is an i.i.d. sequence of random maps satisfying a cancellation condition, implying that F_n behaves roughly like multiplicative random walk as the process escapes to infinity. Our results resembe Cramer-type asymptotics for the "large" exceedances, whereas for the "small" exceedances we obtain a different asyptotic regime. In either case, these asymptotic results suggest distinct importance sampling algorithms for computationally estimating these rare-event probabilities, which we briefly describe.