# Probability that points uniformly distributed are at least $c/\sqrt{N}$ far apart.

$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.

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