Let $X$ be an isotropic random vector (i.e. $E[XX^T]=I\_n$) and $X$ takes value in a finite set $S \subset\mathbb R^n$. If $X$ is a sub-Gaussian random vector and the norm $\|X\|\_{\psi\_2}\le C$ where $C$ is a constant, it will imply that $S$ is expoentially large with dimension $n$.


Note that $X$ is said to be sub-Gaussian with norm $K$ iff the marginal distribution in any direction is a sub-Gaussian with norm less or equal than $K$.


For example, if $X$ is uniformly distributed in $\{-1,+1\}^n$, then $X$ is a sub-Gaussian random vector with constant norm but now $|S|=2^n$. (It can be proved)


How can I prove the proposition? I just have no idea to deal with the "exponential" proof. Thank you!



Prove that a sub-Gaussian random vector over a finite set $S \subset\mathbb R^n$ implies that $|S|$ is exponentially large
If $(Z\_i)\_{1 \leq i \leq N}$ are scalar random variables with $\|Z\_i\|\_{\Psi\_2} \leq C$, then $\mathbf{E} \max Z\_i \leq CC'\sqrt{\log N}$ by the usual union bound argument. 


Now let $X$ be an isotropic random vector in $\mathbf{R}^n$ such that $\|\langle X,\theta \rangle \|\_{\Psi\_2} \leq C $ for every unit vector $\theta$, and let $S$ be the support of $X$. Choose a number $A$ such that $S$ is contained in the ball of radius $A\sqrt{n}$. Since (denoting by $\|\cdot\|$ the Euclidean norm)
$$ ||X||^2 \leq \sup\_{x \in S} |\langle X,x\rangle|, $$
it follows from the aforementioned estimate that
$$ n = \mathbf{E} ||X||^2 \leq A \sqrt{n} CC'\sqrt{\log |S|}.$$
In particular, we get $|S| \geq \exp(c(A,C) n)$.


We are going to reduce to the situation where $A$ is bounded. To that end, 
take an isotropic subgaussian random vector $X$ with $||\langle X,\theta \rangle||\_{\Psi\_2} \leq C$. This implies in particular $\mathbf{E} \langle X,\theta \rangle^4 \leq 4C^2$ (possibly change $4$ into another number depending on which definition of $\|\cdot\|\_{\psi\_2}$ you use). Define a new random vector as $Y = X {\bf 1}\_{\{ ||X|| \leq 4C \sqrt{n}\} }$. The vector $Y$ is not exactly isotropic but satisfies $\frac 12 I\_n \leq \mathbf{E} YY^T \leq I\_n$. This is because (by Cauchy-Schwarz and Markov inequalities)
$$ \mathbf{E} \left[ \langle X,\theta \rangle^2 {\bf 1}\_{\{||X|| > 4C \sqrt{n}\}} \right] \leq \left( \mathbf{E} \left[ \langle X,\theta \rangle^4 \right] \cdot \mathbf{P}(||X||^2 > 16C^2n)\right)^{1/2} \leq \sqrt{\frac{4C^2}{16C^2}} = \frac{1}{2}$$


We are now going to apply the first part of the argument to a linear image $\tilde{Y}$ of $Y$ which is isotropic. The random vector $\tilde{Y}$ is supported in the ball of radius $A\sqrt{n}$ for $A=8C$, and satisfies $\|\langle \tilde{Y},\theta \rangle \|\_{\Psi\_2} \leq 2C$, so the support of $Y$ (which is contained into $S \cup \{0\}$) contains at least $\exp(c(8C,2C)n)$ points.


