Minimal expected absolute value of linear combinations of Gaussian random variables 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}$? 
 A: 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.
A: 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)|$.]
