0

The wikipedia article on Metropolis-Hastings algorithm suggests that using all of the sample points produced by the algorithm as i.i.d samples from the underlying distribution is bad, since consecutive samples are autocorrelated. The article proposes undesirable solutions, such as only keeping every n-th sample, or using a large variance sampling function that would lead to lots of rejections. What I'm wondering is whether, given sufficiently many samples from the distribution, it is possible to randomly shuffle the samples to destroy the autocorrelation. Would the resulting points asymptotically match the desired distribution?

Edit: Reason for starting the bounty: I would like to know the answer to the following two questions:

  • If one obtains a very long sequence of points from MH algorithm with some reasonable generic (e.g. gaussian) sampling function, and then permutes the points, is the resulting set of points an i.i.d sample from the underlying distribution
  • Can this procedure be used in practice with finite number of points? Namely, is there a result that would bound some measure of convergence of the sampled distribution to the true distribution given the sampling function and the number of samples

It is not necessary to explicitly provide the proof. It would suffice to get a link and a conclusive answer.

Aleksejs Fomins
  • 2,240

1 Answers1

0

If I understand your question correctly, the answer is no. The point is that many samples have almost the same value, shuffling won't change that. The autocorrelation is because they are generated sequentially, so it is not really the autocorrelation per se that is the issue, but that the error in convergence to the average is not proportional to $ 1\over \sqrt N$ but rather $1\over \sqrt {N\over \ L}$ with $L$ being the correlation length.

user619894
  • 3,838
  • Thanks for the answer. I don't follow your argument. What average are you talking about? The question is if points sampled using MH asymptotically follow the sampled distribution. Shuffling is only there to make them i.i.d. The argument "many samples have almost the same value" makes no sense to me - if you take many samples from any distribution in any way, then indeed many samples will have almost the same value. Can you try to provide a more formal proof? – Aleksejs Fomins Apr 19 '21 at 10:06
  • @AleksejsFomins let me clarify: suppose you sample from a Gaussian and want to get an estimate of the variance. If you sample $L>>1$ times, the estimate would be reasonable, but suppose you take one sample and replicate it $L$ times (= many samples with the same value), then you would have to repeat this yet another 99 times to get the same accuracy as before. MC sampling has a strong correlation, so each $L$ samples are very near, and do not really contribute to calculating the distribution. – user619894 Apr 19 '21 at 10:34
  • I agree that one needs to get more samples until one arrives to a set of samples representative of the distribution. I agree that convergence to representative sample is slower. But the question is about asymptotic behaviour. The primary question is: If there are sufficiently many samples to cover the whole domain ten times over, can then the sample as a whole be considered representative, or do we still need to throw out points? If no, why? If yes, how many samples are needed to get there in practice? – Aleksejs Fomins Apr 19 '21 at 10:45
  • Yes, it is enough, however it takes $L$ times longer than a naive estimate to get this. Even ff you shuffle you would still need $L$ times the naive coverage. I don't think you actually have to "throw out" samples, just in a conceptual manner of not considering close by samples as independent. – user619894 Apr 19 '21 at 11:25
  • Thanks for your ideas. Still, I would love somebody to post a formal proof of the asymptotic case – Aleksejs Fomins Apr 19 '21 at 15:53
  • I'd like to see one as well... – user619894 Apr 19 '21 at 16:43