# Prove that a sub-Gaussian random vector over a finite set $S \subset\mathbb R^n$ implies that $|S|$ is exponentially large

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!

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.

• Very nice! Only I don't see how and why you would use Paley--Zygmund, instead of just writing $E(a\cdot X)^2\,1_{\|X\|>\sqrt n}\le E\|X\|^2\,1_{\|X\|>\sqrt n}\to0$ as $n\to\infty$, for any unit vector $a$. – Iosif Pinelis Mar 22 '19 at 14:26
• I wanted to compare 2nd with 4th moment. But yes there is a simpler argument along the lines you suggest, I will include it. – Guillaume Aubrun Mar 22 '19 at 14:34
• Do you define $\tilde{Y}:=\text{E}(YY^T)^{-\frac{1}{2}}Y?$ If yes, could you explain how to get that $\lVert \langle \tilde{Y},\theta \rangle \rVert_{\psi_2}\leq 2C$ for all unit vectors $\theta$ holds. – Hugo10T Aug 15 '20 at 12:56
• Yes $\tilde{Y} = T^{-1/2}(Y)$ for $T=\mathbf{E} [ YY^T]$. Now, observe that $\langle \tilde{Y}, \theta \rangle$ is the same as $\langle Y, T^{-1/2} \theta \rangle$ and therefore $\| \langle \tilde{Y}, \theta \rangle \|_{\psi_2} \leq C \|T^{-1/2} \theta \| \leq \sqrt{2}C$. – Guillaume Aubrun Aug 24 '20 at 8:15

This conjecture is false. Indeed, let, as in your example, $$X$$ be uniformly distributed on $$\{-1,1\}^n$$. Let $$Y$$ be a random vector uniformly distributed on the set $$S_Y:=\{\sqrt n\,e_1,-\sqrt n\,e_1,\dots,\sqrt n\,e_n,-\sqrt n\,e_n\},$$ where $$(e_1,\dots,e_n)$$ is the standard basis of $$\mathbb R^n$$. Then $$EYY^T=I_n=EXX^T$$. Also, $$\|Y\|=\sqrt n=\|X\|$$, where $$\|\cdot\|$$ is the Euclidean norm, so that $$Y$$ is sub-Gaussian in exactly the same sense as $$X$$ is. However, $$|S_Y|=2n=o(e^{an})$$ as $$n\to\infty$$ for any constant $$a>0$$.

• I think the OP means by subgaussian that all 1-dimensional marginals of $X$ have to be (uniformly) subgaussian – Guillaume Aubrun Mar 22 '19 at 12:52
• @GuillaumeAubrun : Where do you see any hint about or any mentioning of one-dimensional marginals? Rather to the contrary, in the description of the example in the OP only the constant norm of $X$ is mentioned. – Iosif Pinelis Mar 22 '19 at 13:11
• I've seen this terminology used by people working in high-dimensional probability/convex geometry – Guillaume Aubrun Mar 22 '19 at 13:29
• But why do you think that usage would apply here, especially given that in the description of the example in the OP only the constant norm of $X$ is mentioned? – Iosif Pinelis Mar 22 '19 at 13:33
• I am sorry that I didn't give the definition of $\|\cdot\|_{\psi_2}$ of a random vector. It has the same meaning as @Guillaume Aubrun said. I have added it in the question. – zbh2047 Mar 22 '19 at 13:48