Demartines theorem (page 3) explain why norm of a random vector increases with dimension, whereas its variance remains constant:

Let $X \in \mathbb{R}^d$ be a random vector with i.i.d. components: $X_i \sim \mathcal{F}$. Then, $$ \text{E} \left[ \|X\|_2 \right] = \sqrt{ad-b} + O \left( \frac{1}{d} \right) $$ and $$ \text{Var} \left( \| X \|_2 \right) = b + O \left( \frac{1}{\sqrt{d}} \right) $$ where $a$ and $b$ are constants that do not depend on the dimension.

The theorem proves that the expectation of the euclidean norm of random vectors increases as the square root of the dimension $d$, whereas its variance is constant and independent of the dimension. When the dimension is large, the variance of the norm is very small compared with its expected value.

My questions:

  1. What does $O$ stands for?
  2. Why does norm increases with the square root of dimension? How can we see that?
  3. Why is variance constant? How can we see that?

migrated from stats.stackexchange.com Jul 1 '14 at 18:27

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

  • 2
    $\begingroup$ This is a minor variant of the Central Limit Theorem, which asserts the standardized version of $||X||_2^2$ is asymptotically Normal. It requires that $X$ have finite variance. $\endgroup$ – whuber Jul 1 '14 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.