# near independence of markov chain observations at high lags

I have to simulate independent draws from a very complicated distribution. They only feasible way appears to be using MCMC. I was considering running thousands of chains in parallel, but that would slow things down from me considerably. So I am running one long MCMC chain. Assuming that MCMC chain run did converge nicely ( I realize even determining this is practically impossible in general). . Can I argue that the thinned sample obtained from selecting every 100th observation (or at a sufficiently high lag at which the observed autocorrelation function is close to 0) effectively approximates ,in some sense, a i.i.d draw from the desired distribution. If yes, any references would be greatly appreciated.

-
yes - and that is what people usually do in statistics. You could try to plot the autocorrelation function to get an idea of the lag to be used. What is the dimension of the target probability distribution ? – Alekk Jun 14 '10 at 22:16
12. I want to justify the low correlation implies independence. – Arin Chaudhuri Jun 19 '10 at 15:50

From talking to statisticians, it seems like the standard thing to do is assume a yes. For a specified sequence or thinning, one can create Markov chains which exhibit 0 autocorrelation but a 'very large' amount of dependence despite the thinning, but the idea is that this should be pretty pathological, and so you are probably 'pretty safe'. The examples that come to mind for me are chains like '$X_{t}$ is iid 0-1 for t not divisible by a million, and equal to the sum of the previous 999,999 $X_{s}$ mod 2 for t divisible by a million'

So, you won't get any sort of theoretical justification without telling us something about your chain, because there really are bad chains out there, where what you want fails badly... but in the real world, you can probably wave your hands. Note that just increasing your thinning isn't enough to get rid of this - for any finite amount of thinning, there are bad chains which horribly violate independence despite having 0 covariance.

There is a big world of convergence diagnostics out there. Gelman-Rubin, as pointed out, is a standard. Some other standards include the Geweke test, Mykland-Yu's Cusum test, Raftery-Lewis, and Heidelberg-Welch. There is a lot of literature on each of these, but with the slight exception of some easy calculations in Mykland-Yu, it is all extremely handwavey.

-

Hi,

Thinning samples won't change your target distribution. It's probably a good idea since you'll end up with very unweildy data files otherwise (A brief mention of this is made in Bayesian Data Analysis by Gelman et al page 295).

Another unrelated point is that even though running parallel chains won't help reach convergence faster, it does open up possibilities for testing convergence ( eg Gelman Rubin diagnostic ).

-
I am not attempting to change the target distribution, I am trying to get approximately independent samples from the target distribution. – Arin Chaudhuri Jun 14 '10 at 21:13
Sorry if I wasn't clear ... basically what I was trying to say is that you can thin with whatever interval you like. Your thinned set of samples will come from the same distribution as your unthinned set. – Ira Jun 14 '10 at 22:39
I agree, but the autocorrelation among the members of the thinned sample will be smaller in general (assuming the convergence went well), making it closer to being an independent sample. I just found a link where the point I am trying to make has been made : bit.ly/dyIqEj . However, the justification is too hand wavy for my taste, I would prefer a more mathematical justification. – Arin Chaudhuri Jun 15 '10 at 1:06
No worries ... now I finally understand your question properly :). From my very hand wavy practical perspective it seems reasonable that if the thinned samples are not autocorrelated then they are independent? I'm not in a position to provide any rigorous proofs though .. sorry. – Ira Jun 15 '10 at 1:41