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!


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.