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