C&R ->d proof

As noted by Michael Evans in the discussion containing his proof of convergence in probability (of the nested sampling marginal likelihood estimate to the true marginal likelihood), in order to bound the rate of convergence what was needed next was a proof of convergence in distribution.  This proof was soon supplied by (Nicholas) Chopin & (Christian) Robert in their Biometrika paper; again under the assumption that the replacement live point is drawn exactly from the current likelihood-constrained prior.

Although it looks complicated at first inspection, the required proof is actually quite straight-forwards to follow.  After breaking the approximation error in nested sampling down to three contributions—(i) the remainder of the integral upon stopping at a given c \times N (c times the number of live particles, N), (ii) the error of Riemann integration if the exact L_i (here $\psi_i$) to X_i pairing would be used, and (iii) the error coming from using the randomly drawn (discarded) L_i instead—the investigation turns to the behaviour of this third, stochastic term.

As can be seen below, the authors’ strategy is to find a Taylor series expansion that would allow them to write (iii) as a sum over independent standard random variables which can be approximated by an integral over Brownian motion under the assumption that the target, \psi(x), is sufficiently well behaved (continuous, bounded second derivative).  Now while Donsker’s theorem may seem like heavy artillery, it’s role as functional central limit theorem is necessary here to confirm for us that the resulting stochastic integral is Gaussian (and it provides a neat way to summarise the result).  Interesting to note is that proving the Gaussianity of the stochastic integral of a continuous function is typically done by showing its behaviour as a Riemann sum allows use of the classical central limit theorem.

ns1 ns2

Some inspiration for the present challenge from the conclusions of Chopin & Robert:

For one thing, the convergence properties of Markov chain Monte Carlo-based nested sampling are unknown and technically challenging.


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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