Question about stochastic processes - esp. for Tweed and Urban?

John Baez

Hi! Once upon a time we were talking about something like this... I only vaguely remember it, so interpret this generously, through a fuzzy lens:

There's some known way of trying to sample a random distribution which is a bit like Markov chain Monte Carlo, but instead of a single point (or "particle") walking around randomly, you have a bunch of particles, which can split at various times, and/or die out. Or something like that. Do you remember what I'm talking about? What was it?

All of a sudden this seems exactly like the "phylogenetic trees" discussed on the blog. In these trees we have a Markov chain of random DNA evolution along each edge, but sometimes species split (or die out, but people don't talk about that as much).

I may be modifying my memory of our old conversation to make it seem more similar to the new stuff.

Tim van Beek

I remember talking about stochastic filters, especially for climate time series (hockey stick), which also resulted in the page particle filter (see also Wikipedia, this may be your memory hook) and Temporal filtering.

DavidTweed

Tim's right: that sounds like particle filters, although the page on temporal filtering is more complete and understandable than the stub on particle filter. Another name for a particle filter is "sequential Monte Carlo methods". If there was a specific context you were thinking about this I can see if I know of any pertinent references. It sounds like you're thinking about using them to explore a tree of possible structures rather than track something over time. This sounds interesting, but the key requirement is to come up with a resampling step that puts the computational effort in the most appropriate places in a probabilistically valid way.

One important thing to be aware of is that while the basic particle filter does for a single timestep converge to the correct distribution as the number of particles increases, they don't converge uniformly in time, i.e., for a fixed number of particles one can show that even with the resampling scheme the approximation does (in probability) get worse as time progresses. (It seems like variants have been developed which are do converge uniformly in time, but I haven't done more than look at the titles on a search engine).

Nathan Urban

Yes, this is sequential Monte Carlo (special cases are particle filters and population Monte Carlo). "Populations of walkers" are used in various quantum Monte Carlo algorithms (see a historical review of the QMC literature).

In phylogenetics there is a theory of stochastic branching processes (e.g., see papers involving "divergence"). I don't know how it relates mathematically to sequential Monte Carlo, but the author of those papers (a collaborator of mine) probably would, since he has worked both on phylogeny and SMC. There are probably a lot of similarities.

John Baez

Thanks! There's something fun going on here...