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].

  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Jun 8 '19 at 3:53
  • $\begingroup$ @AnthonyQuas Note how we determine the r.v. $x$. It will always perpendicular to either $\alpha_1$ or $alpha_2$. $\endgroup$ – Lwins Jun 8 '19 at 6:06
  • $\begingroup$ Sorry. I had read it as taking values in $[-1,1]$, not ${-1,1}$. $\endgroup$ – Anthony Quas Jun 8 '19 at 6:15
  • $\begingroup$ @AnthonyQuas Well, I once wanted to delete this question when Iosif pointed out the answer because that made me feel myself so stupid. :P $\endgroup$ – 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$.


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.