Importance sampling rare trajectories in reverse time

Ancestral relationships in population genetics are typically modeled by random, labelled trees. The observed data corresponds to a configuration of leaf labels, and likelihood evaluations can be thought of as the probability of the random tree, started at the root, hitting the observed leaf label configuration before the number of leaves exceeds the sample size. A standard method for estimating these hitting probabilities is via reverse time importance sampling, where trees are grown backwards in time from the observed configuration to the root. Thus every particle is guaranteed to have positive weight.

In this talk I will introduce reverse time importance sampling as a generic algorithm and characterise the class of rare event problems to which it is well suited. This class is largely disjoint from settings where classical, forwards-in-time importance sampling and spitting methods are successful. I will also show how reverse-time proposal distributions can often be naturally designed from low-dimensional conditional sampling distributions, even when the dimension of the problem is high.