Home › Azimuth Project › › - Questions

It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.4K
- Chat 502
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 73
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 718

Options

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.

## Comments

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.

`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]].`

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

resamplingstep that puts the computational effort in the most appropriate placesin a probabilistically valid way.One important thing to be aware of is that while the basic particle filter

doesfor a single timestepconvergeto the correct distribution as the number of particles increases, theydon'tconvergeuniformly in time, i.e., for afixednumber 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).`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).`

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.

`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](http://www.oup.com/us/catalog/general/subject/Physics/QuantumPhysics/?view=usa&ci=9780195310108)). In phylogenetics there is a theory of stochastic branching processes (e.g., see papers involving ["divergence"](http://www.maths.nottingham.ac.uk/personal/pmzrdw/Preprints.html)). 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.`

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

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