I was thinking about studying bounds on the multivariate empirical cumulative distribution function for samples from an MCMC chains. The multivariate Dvoretzky–Kiefer–Wolfowitz inequality would seem almost fit for this purpose except it assumes IID samples whereas my samples will be Markovian.

I think that any difference due to assuming IID vs Markov property will vanish. The number of adjacent random variables in the chain is $n-1$ while the number of pairs between random variables is $\frac{n^2-n}{2}$. Their ratio in terms of the sample size $n \geq 2$ gives

$$\frac{n-1}{\frac{n^2-n}{2}} = \frac{2}{n}$$

which indicates that even if adjacent samples are statistically dependent we will still have $$\lim_{n \rightarrow \infty} \frac{2}{n} = 0.$$

Most of the chains I run are $n \geq 2000$, so this fraction for me is $\frac{2}{n} \leq \frac{1}{1000}$ which does subjectively seem pretty small to me.

But even so, assuming the Markov property instead of IID, is there an adjusted preasymptotic bound I can use for CDF over a collection of sampled instances of my parameters? Or am I falsely assuming there should exist an adjustment?


1 Answer 1


No, this isn't going to work in any straightforward way. The difference between IID and Markov Chain bounds is the whole problem. That is, going from bounds for a mean to bounds for an empirical CDF is solved by the Dvoretzky–Kiefer–Wolfowitz inequality, but the problem of getting bounds even for a mean is the part that's actually difficult.

The autocorrelation of outputs from MCMC isn't just between adjacent samples; it can be quite long range. For example, a random-walk Metropolis algorithm can spend arbitrarily long wandering around one mode of a target distribution without ever encountering the other modes. It's true that the past and future are independent conditional on the present, by the Markov property, but you need the unconditional distributions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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