# Impossibility result for sub-gaussian random variables

Apparently the following statement is true:

If $$X$$ is an isotropic random vector, with finite support set $$T \subset \mathbf{R}^n$$, then if $$\|X\|_{\mathrm{s.g.}} = O(1)$$, then $$|T| \geq e^{cn}$$.

Note that $$\|\cdot\|_{\mathrm{s.g.}}$$ is the sub-gaussian norm of a random vector. It can be defined $$\|X\|_{\mathrm{s.g.}} = \sup_{u \in S^{n-1}} \|\langle X,u \rangle \|$$, with $$\|\cdot\|$$ denote the sub-gaussian norm of a scalar random variable (i.e., if $$Y$$ is a scalar random variable, then $$\|Y\| = \inf \{ t > 0 : \mathbf{E} \exp(Y^2/t^2) \leq 2\}$$).

Questions: How does one start to prove a statement like this? I don't understand really what the $$O(1)$$ statement really means in this setting. (I do know the definition of Landau's big-O notation, but I just don't get why it is relevant here. Are we interested in the scaling behavior with respect to $$n$$?)

Edit (3/19/24): A more precise version of this question. Let us drop the subscript s.g. and without comment use that $$\|\cdot\|$$ denotes the sub-Gaussian norm of a scalar or vector-valued random variable.

The question is asking the following. Show the following is true: for every $$K > 0$$, there exists a constant $$c = c(K) > 0$$ such that: for any integer $$n \geq 1$$, for every finitely supported random variable $$X \in \mathbf{R}^n$$ and $$\mathbf{E} X \otimes X = I_n$$, and $$\|X\| = K$$, the support of $$X$$ is at least of cardinality $$e^{cn}$$.

• I'm having trouble even making sense of the statement to prove. In what sense is "$O(1)$" meant, given that $X$ has finite support? In what sense is $X$ "isotropic" (which ordinarily means invariant under all rotations, which implies non-finite support unless $X$ is identically $0$)? What does "$c$" refer to in the conclusion? Given that $T$ is finite, then evidently "$|T|$" is the cardinality of $T$, but then isn't it trivial that there exists some $c$ for which $|T|\gt e^{cn}$? (Any $c\lt 0$ obviously works.)
– whuber
Commented Feb 19, 2018 at 15:39
• @whuber Thank you for taking a look at this. I think (but am not entirely sure) what this means is that $\|X\|_{s.g.}$ should be bounded above by a constant which is independent of $n$. $X$ being isotropic means that $\mathbf{E}XX^T = I_n$. I don't think the statement is trivial as you say, but if you still think it is, perhaps you can explain why. Commented Feb 20, 2018 at 0:06
• I want to point out that the question above---makes sense. Yes, it perhaps requires more care to state, but I think the intent of the question was quite clear as originally stated. I have updated it to include a more precise statement. Commented Mar 19 at 22:33

Note that for any sequence of sub-Gaussian random variables $$Y_1, \dots, Y_N$$, we have, for an absolute constant $$c > 0$$, that $$\mathbf{E}[\max_{n \leq N} |Y_n|^2] \leq c K^2 \log N,$$ where $$K = \max_{n \leq N} \|Y_n\|$$. (For instance, one may prove this using the fact that the square of a sub-Gaussian random variable is sub-Exponential). Thus, using that $$X$$ is finitely supported, $$n = \mathbf{E} \|X\|_2^2 \leq \mathbf{E}\max_{t \in T} |X_{\tilde t}|^2 \leq c \|X\|^2 \log |T|,$$ where for any $$t \in T =\mathrm{supp}(X)$$ we took $$\tilde t = t/\|t\|_2$$, so that $$\tilde X_t$$. The first equality holds by considering $$t = X$$, so that $$X_{\tilde X} = \|X\|_2$$. Inverting the bound, $$|T| \geq e^{C n},$$ where $$C = c'/\|X\|^2$$, as required.