# Lower bound of the expectation of the product of inner products of random vectors

I encountered the following value in my research:

Let $$n,m$$ be some integer. Suppose $$\alpha_1,\dots,\alpha_m$$ are unit vectors in $$\mathbb{R}^n$$. Denote $$L = \mathop{\mathrm{E}}_x[ \prod_{1\leq j\leq m} \langle \alpha_j,x \rangle^2],$$ where $$x \in \mathbb{R}^n$$ is a random vector whose $$\ell$$th component is i.i.d. uniformly over $$\{-1,1\}$$.

My observation is that if $$m=n$$, $$L$$ may be $$0$$. For instance, let $$m=n=2$$, $$\alpha_1=\frac{1}{\sqrt{2}}(1\ 1)$$ and $$\alpha_2=\frac{1}{\sqrt{2}}(1\ {-1})$$. However, if, say, $$m=o(n)$$ or even $$n/2$$, then $$L$$ is seemingly lower bounded by $$\Omega(1)$$. How can I lower bound $$L$$ for those small $$m$$ (relative to $$n$$)?

For small and concrete $$m$$, I can manually lower bound $$L$$ by first expand the RHS and then apply the random subsum principle (namely, $$\mathrm{E}_x[x_{\ell_1}x_{\ell_2} \dots x_{\ell_c}]=0$$, where $$x_{\ell_j}$$ denotes the $$\ell$$th component of $$x$$). But I am not sure how to generalize this approach to arbitrary $$m$$.

Any hint or reference will be greatly appreciated (let alone an answer).

For those who are curious about the background: I am working on quantum query complexity, and I am trying to use the polynomial method to solve some certain problems. If you are interested but not familiar with these terms, refer to [BdW02].

• I’m missing something here. If you take your $\alpha_1$ and $\alpha_2$, why is the expectation zero? It seems that you’re taking a product of non-negative numbers, and the product is only zero if $x$ is perpendicular to one of the $\alpha$’s, so the product is almost surely positive, and the expectation is positive. – Anthony Quas Jun 8 '19 at 3:53
• @AnthonyQuas Note how we determine the r.v. $x$. It will always perpendicular to either $\alpha_1$ or $alpha_2$. – Lwins Jun 8 '19 at 6:06
• Sorry. I had read it as taking values in $[-1,1]$, not ${-1,1}$. – Anthony Quas Jun 8 '19 at 6:15
• @AnthonyQuas Well, I once wanted to delete this question when Iosif pointed out the answer because that made me feel myself so stupid. :P – Lwins Jun 8 '19 at 6:18

The exact lower bound on $$L$$ is $$0$$ for any $$n\ge2$$ and $$m\ge2$$. Indeed, for $$j=1,\dots, n$$, let $$a_j:=\alpha_j$$ be any unit vectors in $$\mathbb R^n$$ such that $$a_1=\frac1{\sqrt{2}}(1,1,0,\dots,0)$$ and $$a_2=\frac1{\sqrt{2}}(1,-1,0,\dots,0)$$. Then $$\prod_{1\leq j\leq m} \langle \alpha_j,x \rangle^2=0$$ and hence $$L=0$$.