$N$ points are distributed randomly, independently according to uniform distributions in a $1 \times 1$ square. What is the probability that for each pair of points $A(x_1,y_1), B(x_2,y_2)$ in the square, $d_{A,B}>\frac{c}{\sqrt{N}}$, where $c>0$ and $d_{A,B}$ is the distance between the points $(x_1,y_1), (x_2,y_2)$.

Any idea?


In the paper Fermilab-TM=2170 (May 2002) I have described, to lowest and next-lowest order, the probability distribution of the minimum distance amongst $N$ spheres uniformly placed in a $d$-dimensional volume. This distribution provides an answer to your problem.

I will describe the reasoning in $2$ dimensions here.

Imagine p[lacing $N$ balls of radius $a$ in the square, and computing the probability that no center ever lies inside a ball already placed (thus no two centers are less than $a$ apart). At each step there is some area excluded from the area safe to place a ball.

The cumulative distribution that the minimum distance is greater than $a$ involves a product of $N$ decreasing terms each a bit smaller than $1$; an exponential distribution is obtained if you add the logs of those terms and expand each log to lowest in the small distance away from $1$. This discards terms of order $N^3a^4$. This also ignores the fact that two excluded areas ma overlap, leaving more room for further spheres; that overlap effect is also of order $N^3a^4$.

To lowest order, each time you place a ball of radius $a$, the amount of volume it covers is $\pi a^2$. Sometimes when two balls are placed, they cover less than $2\pi a^2$ because though the center of each is outside the other, the two circles overlap. Ignoring this overlap, which leads to next-order corrections in $N a2$, we can immediately write the c.d.f. for minimum distance $s$: $$ P(s^2<a^2) = 1-\prod_{k=1}^{N} (1-(k-1)u) $$ where $u\equiv \pi a^2$.

Working with even $N$ (OK since $N$ will be large) we can group the first and last term, the second and next to last, and so forth, giving $$P(s^2<a^2) = 1-\prod_{k=1}^{N/2} (1-(N-1)u+(k-1)(N-k)u^2) $$ We multipy out, discarding terms whose $N$ exponent is less than twice the $u$ exponent (because when $N^2u\gg 1$ the probability of succeeding is negligible). This leads to $$ P(s^2<a^2) \approx (N/2)(N-1)u \approx (N^2/2)u $$ This is correct until $u$ becomes of order $(1/N^2)$; but ); but it is not very useful because when $u$ reaches that size, this naive cumulative distribution function exceeds 1.

Instead, look at the log of each term. To first order in $Nu$ we can ignore the expressions that include $k$ and are left with $$ \log(1-P(s^2<a^2)) \approx -(N/2)(N-1)u \\ P(s^2<a^2) \approx 1- e^{-(N/2)(N-1)\pi a^2} $$ This suffices to give a lowest-order answer to your question: $$P(s<\frac{c}{\sqrt{N}}) \approx 1- e^{-(N/2)(N-1)\pi c^2/N} =1- e^{-(c^2/2)(N-1)\pi } $$

The next order terms are derived in the paper mentioned.

  • $\begingroup$ Thank. So, the probability that I am looking for goes to zero as N goes to infty? $\endgroup$ – Susan_Math123 Apr 24 '17 at 19:53
  • $\begingroup$ Thank you. That was helpful. Can you help me solve this problem too? math.stackexchange.com/questions/2250734/… $\endgroup$ – Susan_Math123 Apr 25 '17 at 1:26
  • $\begingroup$ The distribution of the number of points that are more than a given distance away from their respective nearest neighbors is more difficult . $\endgroup$ – Mark Fischler Apr 25 '17 at 21:17

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.