Skip to main content
1 of 2

Maximum of the norm of k-averages of n iid random d-dimensional 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?