Given an integration problem $I=\int{f(x)dx}$, we can construct an ordinary Monte Carlo estimator as


where the samples $x_i$ are usually i.i.d. and drawn from the distribution $p$.

Is it possible to use a short autocorrelated sequence $y_j$ inside an i.i.d. sequence $x_i$? For example, we could sample $x_i$ from $p$; and then generate multiple samples $\{y^i_0..y^i_j\}$ from some conditional distribution $q(y|x_i)$ with $j\ll i$. If we then construct a Monte Carlo estimator as


with joint probability $q(y_j|x_i)p(x_i)$, would it converge to the correct value in this case? Should I additionally account for some correlation/normalization terms in it?


In general the answer is no. As an extreme case, suppose that the autocorrelation is 100%. That is, $y_{1}$ is drawn from the desired distribution, but due to the perfect autocorrelation, $y_{1}=y_{2}=\ldots$. The it's clear that your Monte Carlo estimate of $I$ will converge to $f(y_{1})$ rather than the correct value.

Many procedures commonly used in statistics (such as the computation of a 95% confidence interval for the mean) assume independence of the samples. In MCMC methods this is typically achieved by "thinning" the sequence of points generated by MCMC so that successive thinned samples are far enough apart in the sequence that they are effectively uncorrelated. You might for example use only every 100th point in the MCMC sequence. There are lots of practical techniques for insuring that the sequence of points coming out of your MCMC sampler are effectively uncorrelated and that the distribution has "burned in" sufficiently.

  • $\begingroup$ Thanks for the answer. Usually, we can always select such $p$ that it covers the whole support and the original estimator $E[I]$ converges. In order to make sure the autocorrelated samples also cover the whole domain, we can make sure that $j\ll i$, that is we use short autocorrelated sequences, thus limiting the maximum autocorrelation. The goal is to avoid the MCMC computation of forward and backward transition probabilities. Thus, the interesting case is a non-extreme one, where the samples are just slightly autocorrelated. $\endgroup$ – Anton May 11 '14 at 0:45
  • $\begingroup$ Just to be even more clear, the goal would be to construct a non-Markovian estimator, with just "inflates" each i.i.d. sample $x_i$ into a short autocorrelated sequence. $\endgroup$ – Anton May 11 '14 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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