I'm given two i.i.d. standard normal vectors $x, y \sim \mathcal{N}(0, I_n)$, and vectors $a \in \mathbb{S}^{n-1}$, the unit sphere in $n$ dimensions. Additionally, given a set $S \subseteq [n]$, I want to prove (or disprove):

$$ \mathbb{E}\left( \bigg| \sup_{a \in \mathbb{S}^{n-1}} \sum_{i = 1}^n \mathbf{1}\{i \in S\} a_i^2 x_iy_i \bigg| \right) \leq \mathbb{E}\left( \bigg| \sup_{a \in \mathbb{S}^{n-1}} \sum_{i = 1}^n a_i^2 x_iy_i \bigg| \right). $$

Are there any comparison inequalities or tools from probability that could potentially be useful here?


1 Answer 1


The rule you want is

$\mathbf{z}$ be any $n$-vector. The maximum value of $\lambda\cdot \mathbf{z}$ over all vectors $\lambda$ with non-negative components summing to unity is the maximum value of the components of $\mathbf{z}$.

Proof. This follows from the Hölder Inequality for $p=1, q=\infty.$ It has an elementary proof. Let $i$ be any index for which $z_i$ is largest. Then $$z_i - \lambda\cdot \mathbf{z} = (z_i - \lambda_1 z_1, z_i - \lambda_2 z_2, \ldots, z_i - \lambda_n z_n).$$ Since $z_i\ge z_j$ for all $j$ and $0\le \lambda_j\le 1$ for all $j$, each of the components on the right hand side is nonnegative. At least one will be zero when $\lambda_i=1,$ QED.

In the sequel, $\lambda$ will be the vector $(a_1^2, a_2^2, \ldots, a_n^2)$ where $\mathbf a \in \mathbb{S}^{n-1}.$


Let's simplify the expressions. Given vectors $\mathbf{x}$ and $\mathbf y,$ write $$z_i = x_i y_i.$$ Let $P(\mathbf z)$ be the set of coordinates $i$ for which $z_i \gt 0.$ The expression $|\sum_{i=1}^n a_i^2 x_i y_i| = |\sum_{i=1}^n a_i^2 z_i|$ is maximized by setting $a_i=\pm 1$ for some $i\in P(\mathbf z)$ at which $z_i$ is largest (and all $a_j=0$ for $j\ne i$). This yields

$$|\sup_{a\in\mathbb{S}^{n-1}} \sum_{i=1}^n a_i^2 x_i y_i| = |\max_{i\in P(\mathbf{z})} z_i| =\max_{i\in P(\mathbf{z})} z_i.\tag{1}$$

If $P(\mathbf z)$ is empty, this expression is maximized by setting $a_i=1$ for some $i\in[n]$ at which $-x_iy_i$ is smallest, producing

$$|\sup_{a\in\mathbb{S}^{n-1}} \sum_{i=1}^n a_i^2 x_i y_i| = \min_{i} (-z_i) .\tag{2}$$

Suppose $S$ is a proper subset of $[n]$ (if not, the equality of the two sides is trivially true) and is nonempty (it's easy to see the inequality holds in this case). When $S\cap P(\mathbf z) \ne \emptyset,$

$$\sup_{a\in\mathbb{S}^{n-1}} \sum_{i=1}^n I\{i\in S\} a_i^2 x_i y_i = \sup_{a\in\mathbb{S}^{n-1}} \sum_{i\in S}^n a_i^2 z_i\tag{3}$$

is maximized by setting $a_i=\pm 1$ for an $i\in S\cap P(\mathbf z)$ for which $z_i$ is largest, and it tells us

$$|\sup_{a\in\mathbb{S}^{n-1}} \sum_{i\in S}^n a_i^2 z_i| = \max_{i\in S\cap P(\mathbf z)} z_i.\tag{4}$$

Otherwise, $z_i \lt 0$ for all $i\in S$ and $(3)$ is maximized by setting $a_i=0$ for some $i\in S$ (and $a_j=\pm 1$ for some $j\ne i$). In this case

$$|\sup_{a\in\mathbb{S}^{n-1}} \sum_{i\in S}^n a_i^2 z_i| = 0.\tag{5}$$

When $S \cap P(\mathbf Z)$ is nonempty, $(4)$ does not exceed $(1)$ because it is the maximum over a subset of the values in $(1)$. In all other cases $(4)$ does not exceed $(1)$ and $(5)$ does not exceed either $(1)$ or $(2).$ Thus, no matter what the values $\mathbf x$ and $\mathbf y$ may be, the left hand side of the inequality never exceeds the right hand side. The inequality is maintained upon taking expectations.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.