# Sums of uniformly random vectors from the $n$-dimensional unit ball

I'm interested in some instances of the following problem.

Let $n \geq 2$, and suppose we draw $k \geq 2$ vectors $v_1, \dots, v_k$ uniformly at random from the $n$-dimensional ball of radius $1$, $B_n(1)$. Consider the vector $w = v_1 + \dots + v_k$. What is the probability $p(n,k,d)$ that this vector $w$ has norm at most $d$?

For $n = 2$ and $k = 2$, the answer can be obtained by computing the area of the intersection of two circles, and relating it to the area of the whole circle. Similarly, for $n = 3$ and $k = 2$ some results are known to compute the probability exactly. However, I'm mostly interested in larger $n$ and, if possible, slightly varying $k = 2, 3, \dots$ and $d = 1 - \epsilon$ for small $\epsilon > 0$.

My main questions are: Is this general problem known in literature? Does it have a specific name? What is known about higher-dimensional cases?

For $k = 2$, I already do have some reasonable lower and upper bounds on $p(n,k,d)$ for large $n$ which are "only" a polynomial factor (in $n$) apart, and the asymptotic behavior seems pretty clear. But already for $k = 3$, doing anything analytically seems very hard, even when $d = 1$. Any references or help in approaching this problem would be appreciated.

Edit: To clarify, I am mostly interested in asymptotics for reasonably large $n$, while $k$ remains small.

-
What is unsatisfactory about the Central Limit Theorem? –  Douglas Zare May 15 '13 at 22:04
To clarify: $||v_i||\leq 1$ right? not $||v_i||=1$? –  i707107 May 15 '13 at 22:40
@i707107: Yes, $\|v_i\| \leq 1$. For large $n$, one usually has $\|v_i\| \approx 1$ though, so if you can say something about the $\|v_i\| = 1$-case, that may help too. –  TMM May 15 '13 at 23:02
@DouglasZare: The values of $k$ I am interested in are too small for the CLT. I am thinking of $k = 3$ or maybe $k = 4$, while $n$ is "pretty big" (say $n = 100$). –  TMM May 15 '13 at 23:08
Ok, that explains why you can't use the CLT in one direction. There may still be some applications, though. See Stam, 1982. "Limit Theorems for Uniform Distributions on Spheres in High-Dimensional Euclidean Spaces." J. Applied Probability 19, 221-228. –  Douglas Zare May 16 '13 at 0:24

This is a concentration of measure problem on the sphere for fixed $k$ and large $n$. The probability that $|\left< v_1, v_j \right>| \leq \epsilon$ for each fixed $j$ is larger than $1-2e^{-\epsilon^2 n/2}$. So the probability it holds for all $j$ is at least $1-2k e^{-\epsilon^2 n/2}$. The probability that it holds for all pairs of $i$ and $j$ $|\left< v_i, v_j \right>| \leq \epsilon$ is at least $1-2k^2 e^{-\epsilon^2 n/2}$. For any $k$, we can pick $\epsilon$ very small so that this condition implies that $v_1+...+v_k$ has norm almost $\sqrt{k}$ with very high probability if $n$ is large enough.
To nail down some more asymptotics, let $w= v_1+...+v_k$.
$\left< w, w \right> = k + \sum_{i\neq j} \left< v_i,v_j \right>$.
This means that with probability at least $1-2k^2 e^{-\epsilon^2 n/2}$ we have $k-k^2 \epsilon \leq||w||^2 \leq k+ k^2\epsilon$. Choose $\epsilon$ to get the desired level of resolution for large $n$. For example if $\epsilon = 1/k^3$, we get if $d< \sqrt{k-1/k}$ that $||w|| \geq d$ with probability larger than $1-2k^2 e^{-n/(2k^6)}$ and if $d > \sqrt{k+1/k}$ that $||w||\geq d$ with probability smaller than $2k^2 e^{-n/(2k^6)}$