Counting, Rare-events and Efficient Importance Sampling

Jose Blanchet
Department of Statistics
Harvard University


Friday, February 23, 2006
3:00 - 4:00 PM
Thornton 110


Abstract:

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.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html