2
$\begingroup$

Suppose $X$ and $Y$ are independent sub-Gaussian random variables with 0 mean and $\sigma^2$ sub-Gaussian parameter. More specifically, $\mathbb E[\exp(a^T X)]\leq \exp\{\|a\|_2^2\sigma^2/2\}$ for all $a$, and the same holds for $Y$ as well.

I wish to upper bound the tail probability $$ \Pr\left[|X^T Y|>t\right] $$ using $\sigma^2$ and dimension $n$ (that is, both $X$ and $Y$ are $d$-dimensional random variables). How can I achieve this? $X^T Y$ does not seem to be either sub-Gaussian or sub-exponential.

$\endgroup$
3
+50
$\begingroup$

Though you are right that the product is in general not sub-Gaussian, but it is still subexponential.

Note that for a sub-Gaussian vector $X$ in $\mathbb{R}^n$ with parameter $\sigma^2$ and for $r<\sigma^2$, $$ \mathrm{E}\bigg[\exp\Big\{\frac{r||X||^2}2\Big\}\bigg] = \frac{1}{(2\pi r)^{n/2}}\int_{\mathrm{R}^n} \exp\Big\{-\frac{||a||^2}{2r}\Big\}\, \mathbb{E}[e^{a^T X}]da \\ \le \frac{1}{(2\pi r)^{n/2}}\int_{\mathrm{R}^n} \exp\Big\{-\frac{||a||^2}{2r} + \frac{||a^2||\sigma^2}{2}\Big\}da = \frac{1}{\big(2\pi (\sigma^2-r)\big)^{n/2}}. $$ Therefore, thanks to independence, for any $\lambda<1$, $$ \mathrm{E}\big[\exp\{\lambda X^T Y\}\big] \le \mathrm{E}\bigg[\exp\Big\{\frac{\lambda^2\sigma^2||X||^2}2\Big\}\bigg]\le\frac{1}{\big(2\pi \sigma^2(1-\lambda^2)\big)^{n/2}}. $$ Hence you can easily derive an exponential bound for $\mathrm{P}(X^TY>t)$.

$\endgroup$
  • $\begingroup$ You're definitely right! I obtained the same results (sub-exponentiality of $X^T Y$) by bounding $\mathbb E|X^T Y|^p$ and invoking the Bernstein condition. Anyway I accepted your answer and awarded the bounty. $\endgroup$ – Yining Wang Aug 25 '17 at 17:06
1
$\begingroup$

By Cauchy-Schwarz, the event $[ |X^TY|>t]$ is a subset of $[\| X\|>\sqrt t] \cup[\|Y\|>\sqrt t]$, so its probability is bounded above by $P(\| X\|>\sqrt t)+P(\| Y\|>\sqrt t)$, for which $O(\exp{-At})$ bounds can probably be derived, for some $\sigma$-dependent $A$.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Unfortunately, I think this upper bound is very loose because $\|X\|$ is far from 0 because $\mathbb E\|X\|_2^2>0$, and $X^T Y$ is known to concentrate to 0 because $\mathbb EX^T Y = 0$. In particular, in the $P(\|X\|>\sqrt{t})$ bound the $t$ can never be arbitrarily small. $\endgroup$ – Yining Wang Jul 8 '17 at 1:36
  • $\begingroup$ And also, this argument applies to dependent $X$ and $Y$: which is not good because we know that when $X$ and $Y$ are independent, $X^T Y$ should be much smaller and close to 0. $\endgroup$ – Yining Wang Jul 8 '17 at 1:37
0
$\begingroup$

Moment generating functions of subgaussian vector can often be bounded from above by the same moment generating function, with the subgaussian vector replaced by a standard normal. This is equivalent to zhoraster's answer.

Take $\sigma=1$ without loss of generality (otherwise, consider $X/\sigma$ and $Y/\sigma$ and scale back afterwards). Let $g,h$ be standard normal random vectors, independent of $X,Y$. Then by independence, \[ E[e^{uX^TY} | X ] = E[e^{u^2\|X\|^2/2} ] = E[e^{u X^\top g}]. \] Now by the law of total expectation, and a similar argument for $Y$, \[ E[e^{uX^TY}] \le E[ E[e^{u X^T g}| g] ] = E[E[ e^{u^2\|g\|^2/2} | g]] = E[e^{u g^Th}]. \] So the problem is reduced to bounding the moment generating function where both random vectors are standard normal.

$\endgroup$

Your Answer

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

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