4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – herb steinberg Jul 20 '18 at 21:21
  • $\begingroup$ 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. $\endgroup$ – iYOA Jul 20 '18 at 22:00
  • $\begingroup$ 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. $\endgroup$ – Brian Tung Jul 20 '18 at 22:46
  • $\begingroup$ Also, with the factorials, I'd make use of Stirling's approximation, if that's permissible. $\endgroup$ – Brian Tung Jul 20 '18 at 22:48
  • $\begingroup$ I think stirling's approximation is fair game here, since we did indeed cover it in class. $\endgroup$ – iYOA Jul 21 '18 at 22:02
5
$\begingroup$

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. :-)

$\endgroup$
  • $\begingroup$ 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})}$. $\endgroup$ – iYOA Jul 21 '18 at 22:48
  • $\begingroup$ @iYOA: Yeah, that was a whopper of a typo. I edited my answer, but you can check the edit history. $\endgroup$ – Brian Tung Jul 22 '18 at 4:14
  • $\begingroup$ @iYOA: To answer your other question, see here for a pretty good exposition. It's about halfway down the page—look for "Stirling." $\endgroup$ – Brian Tung Jul 22 '18 at 4:33

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.