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

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

$E[I]=\sum\limits_i\frac{f(x_i)}{p(x_i)}$

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

$E'[I]=\sum\limits_{i,j}\frac{f(y_j)}{q(y_j|x_i)p(x_i)}$

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?

share|improve this question
add comment

1 Answer 1

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.

share|improve this answer
    
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. –  Anton May 11 at 0:45
    
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. –  Anton May 11 at 0:51
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.