Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Edit: I simplified the example to a canonical case for clarity.

Given an integral $\int_{\Omega}{g(\mathbf{x})}$ with a well-posed integrand $g(\mathbf{x})$ defined on some multidimensional space $\Omega$, one can integrate it successfully with a Markov Chain Monte Carlo method, in particular using Metropolis-Hastings method. Detailed balance and ergodicity are achieved with any well-posed (samplable) integrand. Transition kernel $K(\dot{},\dot{})$ is Harris recurrent and its transition probability is known for every pair $(\mathbf{x},\mathbf{y})$. The value of the desired integral is always finite, even in presence of delta distributions in the integrand. This is given.

In the case of interest, the integrand is of a form $f(\mathbf{x})=\delta_{\mathbf{x}_0}(\mathbf{x})\dot{} g(\mathbf{x}) + h(\mathbf{x})$ and consists of a delta distribution at some unknown location $\mathbf{x}_0\in \Omega$ and some regular (well-posed) non-zero functions $g(\mathbf{x})$ and $h(\mathbf{x})$. This delta distribution cannot be sampled explicitly or using numerical optimization (given). This makes such an integrand unsamplable with random walk.

I mollify (approximate to the identity) this delta distribution using some mollifier (normalized smooth function $\phi_\epsilon(\mathbf{x})=\epsilon^{-1}\phi\left(\frac{\mathbf{x}}{\epsilon}\right)$ with some bandwidth $\epsilon$). This leads to a tempered integrand $f_\epsilon(\mathbf{x})=\phi_\epsilon(\mathbf{x}-\mathbf{x}_0)\dot{} g(\mathbf{x})+h(\mathbf{x})$. During the integration, at every step $n$, I gradually shrink the parameter $\epsilon_n$ to zero in order to achieve $f_{\epsilon_n} \to f$ as $n \to \infty$ in spirit of serial tempering and simulated annealing.

One cannot use parallel or serial tempering here, as the probability of the proposal to descend from a tempered mixture to the original integrand $f$ at the exact location $\mathbf{x}_0$ of the delta distribution is zero.

Thus I have two rather similar questions:

  1. Would the integral converge to the proper value $g(\mathbf{x_0})+\int_{\Omega}{h(\mathbf{x})}$ with such scheme?
  2. What are the conditions for the asymptotic decrease rate of the sequence $\epsilon_n$ that guarantees the consistency of the MCMC integration? In other words, the rate that allows the integral to converge before parts of the integrand $f_{\epsilon_n}$ become unsamplable?
share|improve this question
add comment

1 Answer

I don't know how committed you are to decreasing epsilon at every step; doing so makes theory a bit harder, at least for me. In any case, as your second question suggests, the answer is that everything should work out fine if you're a little bit careful; checking that you're being careful depends on the values of g,h and your space.

If you're willing to decrease epsilon by a factor of two at certain steps T(1), T(2), ... then the answers become:

1) Yes, if T(i) grows sufficiently quickly 2) There are many answers, depending on what you know! Bremaud's undergraduate text on Markov chains and such gives a proof that simulated annealing works which should be almost exactly what you want here. Essentially, within each epoch $T(i+1) - T(i)$, you should be able to guarantee mixing of your Markov chain to the extent that your integral is within some error $\epsilon(i)$ of the integral of $f_{\epsilon(i)}$ with probability at least e.g. $1 - i^{-2}$. Furthermore, you should be able to guarantee that the integral of $f_{\epsilon(i)}$ is within $\delta(i)$ of the integral of $f$.

As long as $\epsilon(i)$ and $\delta(i)$ go to 0, and $T(i+1) - T(i)$ is sufficiently large for these conditions to hold, you will have convergence.

Of course, in real life, this requires knowledge of e.g. the spikiness of $f_{\epsilon}$ as well as good information about the convergence of your underlying chain.

share|improve this answer
    
I'm not restricted by the demollification rate. Functions $g$ and $h$ are bounded and Lipschitz-continuous almost everywhere. What bothers me the most are two things: 1. Simulated annealing is proven for optimization, where only one point of the function is of interest. Here the whole coverage of the integrand is of interest. So one needs to ensure a stronger condition: it doesn't only converge to something, but to the ground truth value in the limit. 2. Seems like the majority of the proofs base on the assumption that the function is samplable. This is not true for the original $f(x)$. –  Anton Jul 25 '12 at 10:04
    
Thanks a lot for you reply. Also just out of curiosity, why the probability should be $1-i^{-2}$? If I know the complete transition kernel for each epoch $T(i)$, how can I ensure the probability of this event? –  Anton Jul 25 '12 at 15:14
    
Sorry for the late response - I don't check so often. The $1 - i^{2}$ was just chosen so that the error term is summable; there's nothing special about that particular answer. In general, finding this answer is pretty hard for real problems'. If you can find the spectral gap for your transition kernel, that gives a pretty good bound on the error probability', which is normally called the `total variation distance to stationarity' in the literature I'm familiar with. Best of luck! –  passing_by Aug 6 '12 at 12:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.