Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
@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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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