4
$\begingroup$

Background

We want to sample from some intractable density $\pi(\theta)$. Using an MCMC algorithm, we generate a sample of draws $\{\theta_i\}_{i=1}^N$ from a Markov chain that has $\pi(\theta)$ as its invariant distribution. We typically use the draws $\{\theta_i\}_{i=1}^N$ to "approximate" $\pi(\theta)$ in the following ways:

  1. Use sample averages $(1/N)\sum_{i=1}^Nf(\theta_i)$ to approximate integrals like $$\mathbb{E}[f(\theta)] = \int f(\theta)\pi(\theta)d\theta;$$
  2. Generate histograms and kernel density estimates to visualize $\pi(\theta)$ or its marginals;
  3. Compute the ECDF $\hat{F}(\theta)=(1/N)\sum_{i=1}^N\mathbf{1}_{\theta_i\leq\theta}$ to estimate quantiles of $\pi(\theta)$.

If $\{\theta_i\}_{i=1}^N$ were direct, iid draws from $\pi(\theta)$, then there is theory that justifies all of these approximations.

Question

What exactly are the theoretical justifications for the different ways that we use MCMC draws to approximate the target distribution?

As an example, the theorems in Sections 4.5 and 4.7 of Geweke (2005) establish that the sample averages $(1/N)\sum_{i=1}^Nf(\theta_i)$ satisfy a central limit theorem with respect to the true value $\mathbb{E}[f(\theta)]$. Great. That takes care of (1).

What about (2) or (3)? What justifies using a kernel density estimator with MCMC draws, or computing the ECDF of MCMC draws?

$\endgroup$
  • 4
    $\begingroup$ Maybe I’m missing something but how is 2-3 different from 1? The virtue of any Monte Carlo procedure is that virtually anything can be formulated as an expectation. For example, $F(0)$ is just the expected value of $1_{\theta<0}$. $\endgroup$ – hejseb Aug 8 '18 at 8:44
  • $\begingroup$ Right. That's part of what I wanted to know. I know (1) is theoretically justified. Do (2) and (3) simply follow from it? $\endgroup$ – jcz Aug 8 '18 at 15:44
4
$\begingroup$

The main theoretical justification of (1), (2), and (3) is ergodicity of a Markov chain. Let $\mathcal{X}$ be the state space of the Markov chain and let $\mathcal{B}(\mathcal{X})$ be the Borel $\sigma$-algebra for $\mathcal{X}$. A Markov chain is characterized by its Markov transition kernel $P: \mathcal{X} \times \mathcal{B}(\mathcal{X}) \to [0,1]$. That is for element $x \in \mathcal{X}$ and set $A \in \mathcal{B}(\mathcal{X})$, $$P(x, A) = \Pr(X_{1} \in A \mid X_0 = x)\,.$$ After taking $t$ steps, the $t$-step transition for the Markov chain is $$P^{t}(x, A) = \Pr(X_{t} \in A \mid X_0 = x)$$

Under certain regularity conditions (aperiodicity, irreducibility and Harris recurrence), the $t$-step transition kernel converges to the stationary distribution $\pi$ in total-variation norm. That is, $$ \|P^t(x, \cdot) - \pi(\cdot)\|_{TV} \to 0 \text{ as } t \to \infty\,.$$

Convergence in total variation is strong than convergence in distribution. Thus, for large $t$, drawing from $P^{t}(x, \cdot)$ is approximately drawing from $\pi$. As a consequence of this you get (1) by the Birkhoff Ergodic Theorem for Markov chains, (2) by the definition of convergence in distribution, and (3) because it is essentially an expectation so it is a special case of (1).

$\endgroup$
  • $\begingroup$ Thanks for the answer! So, a follow-up concerning the ECDF $\hat{F}(\theta)$. As a consequence of (1), you get that $\hat{F}(\theta)$ is a valid pointwise approximation to $F(\theta)$. But in the iid case you have stronger results like the Glivenko-Cantelli theorem, which gives you uniform convergence. Does that still hold for MCMC? (Really what I'm thinking about is: "Convergence rates aside, do all of the statistical properties of iid draws carry over to MCMC draws?") $\endgroup$ – jcz Aug 8 '18 at 16:04
  • 2
    $\begingroup$ @bamts I am not familiar with the literature on Glivenko-Cantelli, but a quick google search led me to this counter-example. So it would seem like ergodic processes don't share the uniform convergence. I am familiar with other results like the strong invariance principle etc holding under some stronger conditions on rate of convergence and moments of functions. $\endgroup$ – Greenparker Aug 8 '18 at 16:06
  • $\begingroup$ Thanks for the clarification, Greenparker. I am curious to hear your thoughts on the following: It is advocated in Metropolis MCMC that the step size be chosen correspondingly to minimize the correlation length of the samples. It appears that this practice is to address objective 1 in the post above to make it comparable to standard Monte Carlo. But if your goal is the 2nd objective above, which is the histogram, what benefits would you have from minimizing the correlation length? is it for better exploration of the state space (since high correlation length means high accept rate?) $\endgroup$ – user1237300 Aug 8 '18 at 21:10
  • 1
    $\begingroup$ @user1237300 This sounds like a separate detailed question. If you post it as such, the community will be able to discuss it better. Also, clarify what you mean by "correlation length" $\endgroup$ – Greenparker Aug 8 '18 at 21:14
  • $\begingroup$ I see. I will make a new question. Thanks Greenparker. Btw, any accessible reference to what you discussed in your answer? $\endgroup$ – user1237300 Aug 8 '18 at 21:48

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.