A previously posted question "mean minimum distance for N random points on a one-dimensional line" produced an elegant answer: for a line of length L, the expected minimum distance (between random points) = L/(N^2/1), or simply 1/(N^2-1) for a line of unit length.
I am wondering what the corresponding value would be for the unit plane? I am not a mathematician, but my intuition suggests the answer is simply 1/(N -1), given N points on a unit square (plane).
Am I correct?
Best Answer
Let $p_n(x)$ be the probability that $n$ points in the unit square are at distances at least $x$ from each other. The expected minimum distance $E_n$ is $\int_0^\sqrt{2} p_n(x)dx$. If we can estimate $p_n(x)$, we get estimates on the integral.
Here are two crude estimates for $p_n(x)$. If we have drawn $k$ points, the probability that the next is within $x$ of one of the points is at most $k \pi x^2$, and at least $k \frac{\pi}4 (\frac{x}2)^2 = k \pi x^2/16$. The latter comes from putting a disk of radius $x/2$ at each of the previous points. These disks can't overlap, and at least a quarter of each disk is inside the square. We could improve this significantly on a torus.
Lower bound:
$$\begin{eqnarray} p_n(x) & \ge & \prod_{k=0}^{n-1} \max(0,1-k\pi x^2) \newline &\ge &\prod_{k=0}^{n-1} \max(0,1-n\pi x^2)^{k/n} \newline & = & \max(0,1-n\pi x^2)^{(n-1)/2} \newline \int_0^\sqrt2 p_n(x)dx & \ge & \int_0^{1/\sqrt{n\pi}} (1-n\pi x^2)^{(n-1)/2 } dx. \end{eqnarray}$$
A trigonometric substitution works. Mathematica evaluates that integral as $$E_n \ge \frac{\Gamma((n+1)/2)}{n^{3/2} \Gamma(n/2)} = \frac{{n\choose n/2}\sqrt{\pi}} {2^n 2\sqrt{n}} \sim \frac{1}{n\sqrt{2}}.$$
Upper bound:
$$\begin{eqnarray}p_n(x) & \le & \prod_{k=0}^{n-1} \max(0,1-k\pi x^2/16) \newline & \le & \prod_{k=0}^{n-1} \max(0,1-\pi x^2/16)^k \newline & = & \max(0,1-\pi x^2/16)^{n(n-1)/2}\newline \int_0^\sqrt{2} p_n(x)dx &\le & \int_0^{4/\sqrt{\pi}}(1-\pi x^2/16)^{n(n-1)/2}dx. \end{eqnarray}$$
Mathematica evaluates that integral as $$E_n \le \frac{2 \Gamma(1 + n(n-1)/2)}{\Gamma(3/2 + n(n-1)/2)} = \frac{2 \sqrt{\pi}{t(n) \choose t(n)/2}}{2^{t(n)}} \sim \frac{2\sqrt{2}}{n}.$$
where $t(n) = n^2 -n + 1$.
So, these crude upper and lower bounds only differ by a factor of $4$, and for large $n$, $1/n$ might be about right.