  In this paper, we present a method for computing the marginal likelihood,
also known as the model likelihood or Bayesian evidence, from Markov Chain
Monte Carlo (MCMC), or other sampled posterior distributions. In order to do
this, one needs to be able to estimate the density of points in parameter
space, and this can be challenging in high numbers of dimensions. Here we
present a Bayesian analysis, where we obtain the posterior for the marginal
likelihood, using $k$th nearest-neighbour distances in parameter space, using
the Mahalanobis distance metric, under the assumption that the points in the
chain (thinned if required) are independent. We generalise the algorithm to
apply to importance-sampled chains, where each point is assigned a weight. We
illustrate this with an idealised posterior of known form with an analytic
marginal likelihood, and show that for chains of length $\sim 10^5$ points, the
technique is effective for parameter spaces with up to $\sim 20$ dimensions. We
also argue that $k=1$ is the optimal choice, and discuss failure modes for the
algorithm. In a companion paper (Heavens et al. 2017) we apply the technique to
the main MCMC chains from the 2015 Planck analysis of cosmic background
radiation data, to infer that quantitatively the simplest 6-parameter flat
$\Lambda$CDM standard model of cosmology is preferred over all extensions
considered.
