Minimal expected absolute value of linear combinations of Gaussian random variables

Question

I am interested in the following question. Consider $n$ independent standard normal random variables $g_i$. Cosider a linear combination $w_1g_1+\cdots+w_ng_n$. Can one give a "decent" upper bound for \begin{equation} \mathbb{E}\min_{w_i \in \left\{-1,1\right\}}|w_1g_1+\cdots+w_ng_n| \text{?} \end{equation}

Basically, I am asking about the minimum expected absolute value of a family of correlated gaussian random variables.

If a good bound can be obtained, what about the same question for more general linear combinations, such as $w_1a_1g_1+\cdots+w_na_ng_n$ in term of $n$ and some norm of $a_i$, say $l_{2}$?

Answer 1

For any numbers $g_1,\dots,g_n$, we have $$ \min_{w_i=\pm 1} \left|\sum_i w_ig_i\right|\le \max_i |g_i|$$ since you can separate the $g_i$ into two piles whose sum of absolute values are about equally large (see @MattF.'s answer for a precise formulation). Then $$\mathbb E\max_{i=1}^n |g_i|=\int_0^\infty \Pr\left[\max_i |g_i|)\ge x\right] dx$$ $$=\int_0^\infty 1-\Pr\left[\max_i |g_i|\le x\right]dx=\int_0^\infty 1-\left(\Pr\left[|g_1|\le x\right]\right)^ndx$$ $$=\int_0^\infty 1-(\Phi(x)-\Phi(-x))^ndx,\qquad\Phi=\text{standard normal cdf}$$ $$=\int_0^\infty 1-(1-2\Phi(-x))^ndx.$$ I suppose one can say more at this point but I'll just note that Wolfram Alpha has some further info about such integrals. For $n=1$ it's $\int 2\Phi(-x))dx=\frac{2}{\sqrt{2\pi}}=\sqrt{2/\pi}$ as it should be, and for $n=2$ it is $$ \int_0^\infty 4\Phi(-x)-4\Phi(-x)^2\,dx=4 \left(\frac1{\sqrt{2\pi}} - \frac{\sqrt 2-1}{\sqrt{2\pi}}\right) = 4 \frac{2-\sqrt 2}{\sqrt{2\pi}} = 4\frac{\sqrt 2-1}{\sqrt\pi} $$ which is already better than @user35593's estimate.

Answer 2

Experimentally, a constant bound of $2/3$ should do, while the bounds above grow with n.

We can get a reasonable bound by using the Thue-Morse sequence to select $w_i$'s. So we start with a weight of $+1$ for the largest $|g|$, and then weight smaller $|g|$'s with the inverse of the signs so far.

\begin{equation} \mathbb{E}\min_{w_i \in \left\{-1,1\right\}}|w_1g_1+\cdots+w_ng_n| \ \le\ \mathbb{E}\left|\sum_{i=1}^n s_{n-i}\ |g|_{(i)}\right| \end{equation}

where $|g|_{(i)}$ is the $i^{th}$ element after sorting the $|g|$'s, and $s_i$ is the $i^{th}$ element of A106400.

E.g. if the $w$'s are 1.31, -0.25, 2.59, 0.68, -0.77, then this bound is |2.59 - 1.31 - 0.77 + 0.68 - 0.25|.

This gives an expectation of $(4-2\sqrt{2})/\sqrt{\pi}$ for $n=2$, using reasoning like Bjorn Kjos-Hanssen's.

Here is some Mathematica code for experimenting with 100 sets of $n$ random variables:

I got expectations for this bound around 0.18 with $n$ of 100,000 or 1,000,000.

$\\$

[Update: We can use the same notation to prove that the expectation in the question is less than $E[\max|g_i|]$. Let $v_n = 1$, let $v_{j-1} = -\text{sign}( \sum_{i=j}^n v_i |g|_{(i)} )$, and then indeed $\left|\sum v_i |g|_{(i)} \right| < \max |g(i)|$.]