Importance sampling (which is a variance reduction technique for
stochastic simulation) has become a standard tool for estimating
probabilities of rare-events. Recently, in work by Chen, Diaconis,
Holmes and Liu (2005), this technique was also applied to count the
number of bipartite graphs with a given degree sequence. Although
empirical evidence suggests that importance sampling may be a
suitable technique for approximate counting, the theoretical support
to substantiate this evidence is still under development. We shall
discuss a new technique, based on Lyapunov bounds for Markov chains,
that can be used to analyze the complexity of state-dependent
importance sampling algorithms for rare-events and counting. Using
this technique, we analyze the complexity of the algorithm proposed
by Chen et al (2005) and show that its complexity grows quadratically
in the sum of the degrees (if the maximum degree satisfies an
appropriate growth condition). Connections between rare-event
simulation algorithms, counting and large deviation analysis of
stochastic processes will be discussed.