# Variance of the maximum of linear combinations of iid normal random variables

Let $X_i$ for $i\in\{1,\dots,n\}$ be a set iid normally distributed random variables with mean $\mu$ and variance $\sigma^2$. Let $Y_j$ for $j\in\{1,\dots,2^n\}$ be a positive linear combination of the $X$'s, i.e. $$Y_j=\sum_{i=1}^n c_{ij}X_i$$ with $c_{ij}\geq 0$. I am interested in the properties of $$Z=\max_j{Y_j}.$$ In particular, is it possible to say anything about its mean and its variance? Does it help if we assume that $n\rightarrow \infty$?

• $n\to \infty$ is meaningless without a concomitant stipulation governing the behavior of the $c_{ij}$. – whuber Jan 26 '17 at 17:33
• Would it help if they are all bounded: $0 \leq c_{ij} \leq a$ with $a$ constant? – user_lambda Jan 26 '17 at 18:28
• Yes, a bound would help. But you still wouldn't be able to say anything very precise, because the maximum could range from $a(X_1+\cdots+X_n)$ down to $aX_1$. Their means and variances differ more and more as $n$ increases. – whuber Jan 26 '17 at 19:00

The variables $Y_j$ are Gaussian, so I would recommend looking at some results on the extrema of Gaussian random variables.
M. Talagrand has recently published an excellent book (1), (though way over my head after the second chapter) which has strong results on the supremum of Gaussian processes. I think his results can be applied to this discrete setting in a straightforward way (choose the index set to be $\mathcal{X} = \{1,\dots,2^n\}$). If I remember correctly, the basic result is that the expected value of the supremum grows as order $\sqrt{\log(\lvert \mathcal{X}\rvert)}$. This result is Theorem 2.4.1, but he goes on to describe high probability bounds on the supremum as well. A good overview of this topic is given by this summary. You'll need to have a bit more information about the $c_{ij}$ for this to be useful, since there is a leading constant which depends on the smallest covariances between the $Y_j$.
Another good reference that is probably more familiar is (2), which has a chapter on the order statistics of exchangeable normal variables (e.g. the $X_i$). Section 6.3 specifically discusses linear combinations of order statistics, which might be interesting.