Expected value of Bernoulli quadratic forms

Question

Let $\mathbf{Y}\in\mathbb{R}^{n\times n}$ be a symmetric matrix. Let $\mathbf{x}\in\mathbb{R}^n$ be random vectors with entries i.i.d. $\pm 1$ with equal probability. I'm interested in a lower bound on

$\mathbb{E}[|\mathbf{x}^T\mathbf{Y}\mathbf{x}|]$

where the expectation is w.r.t. $\mathbf{x}$. An obvious lower bound based on Jenson's inequality is $|tr(\mathbf{Y})|$. I was wondering if anything sharper is known.

To be more clear about the kind of problem I care about assume $\mathbf{Y}=\mathbf{y}\mathbf{y}^T-\mathbf{z}\mathbf{z}^T$ then $|tr(\mathbf{Y})|=\big|||\mathbf{y}||_{\ell_2}^2-||\mathbf{z}||_{\ell_2}^2\big|$. However, I would like to prove something like

$\mathbb{E}[|\mathbf{x}^T\mathbf{Y}\mathbf{x}|]\ge c ||\mathbf{y}-\mathbf{z}||_{\ell_2}||\mathbf{y}+\mathbf{z}||_{\ell_2}$

with $c$ a fixed numerical constant.

Answer 1

If diagonal entries of $Y$ are zero then there is an open question of Pełczyński which asks whether we have the lower bound
$$ \mathbb{E} |x^{T}Yx| \geq \frac{1}{2} \sqrt{\mathbb{E} |x^{T}Yx|^{2}} ? $$

K. Oleszkiewicz writes in his slides (see slides 170) https://simons.berkeley.edu/sites/default/files/docs/481/oleszkiewiczslides.pdf

Known to be true for n ≤ 6. In general, unknown ...

Remark: One can weaken the assumption "diagonal entries of $Y$ are zero" to "$\mathrm{Tr}(Y)=0$" but then the conclusion would be $$ \mathbb{E} |x^{T}Yx| \geq \frac{1}{2} \sqrt{\mathbb{E} |x^{T}Y^{0}x|^{2}}? $$ where $Y^{0}$ is obtained from $Y$ by removing diagonal entries. Indeed, this follows from the identity $x^{T}Yx=x^{T}Y^{0}x$.

Answer 2

Since $Y$ is diagonal you get $M$ such that $M^TM=Y$ so $x^TYx=|Mx|^2$

let's say $X_1$ is centered

then $$E(X^T Y X)=\sum_{i=1}^n\text{Var}(\sum_{j=1}^n M_{ij}X_j)$$

then since $X_j$ are independent you get : $$\text{Var}(\sum_{j=1}^n M_{ij}X_j)=\sum_{j=1} M_{ij}^2\text{Var}(X_j)$$ because they have same law $$\text{Var}(\sum_{j=1}^n M_{ij}X_j)=\text{Var}(X_1)\sum_{j=1} M_{ij}^2$$ now you sum over $i$ and you get : $$E(X^T Y X)=\text{Var}(X_1)\bf{1}^T Y \bf{1}$$ where $\bf{1}$ is the vector full of ones

Answer 3

The expectation can be computed in closed form, and I think that without further assumptions on entries of the matrix $Y$, the Jensen bound is sharp according to following calculation: $\begin{align}\mathbb{E}\left[\boldsymbol{X^{t}YX}\right] & =\mathbb{E}\left[\sum_{\substack{1\le i,j\le n} }X_{i}X_{j}Y_{ij}\right]\\ & =\sum_{m=-n}^{n}\mathbb{E}\left[\sum_{1\le i,j\le n}X_{i}X_{j}Y_{ij}\left|\sum_{i=1}^{n}X_{i}=m\right.\right]\mathbb{P}\left(\sum_{i=1}^{n}X_{i}=m\right)\\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\mathbb{E}\left[X_{i}X_{j}\left|\sum_{i=1}^{n}X_{i}=m\right.\right]\mathbb{P}\left(\sum_{i=1}^{n}X_{i}=m\right)\\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\left\{ x_{i}x_{j}\mathbb{P}\left(X_{i}=x_{i},X_{j}=x_{j}\left|\sum_{i=1}^{n}X_{i}=m\right.\right)\right\} \mathbb{P}\left(\sum_{i=1}^{n}X_{i}=m\right)\\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\left\{ \sum_{x_{i},x_{j}\in\{\pm1\}}x_{i}x_{j}\mathbb{P}\left(\left.\sum_{i=1}^{n}X_{i}=m\right|X_{i}=x_{i},X_{j}=x_{j}\right)\mathbb{P}\left(X_{i}=x_{i},X_{j}=x_{j}\right)\right\} \\ & \text{The probability }\mathbb{P}\left(X_{i}=x_{i},X_{j}=x_{j}\right)=\left(\frac{1}{2}\right)^{x_{i}+x_{j}}\left(\frac{1}{2}\right)^{2-x_{i}-x_{j}}=\frac{1}{4},\forall x_{i},x_{j}\in\{\pm1\}\\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\frac{1}{4}\left\{ \sum_{x_{i},x_{j}\in\{\pm1\}}x_{i}x_{j}\mathbb{P}\left(\left.\sum_{i=1}^{n}X_{i}=m\right|X_{i}=x_{i},X_{j}=x_{j}\right)\right\} \\ & \text{The probability }\mathbb{P}\left(\left.\sum_{i=1}^{n}X_{i}=m\right|X_{i}=x_{i},X_{j}=x_{j}\right)=\begin{cases} m\neq\pm n,\pm(n-2) & \begin{cases} \frac{\left(\begin{array}{c} n-2\\ \frac{n-2-m}{2} \end{array}\right)\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}+m}\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}}}{1/4} & n-m\,even\\ 0 & n-m\,odd \end{cases}\\ m=\pm n & \left(\frac{1}{2}\right)^{n}I_{(x_{i}=x_{j}=1)}\text{ or }\left(\frac{1}{2}\right)^{n}I_{(x_{i}=x_{j}=-1)}\\ m=\pm(n-2) & \left(\frac{1}{2}\right)^{n}I_{(x_{i}=1,x_{j}=-1)}\text{ or }\left(\frac{1}{2}\right)^{n}I_{(x_{i}=-1,x_{j}=1)} \end{cases}\,\text{treated as a 1-d random walk.}\\ & \text{Following simplification assumes }m\neq\pm n,\pm(n-2)\\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\frac{1}{4}\left\{ \sum_{x_{i},x_{j}\in\{\pm1\}}x_{i}x_{j}\left(\frac{1+(-1)^{n-m}}{2}\right)\cdot\frac{\left(\begin{array}{c} n-2\\ \frac{n-2-m}{2} \end{array}\right)\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}+m}\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}}}{1/4}\right\} \\ & =\sum_{m=-n}^{n}\sum_{1\le i,j\le n}Y_{ij}\left\{ \sum_{x_{i},x_{j}\in\{\pm1\}}x_{i}x_{j}\left(\frac{1+(-1)^{n-m}}{2}\right)\cdot\left(\begin{array}{c} n-2\\ \frac{n-2-m}{2} \end{array}\right)\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}+m}\left(\frac{1}{2}\right)^{\frac{n-2-m}{2}}\right\} \end{align} $ If $Y=I_n$ then the lower bound is literally reached. If you want a Hanson-Wright type concentration bound, then it can be improved since Bernoulli random vectors are sub-gaussian:

Hanson-Wright inequality.

Let $X=(X_{1},\cdots X_{n})\in\mathbb{R}^{n}$ be a random vector with independent components $X_{i}$ such that

(i)$EX_{i}=0$

(ii) $\left\Vert X_{i}\right\Vert _{\psi_{2}}= sup_{p\geq1}p^{-\frac{1}{2}}\left[E\left|X\right|^{p}\right]^{\frac{1}{p}}\leq K$ i.e. its components have uniform sub-gaussian norm.

Then for arbitrary n\times n constant matrix A and $\forall t\geq 0$ we can assert that

$Pr\left\{ \left|X^{t}AX-EX^{t}AX\right|>t\right\} \leq2exp\left(-c\cdot min\left(\frac{t^{2}}{K^{4}\left\Vert A\right\Vert _{HS}^{2}},\frac{t}{K^{2}\left\Vert A\right\Vert }\right)\right)$ for some constant $c>0$.

where $\left\Vert A\right\Vert =max_{x\neq0}\frac{\left\Vert Ax\right\Vert _{L^{2}}}{\left\Vert x\right\Vert _{L^{2}}}$ and $\left\Vert A\right\Vert _{HS}=\sqrt{\sum_{i,j}\left|a_{ij}\right|^{2}}$.

It is readily verifed that a Bernoulli random vector satisfies (i)(ii) with $K=2$. Therefore we can assert that

$$Pr\left\{ \left|X^{t}YX-EX^{t}YX\right|>t\right\} \leq2exp\left(-c\cdot min\left(\frac{t^{2}}{K^{4}\left\Vert Y\right\Vert _{HS}^{2}},\frac{t}{K^{2}\left\Vert Y\right\Vert }\right)\right)$$

where $Y=yy^{t}-zz^{t}$ is symmetric as stated in the OP.

Answer 4

If Y is any diagonal matrix then the lower bound is achieved so the lower bound is tight for diagonal matrices. There can't be any sharper bound defined in terms of eigen values since there exists a diagonal matrix with those eigenvalues.

Update after edit to the question:

If a bound of the type $c||y-z|| ||y + z||$ has to be better than the trace bound then it has to match the trace bound in the special case where $y,z$ are $[0, 1, \ldots ]$ and $[1, 0, \ldots]$ orthogonal basis vectors. In this case $Y$ would again be a diagonal matrix with only two non-zero entries. Moreover, $E[|x^TYx|]$ would be $E[|(x_1)^2 - (x_2)^2|] = 0$ and $||y-z|| = ||y + z|| = \sqrt{2}$. Which means $0 \ge c \times 2 \implies c = 0$. So this form of bound is not going to lead anywhere.

Thinking more geometrically what you need are constraints on the angle between $y,z$ and you need to quantify how much energy a hyperplane spanned by $y,z$ is allowed to receive. So the $c$ in your hypothesized bound can't be a constant but has to depend on $y,z$