11
$\begingroup$

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}$?

$\endgroup$
3
  • $\begingroup$ $\sum_i w_i g_i$ is normal distributed with variance $\sum_i |w_i|=n$. Hence $n\mathbb{E} |g|$ with $g$ the standard normal distribution is an upper bound. Do I understand something wrong? $\endgroup$
    – user35593
    Mar 18, 2015 at 13:29
  • $\begingroup$ I am sorry, the minimum has to be inside the integral, the way it stands it is silly. Corrected. $\endgroup$
    – TOM
    Mar 18, 2015 at 14:21
  • $\begingroup$ Can you say what you are looking for, in particular should the answer be $o(1)$ and if so how good a bound would you like? (If this is uncertain, did you try simulating it at all to guess what the asmyptotics would be? Probably requires some nontrivial code to solve the minimization problem.) Finally, maybe a totally different approach is to argue that the empirical distribution of the $\{g_i\}$ is approximately normal, which together with a bounded maximum $g_i$ might imply something good. $\endgroup$
    – usul
    Mar 29, 2015 at 20:28

2 Answers 2

4
+25
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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:

code with histogram of signed sums for n=10000

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

$\endgroup$
2
  • $\begingroup$ @Bjorn, I agree that $g_1-g_2 \sim N(0,2)$, and $g_{(2)}-g_{(1)}$ has a folded normal distribution. (Subscripts with parentheses indicate the order statistics.) But I am looking at $|g|_{(2)}-|g|_{(1)}$, which is distributed as $2\exp(-z^2/4)\,\text{erfc}(z/2)\,/\sqrt{\pi}$ for positive $z$. $\endgroup$
    – user44143
    Mar 29, 2015 at 1:29
  • $\begingroup$ Ah, yes. Interesting idea to use Thue-Morse here. $\endgroup$ Mar 29, 2015 at 1:31

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.