# Understanding the Typical Set for Markov chain Monte Carlo sampling

I started reading "A Conceptual Introduction to Hamiltonian Monte Carlo" today, and I've gotten stuck on understanding Betancourt's explanation of what a "typical set" is.

If $q_1, q_2, \ldots, q_n$ are generated from, say, a Metropolis-Hastings algorithm targeting the density $\pi(q)$, we can take the sample average in order to approximate expectations: $$\frac{1}{n} \sum_{i=1}^n f(q_i) \approx \int f(q) \pi(q)dq.$$

I am often told that, because we cannot run the sampler for an infinite amount of time, it's desirable to obtain samples in area of high density $\pi(q)$. Betancourt, on the other hand, says I should focus on area of high mass $\pi(q)dq$, and to ignore the variability of $f$. This makes sense to me because the integral above is kind of like $\sum_i f(q_i)\pi(q_i)dq_i$, and the big "contributors" to this sum are $q_i$ that have big $\pi(q_i)dq_i$. Really they are $q_i$ that have big $f(q_i)\pi(q_i)dq_i$, but we're ignoring $f$ for now.

What doesn't make sense to me, is why $dq$ isn't uniform all over the sample space $Q$. My intuition stems from these 2-dimensional Riemann integrals where we make $dq$ very small, and they're all equal to each other no matter where $q$ is. When each $q_i$ is 2-d, we have $dq=d(2\pi r) = 2 \pi r dr$. But why are we taking the change in volume of the 2-sphere (circle) centered at $0$? Here was a question on our site asking for advice on how to reproduce one of the plots. However, I'm not confused about where these formulas come from, rather I am confused about why they are coming from the places they are.

• Nearly two years later: I thought of this post when I saw a very nice writeup by Andrew Gelman pop up on the Stan mailing list: discourse.mc-stan.org/t/… Aug 26, 2020 at 13:59

$\mathrm{d}q$ is uniform across the entire space and that's the problem! Unfortunately as we consider higher-dimensional spaces out intuition of uniform starts failing us and we end up in conceptual difficulties like this.

Yes, the volume of the neighborhood around any given point remains the same size as we increase the dimensionality of our space. But as we do so we also add many more points to the space, and hence many more points and corresponding neighborhoods. It's not that the volume around our chosen point is shrinking in any absolute sense, it's rather the the volume is shrinking relative to the volume of the rest of the space.

If we consider radial shells around any point we see that volume increases exponentially fast (the exponent being $N - 1$, or $2 - 1 = 1$ in your $2$-dimensional example) as we move further away from that point. The growth of volume away from a point is the same no matter which point we take!

The symmetry of this behavior is broken only when we consider the particular density representation of our probability distribution. The mode of the density identifies a special point in space around which the density is the largest. Then in order to understand how the typical set behaves we have to consider how volume behaves around this one, special point.

We don't alway take $r = 0$ -- it just happens that $r = 0$ is the mode of an independently identically distributed unit Gaussian that we usually use to demonstrate the phenomenon.