# Distribution of the maximum of the norm of k-averages of n i.i.d. d-dimensional random vectors

Suppose $X_1, ... X_n$ are i.i.d. random vectors in $d$-dimensional space (i.e., $R^d$) with continuous centrally symmetric density function $f(\cdot)$ (i.e., symmetric with respect to the origin). For concretenes's sake, assume $X_i$ is just a multivariate normal distribution with covariance matrix equal to the identity.

What is the expectation (as a function of $d$, $k$ and $n$) of the maximum value of $||X_{i_1}+...+X_{i_k}||^2$ where the maximum is taken over all possible $1 \leq i_{1} < i_{2} < \ldots < i_{k} \leq n$ and $||\cdot||$ denotes the Euclidean norm?

Are large deviation bounds known? In general, what is the relation between $f(\cdot)$ and the expectation of the maximum?

• Sounds like you want a 'maximal inequality'. Not exactly sure how to do what you are asking by I would start at Section 3 of stat.yale.edu/~pollard/Papers/Pollard89StatSci.pdf. – Robby McKilliam Jun 11 '12 at 23:12
• @RobbyMcKilliam It does not seem to me that the OP wants a maximal inequality and the paper you cited is about empirical process, could you explain a bit about your comment? – Henry.L Jun 6 '17 at 15:27

The problem can be solved if the distribution $f(\cdot)$ is in a Levy stable distribution family. In your concrete example, since the $d\dim$ normal distribution $N(\mu,I_d)$ is "additive", the exact distribution of the $k$-sum $X_{i_1}+\cdots+X_{i_k}$ is $N(k\mu,kI_d)$. The choice of these $k$ random variables $X_{i_1},\cdots,X_{i_k}$ does not affect the mean nor covariance since the $X_i$'s are i.i.d. So it suffices to derive the distribution of $\|Y\|^2$ for a $d$-dimensional $Y\sim N(k\mu,kI_d)$, and there are $\left(\begin{array}{c} n\\k\end{array}\right)$ possible combinations of one realization value of $\|Y\|^2$ if $Y=X_{i_1}+\cdots+X_{i_k}$ is the sum of an i.i.d. sample of size $k$ therefore the probability $Pr(max\|X_{i_1}+\cdots+X_{i_k}\|^2=y)$ will be $\left(\begin{array}{c} n\\k\end{array}\right)\cdot f_{\|Y\|^2}(y)\cdot F_{\|Y'\|^2}(y)$. The maximum is taken over all possible $1 \leq i_{1} < i_{2} < \ldots < i_{k} \leq n$, same below. The $Y'=\sum_{j\notin\{i_1,\cdots,i_k\} }X_j$ follows a similar derivation but $F$ is the c.d.f.
To calculate the latter $f_{\|Y\|^2}(y)$, we need to notice that $\frac{Y}{\sqrt{k}}\sim N_d(\sqrt{k}\mu,I_d)$, we can compute its $L^2$ norm $\frac{1}{k}\sum_iY^2_i=:\|\frac{Y}{\sqrt{k}}\|^2\sim\chi^2(d)$. Thus the p.d.f. $f_{\|Y\|^2}(y)=f_{\chi^2(d)}(ky)$
To draw a conclusion, $Pr(max\|X_{i_1}+\cdots+X_{i_k}\|^2=y)=\left(\begin{array}{c} n\\k\end{array}\right)\cdot f_{\chi^2(d)}(ky)\cdot F_{\chi^2(d)}((n-k)y)$ in case of $d\dim$ multivariate normal as you indicated in OP. For other families of $f(\cdot )$ closed under addition, we can proceed the same way, and the resulting density may not be of closed form if we do not know one under square transformation (in contrast that we know $\chi^2(d)$ in above.).