0
$\begingroup$

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}$.

$\endgroup$
3
  • $\begingroup$ 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.) $\endgroup$
    – whuber
    Commented Feb 19, 2018 at 15:39
  • $\begingroup$ @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. $\endgroup$
    – Drew Brady
    Commented Feb 20, 2018 at 0:06
  • $\begingroup$ 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. $\endgroup$
    – Drew Brady
    Commented Mar 19 at 22:33

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.