1
$\begingroup$

I have found a lot of references on quadratic forms of Normal Random Variables but was not able to find any reference on quadratic forms of {+1,-1} random variables. Formally, let $X_i$ be independent random variables taking values $1,-1$ with equal probability. A quadratic form on these is defined by

$$A = \sum a_{ij}X_i.X_j$$

What bounds can we get on moments of such forms or what can be said about their tails ? References would be great.

$\endgroup$
2
$\begingroup$

You may take a look at Proposition 8.13 in A Mathematical Introduction to Compressive Sensing by Simon Foucart and Holger Rauhut.

Let $\mathbf x$ be a Rademacher vector. For a self-adjoint matrix $\mathbf M$ with zero diagonal we consider the homogeneous Rademacher chaos

$$X := \mathbf x^*\mathbf M \mathbf x = \sum_{i\neq j} x_iM_{ij}x_j.$$

They showed Hanson-Wright type tail bound with specific constants.

$$\Pr[|x| \geq t] \leq 2 \exp\left(-\min\left[ \frac{3t^2}{128||\mathbf M||_F^2}, \frac{t}{32||\mathbf M||_{2\to 2}} \right]\right)$$

If your matrix $\mathbf M$ is not diagonal-free, you may take a look at the paper by Mark Rudelson and Roman Vershynin on how to handle the diagonal entries separately.

$\endgroup$
1
$\begingroup$

See the paper A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables by D. L. Hanson and F. T. Wright, The Annals of Mathematical Statistics Vol. 42, No. 3 (Jun., 1971), pp. 1079-1083.

$\endgroup$
  • $\begingroup$ The paper has bounds for variables that are sub-gaussian. My case is much simpler and probably tighter bounds can be expected. $\endgroup$ – user1189053 Jul 14 '13 at 4:46

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.