Given: Fix $n, k \in \mathbb{N}$, we generate $n$ random vectors $X_i \in \mathbb{R}^k$ with $\|X_i\|_2 = 1$.
We want to compute: The expected max Euclidean inner product between a random vector and the sum of the random vectors, i.e., $$ \mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle. $$
What I have tried:
- When $n = 2$, $\langle X_1, X_1 + X_2 \rangle = \langle X_2, X_1 + X_2 \rangle = 1 + \langle X_1, X_2 \rangle$; $\mathbb E \langle X_1, X_2 \rangle = 0$ due to symmetry, and thus $\mathbb E \max_{i \in [n]} \langle X_i, \sum_{j \in [n]} X_j \rangle = 1$.
- When $n \geq 3$, it becomes unclear to me.
- Intuitively it might get larger as $n$ increases since we have more options, and would approach some limit, possibly related to $\| \sum_{j \in [n]} X_j \|$.
- Simulations (1,000,000 trials) with $n = 3$ and $k = 2$ gives $1.5319441791547532 \pm 0.7104635978561801$.
- Simulations (1,000,000 trials) with $n = 4$ and $k = 2$ gives $1.6632600316282025 \pm 0.9042611238131294$.
- Simulations (1,000,000 trials) with $n = 5$ and $k = 2$ gives $1.9472506556915035 \pm 0.9787530817053821$.
- Simulations (1,000,000 trials) with $n = 100$ and $k = 2$ gives $8.86393808099978 \pm 4.6286431725480295$.
- Simulations (1,000,000 trials) with $n = 100$ and $k = 3$ gives $9.083624932218164 \pm 3.8388222137766603$
- Simulations (1,000,000 trials) with $n = 10,000$ and $k = 2$ gives $88.64022827148438 \pm 46.3698844909668$.
- Simulations (1,000,000 trials) with $n = 10,000$ and $k = 3$ gives $92.19273147896439 \pm 38.86980525584397$.
- Simulations (1,000,000 trials) with $n = 1,000,000$ and $k = 2$ gives $886.809001225146 \pm 463.51510862527164$
- Simulations (1,000,000 trials) with $n = 1,000,000$ and $k = 3$ gives $921.3826932102985 \pm 388.68428531397456$
- Simulations (1,000,000 trials) with $n = 1,000,000$ and $k = 4$ gives $939.8279114022998 \pm 341.27201929744365$
- It looks like the order is near $\sqrt{n}$, and I consequently have a conjecture that it would be something close to $\sqrt{n}$.
- I saw something $0.886$ for $k = 2$, and I know $\sqrt{\pi} / 2 \approx 0.8862$; not sure it is related or not.
- Limit of the integral is the square root of pi over 2
- https://en.wikipedia.org/wiki/Gaussian_integral
- I also suspect that it is related to the sphere-cylinder ratio; see, e.g., Volume of Region in 5D Space
As @Sal pointed out, this is related to random walks (see, e.g., Expected Value of Random Walk), and seemingly $$ \mathbb E \| \sum_{j \in [n]} X_j \| = \sqrt{\dfrac{2n}{k}} \dfrac{\Gamma(\frac{k+1}{2})}{\Gamma(\frac{k}{2})}, $$$$ \mathbb E \| \sum_{j \in [n]} X_j \| \approx \sqrt{\dfrac{2n}{k}} \dfrac{\Gamma(\frac{k+1}{2})}{\Gamma(\frac{k}{2})}, $$ which is
- $\sqrt{n} \frac{\Gamma(1.5)}{\Gamma(1)} = \frac{\sqrt{\pi}}{2}\sqrt{n} \approx 0.886227 \sqrt{n}$ for $k = 2$ as I suspected,
- $\sqrt{\frac{8}{3\pi}} \sqrt{n} \approx 0.921318 \sqrt{n}$ for $k = 3$,
- $\frac{3}{4} \sqrt{\frac{\pi}2} \sqrt{n} \approx 0.939986 \sqrt{n}$ for $k = 4$, and
- indeed approaches $\sqrt{n}$ as $k \to \infty$.
However, this only gives us the asymptotic results as $n \to \infty$, while the cases for small $n$ are still unclear.