Sampling Quasistationary Distributions: Computational Efficiency and Particle Based Algorithms

Wednesday, March 18, 2015 - 11:20am - 12:00pm
Klaus 1116
Roberto Oliveira (Institute of Pure and Applied Mathematics (IMPA))
Quasistationary distributions (or QSDs) are the long term distributions of Markov processes that are conditioned on not visiting a certain subset of the state space. Examples include biological models conditioned on non extinction, random walk conditioned on not leaving a bounded domain, and queueing systems conditioned on not clearing up.

In this talk we will report on some work in progress about the complexity of (approximate) sampling from QSDs of finite state Markov chains. In principle, one could imagine an analogy with the usual theory for stationary distributions, but we will show that QSDs are harder: small quasistationary mixing time does *not* imply efficient sampling in a natural computational model. On the positive side, we use a natural particle based algorithm to prove that efficient sampling is possible under certain extra conditions, which may include a good starting distribution. The example of random walk in a bounded domain will show that (modulo some technicalities) our bounds are good enough to pass to the continuum limit of Brownian motions.