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.

Thanks in advance.

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

  • 1
    $\begingroup$ What is unsatisfactory about the Central Limit Theorem? $\endgroup$ May 15, 2013 at 22:04
  • $\begingroup$ To clarify: $||v_i||\leq 1$ right? not $||v_i||=1$? $\endgroup$ May 15, 2013 at 22:40
  • $\begingroup$ @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. $\endgroup$
    – TMM
    May 15, 2013 at 23:02
  • 1
    $\begingroup$ @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$). $\endgroup$
    – TMM
    May 15, 2013 at 23:08
  • $\begingroup$ 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. $\endgroup$ May 16, 2013 at 0:24

1 Answer 1


EDIT: Woops just realized the vectors are drawn from the ball, not the sphere. But the measure of the ball is almost entirely concentrated at the sphere so the same result should apply with just slightly weaker asymptotics

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)}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.