# Estimating the smallest distance between $n$ points uniformly distributed on the unit circle.

I'm working on the following question and would like some hints or solutions

Let $n$ points be iid, uniformly distributed on the unit circle. Let $\Delta_n$ be the smallest distance between any two of these points. Show that $n^\theta \Delta_n\to 0$ in probability as $n\to \infty$, for all $0<\theta<2$. HINT: Divide the circle into small arcs and find the probability that at least one arc contains 2 or more points

So I tried following the hint, and I considered dividing up the circle into $n-1$ pieces that would give with probability 1, that two are in the same section. However, $n^\theta/n-1$ does not go to zero. The other things I tried were $n^2$ pieces and $n$ pieces, but the probability calculations are rather messy for these and I'd be dealing with factorials, which does not seem like it would go well with this problem.

Source: Problem 2

• Try starting with the following question. Given n points and m (> n) arcs, what is the probability that all the points are in different arcs? The answer to your question should follow. – herb steinberg Jul 20 '18 at 21:21
• I got that the probability is $\frac{m*(m-1)\cdots(m-n+1)}{m^n}$ but don't we need to be more specific about what $m$ is becuase $n^\theta/m$ doesnt necessarily go to zero. – iYOA Jul 20 '18 at 22:00
• Can you make something of the following? In the limit, we are essentially dealing with points distributed according to a Poisson distribution with mean separation $2\pi/n$. Then the minimum of $n$ variables, each with that distribution, has a mean value of $1/n$ times that, or $2\pi/n^2$, and the result follows. Not exactly rigorous, but perhaps it can be turned into something rigorous. – Brian Tung Jul 20 '18 at 22:46
• Also, with the factorials, I'd make use of Stirling's approximation, if that's permissible. – Brian Tung Jul 20 '18 at 22:48
• I think stirling's approximation is fair game here, since we did indeed cover it in class. – iYOA Jul 21 '18 at 22:02

## 1 Answer

This is essentially the birthday problem, thinly disguised. (I'm a little dismayed it took me this long to see it.) If we divide the circle into $m$ equal segments, then the probability that there exists at least one segment shared by at least two of the $n$ points is $q = 1-\frac{m!}{m^n(m-n)!}$. Stirling's approximation

$$k! \approx \left(\frac{k}{e}\right)^k\sqrt{2\pi k}$$

allows us to rewrite $q$, roughly, as

$$q \approx 1-\exp \left(-\frac{n^2}{2m}\right)$$

Observe that for $m = n^\theta$, $0 < \theta < 2$, we have that $q \approx 1-\exp \left(\frac{-n^{2-\theta}}{2}\right) \to 1$.

The Wikipedia article linked above gives a variety of ways to approximate the birthday coincidence probability. Pick a favorite. :-)

• Thanks, the idea makes sense but I'm trying to work out the details and I seem to be getting stuck. For instance, how do you get that $\frac{m!}{m^n(m-n)!}$ equals $\exp(-n/m^2)$. Using stirling's approximation, I'm getting that it is $e^{(-n)}(\frac{m}{m-n})^{(m-n+1/2)}$, but I don't see how to further simplify it. Also, there might be a typo somewhere because if you set $m=n^\theta$, we would have $\exp{(-n^{1-2\theta})}$, not $\exp{(-n^{2-\theta})}$. – iYOA Jul 21 '18 at 22:48
• @iYOA: Yeah, that was a whopper of a typo. I edited my answer, but you can check the edit history. – Brian Tung Jul 22 '18 at 4:14
• @iYOA: To answer your other question, see here for a pretty good exposition. It's about halfway down the page—look for "Stirling." – Brian Tung Jul 22 '18 at 4:33