# Curse of Dimensionality - A Formalization

Let $$\mathbf{X}$$ be a vector in $$\mathbb{R}^p$$, and assume that all its components are independent standard normal random variables (i.e. $$\mathbf{X}_j \sim \mathcal{N} (0, 1)$$ for $$j = 1, \cdots, p$$). Show that as $$p \rightarrow \infty$$, we have $$P(||\mathbf{X}||^2 \leq \epsilon) \rightarrow 0, \,\, \forall \epsilon > 0$$.

Apologies if the title is incorrect, but I interpreted this as a "proof" of the curse of dimensionality. I've attempted to prove this through Chebyshev's inequality, and my intuition says this should work given what I've seen other proofs for limiting distributions involve, but I'm not sure how to go about formalizing this.

It is not clear to me how the limit result in your question constitutes a formalisation of the concept of the "curse of dimensionality". Nevertheless, the limit result you are seeking to prove is fairly simple. Since you have stiuplated that $$X_1,...X_p \sim \text{IID } \mathcal{N} (0,1)$$ you have the explicit distribution:

$$||\mathbf{X}_p||^2 = \sum_{i=1}^p X_i^2 \sim \text{ChiSq}(\text{df} = p).$$

It follows that $$\mathbb{E}(||\mathbf{X}_p||^2) = p$$ and $$\mathbb{V}(||\mathbf{X}_p||^2) = 2p$$. The classical central limit theorem gives us the asymptotic equivalence:

\begin{aligned} \mathbb{P}(||\mathbf{X}_p||^2 \leq \epsilon) &= \mathbb{P} \bigg( \frac{||\mathbf{X}_p||^2 - p}{\sqrt{2p}} \leqslant \frac{\epsilon - p}{\sqrt{2p}} \bigg) \\[6pt] &\simeq \Phi \bigg( \frac{\epsilon - p}{\sqrt{2p}} \bigg). \\[6pt] \end{aligned}

Taking limits then gives the result:

$$\lim_{p \rightarrow \infty} \mathbb{P}(||\mathbf{X}_p||^2 \leq \epsilon) = \lim_{p \rightarrow \infty} \Phi \bigg( \frac{\epsilon - p}{\sqrt{2p}} \bigg) = \lim_{z \rightarrow \infty} \Phi( -z ) = 0.$$

There are other ways to prove this if you prefer, but the fact that you have a stipulated distributional form makes it easy to apply the central limit theorem here. Now, if you want to assert that this limit constitutes "proof" of the concept of the "curse of dimensionality" then you are going to need some further argument to back that up. Moreover, the fact that you have assumed a full joint distribution for your random vector makes your result very narrow, so even if you can give some argument linking this to the "curse of dimensionality", this is only going to apply to a very narrow class of cases (which is not very convincing, since the "curse of dimensionality" is a much more general phenomena).

• Right, I wasn't sure either, hence the quotations. I think this shows that with increasing dimension $p$, the support of the distribution of $\mathbf{X}$ lies outside any fixed ball, which is how I saw the connection to the curse of dimensionality. – rw435 Dec 17 '19 at 1:53
• The support is always the whole space, and that doesn't reduce at all. – Ben Dec 17 '19 at 1:55