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 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
    Mar 18, 2019 at 16:30
  • $\begingroup$ Yes indeed, thanks for the correction. $\endgroup$
    – felipeh
    Mar 18, 2019 at 16:45

Your Answer

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