# Minimum distance between independent points drawn from the normal distribution

Let $$x_1,\ldots,x_N$$ be $$N$$ samples drawn independently from the normal distribution $$\mathcal{N}(0,1)$$. Let $$\Delta_{ij} = | x_i - x_j |$$ be the distance between the $$i$$-th and the $$j$$-th sample. Let $$M_N = \min_{ij} \Delta_{ij}$$ be the minimal distance (nearest neighbor distance) between all pairs of points.

Is the distribution of $$M_N$$ easy to compute?

I am particularly interested in making a statement of the form "$$P(M_N \ge \mu) \ge 1 - \epsilon$$", computing the limit $$\mu$$ for a given $$\epsilon$$.

The bound does not need to be tight, but it should not be catastrophically off. I am considering the non asymptotic case, $$N$$ will be between 1 and 10000, $$\epsilon$$ will be small (of the order of $$10^{-6}$$ to $$10^{-12}$$) -- which seems to hinder Monte Carlo computations.

(I have seen plenty of posts on MathOverflow and the Mathematics Stack Exchange about samples from the uniform distribution -- but nothing about normal variables.)

This answer gives a bound of the requested form, but I have no idea whether it is "catastrophically off" :)

• $$\min_{ij} \Delta_{ij} < \mu \iff \text{some } \Delta_{ij} < \mu$$

• $$P(\min_{ij} \Delta_{ij} < \mu) = P(\text{some } \Delta_{ij} < \mu) = P(\bigcup_{ij} (\Delta_{ij} < \mu)) \le \sum_{ij} P(\Delta_{ij} < \mu)$$

• $$P(\min_{ij} \Delta_{ij} \ge \mu) = 1 - P(\min_{ij} \Delta_{ij} < \mu) > 1 - \sum_{ij} P(\Delta_{ij} < \mu) = 1 - \epsilon$$

So we identify $$\epsilon = \sum_{ij} P(\Delta_{ij} < \mu)$$. But all the $$x_i$$ are i.i.d. $$N(0,1)$$, so any $$(x_i - x_j) \sim N(0,\sqrt{2})$$.

• $$\epsilon = \sum_{ij} P(\Delta_{ij} < \mu) = {N \choose 2} P(|N(0,\sqrt{2})| < \mu) = {N \choose 2} \text{ erf}({\mu \over 2}),$$ where $$\text{erf}$$ is the error function

• $$\mu = 2 \text{ erf}^{-1} (\epsilon / {N \choose 2})$$

For your typical values of $$\epsilon < 10^{-6}$$, especially if you then divide $$\epsilon / {N \choose 2}$$ for some large $$N$$, the argument to the error function is going to be tiny. In this case I think a reasonable approximation might be:

• $$x \approx 0 \implies \text{erf}(x) = {2 \over \sqrt{\pi}} \int^x_0 e^{-t^2} dt \approx {2 \over \sqrt{\pi}} \int^x_0 e^0 dt = {2 \over \sqrt{\pi}} x$$

• So $$\mu \approx 2 {\sqrt{\pi} \over 2} \epsilon / {N \choose 2} = \color{red}{\sqrt{\pi} \epsilon / {N \choose 2}}$$

Reminder: I have no idea how accurate / catastropically off this is. Hope this helps!