Convergence Proof

This is the rolling blog page for the first part of this project: to provide a convergence proof for ‘real’ nested sampling.

Q. Hasn’t this been done already?
A. No. There are indeed already a number of convergence proofs for idealised versions of nested sampling, but not yet one for the most common ‘real world’ version in which the replacement to the most recently deleted ‘live particle’ is sought via random-walk MCMC.  Existing ‘statistical’ proofs establish the convergence in probability of the Riemann sum part of nested sampling (Evans 2006) and provide a central limit theorem (convergence in distribution) for the corresponding marginal likelihood estimate (Chopin & Robert 2009)—both under the simplifying assumption that the replacement ‘live particle’ is drawn exactly from the likelihood-constrained posterior.  A similar ‘physics-y’ proof of nested sampling’s convergence in mean square has also been given by John Skilling (2008).

As a first step to catch everyone up to the current state of affairs and thereby clarify what remains to be done here I will type up some notes on the above three proofs and post them here.

Q. Why do you think a proof is feasible?
A. There’s some ‘nice’ aspects of nested sampling that I imagine help naturally alleviate the theoretical demands on random walk MCMC in this context:
– starting the chain from one of the existing ‘live particles’ means we’re starting the chain from an approximation of the stationary distribution
– since we’re only looking for a new point to supplement the existing collection of ‘live particles’ we presumably don’t need to run the chain so long as to explore the whole state space; rather we just need to run it long enough to diffuse over the scale length of the inter-particle separation
– for a wide class of likelihood functions (& priors + parameter spaces) the constrained-likelihood prior is a bounded set in R^n, allowing for uniform ergodicity* under moderate conditions

*One issue I mean to clarify here as a starting point is the definition of uniform ergodicity, or more precisely, the definition of the random walk MCMC algorithm: since there’s some disagreement here between usage in Tierney (1994) and Mengersen & Tweedie (1996).

Q. Why do you think a proof is difficult?
A. Because the current collection of ‘live particles’ depends on a complex history of draws under the previous MCMC chains and discards according to likelihood ranking.

– Also, running the chain for a finite number of steps starting from a given ‘live particle’ doesn’t guarantee that the chain will move and produce a genuinely new point: i.e., if the MCMC chain is performing poorly then we risk particle degeneracy.  This makes me think that some help will be required from the Feynman-Kac integration ideas developed by various SMC researchers (esp. Pierre Del Moral).


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s