# How is typical set defined for general high-dimensional distributions?

I'm only aware of the definitions in Elements of Information Theory, which deal with iid and stationary ergodic processes. From there we can speak of the typical set of, e.g., a high-dimensional standard normal distribution. But I've seen people referring to the "typical set" of general high-dimensional distributions (such as in Betancourt’s introduction to Hamiltonian Monte Carlo). Is there any rigorous definition in such cases?

• Not only does that paper lack a definition, it makes an erroneous claim. The error is that the mode of a density does not necessarily persist under a "reparameterization" unless the types of reparameterizations are heavily restricted (e.g., must be affine transformations). The idea (as explained on pp 7-8), though, is to find a relatively small subset of the space to which one may truncate the distribution and still obtain accurate estimates of expectations. Since that depends on the random variable, this sense of "typical set" depends on the variable, too, making it rather a misnomer. – whuber May 19 at 15:25
• The author has answered some other questions about HMC on here, let’s see.... I’m also very interested in the answer. – innisfree May 21 at 6:44

I agree with @r8. We can see from e.g., stan or these notes that the weakly $$\epsilon$$-typical set is given by $$A_\epsilon = \{ x: \left|\ln \frac{p(x)}{\pi(x)} - H(p, \pi)\right| \le \epsilon \}$$ where $$\pi(x)$$ is a reference measure and $$H(p, \pi) = \int p(x) \ln \frac{p(x)}{\pi(x)} dx$$ Let me add that we may quickly demonstrate an inequality for the volume of the typical set. We begin by expressing the condition above as $$e^{H - \epsilon}\, \pi(x) \le p(x) \le e^{H + \epsilon}\, \pi(x)$$ We then build an inequality $$1 \ge \int_{A_\epsilon} p(x) dx \ge \int_{A_\epsilon} \pi(x) dx \, e^{H - \epsilon}$$ and thus $$\text{Volume of typical set} \equiv \int_{A_\epsilon} \pi(x) dx \le e^{-H + \epsilon}$$ Let me further add that in the context of inference from a prior to a posterior (which I why I chose the notation $$\pi$$ and $$p$$) we may write the condition for the typical set in terms of the likelihood function $$\mathcal{L(x)}$$, $$e^{H - \epsilon}\, \mathcal{Z} \le \mathcal{L(x)} \le e^{H + \epsilon}\, \mathcal{Z}$$ where $$\mathcal{Z}$$ is the Bayesian evidence (also known as the marginal likelihood), $$\mathcal{Z} \equiv \int \mathcal{L}(x) \pi(x) dx$$

• I think we can also make the lower bound, $(1-\epsilon) e^{-H - \epsilon}$ for the volume just like the case for discrete sequences, but the proof and details are slightly more complicated – innisfree May 22 at 8:01

My understanding is that the rigorous definition of the $$\delta$$-typical set of $$p$$, relative to the base measure $$p_0$$, is given by

$$S_\delta ( p; p_0 ) = \left\{ x : \left| \log \frac{p (x)}{p_0 (x)} - \mathbf{E}_{p(\tilde{x})} \left[ \log \frac{p (\tilde{x})}{p_0 (\tilde{x})} \right] \right| < \delta \right\}.$$

I cannot provide a reference for this, unfortunately.

Note that the inclusion of the base measure is often left implicit, which can lead to confusion, as without it, the typical set will generally not be reparametrisation-equivariant.

• I had in mind that the volume of the typical set is $\int_S p_0(x) dx \sim e^{-H}$, where $H$ is the expectation in the second term of the rhs of your expression. Is that right? Can we show it? – innisfree May 21 at 8:57
• @innisfree there is no `the' typical set (to my knowledge); there is always some implicit threshold $\delta$. in some circumstances, it should be possible to estimate the volume of $S_\delta$ (see e.g. projecteuclid.org/euclid.aop/1312555807) but this will depend on various details / assumptions on $p_0, p$. – πr8 May 21 at 9:00