1
$\begingroup$

Is there a concentration inequality for quadratic forms of bounded random vectors $X \in [-1, 1]^n$ with zero mean and given covariance matrix $\Sigma \in \mathbb{R}^{n \times n}$ but otherwise unknown distribution, i.e. a bound on the tail probability $$ \Pr(|X^T \Sigma^{-1} X - n| \ge t) \le \ldots $$ Since for sub-Gaussian random vectors there is the Hanson-Wright inequality $$ \Pr(|X^T A X - \operatorname{E}[X^T A X]| > t) \le \ldots $$ for some matrix $A \in \mathbb{R}^{n \times n}$ and $E[X^T \Sigma^{-1} X] = n$, it seems like such a bound should be within reach for the stronger restriction of bounded random vectors, even if the variance of the quadratic form is not available.

Note that this is specifically a question regarding the concentration about the mean $n$, since else we have the straightforward bound $\Pr(X^T \Sigma^{-1} X \ge t) \le n/t$ from Markov's inequality.


Edit: Thanks to @felipeh's answer for pointing out that there need to be additional restrictions on the function to give a meaningful bound. It would be reasonable to ask for the $X_i$ to be some or all of continuous, unimodal, symmetric as helpful.

$\endgroup$
1
  • $\begingroup$ Your confusion is that if $X$ is sub-Gaussian with a norm which is independent of $n$, this is a very strong condition. However, if $X \in [-1, 1]^n$, then the sub-Gaussian norm can be on the order $\sqrt{n}$, and then such exponential tail inequalities are not possible! $\endgroup$
    – Drew Brady
    Commented Jun 18 at 17:45

1 Answer 1

0
$\begingroup$

Let $X$ be the random vector that is identically $0$ with probability $1/2$, and with probability $1/2$ is sampled uniformly from the boolean cube $\{-1,1\}^n$. The covariance is $\Sigma=\frac{1}{2} Id$, and $X^T\Sigma^{-1} X$ is either equal to $0$ or $2n$, each with probability $1/2$.

This example suggests that there is no nontrivial concentration inequality in this case.

$\endgroup$
2
  • $\begingroup$ (I take it you meant the boolean cube $\{-1, 1\}^n$.) That is a good example, there need to be additional quantifiers on the distribution. I will edit the question, apologies for that. $\endgroup$
    – user114668
    Commented Mar 18, 2019 at 16:30
  • $\begingroup$ Yes indeed, thanks for the correction. $\endgroup$
    – felipeh
    Commented Mar 18, 2019 at 16:45

You must log in to answer this question.