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?
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.
The OP's intuition goes awry in the very first case, $N=2$, where it predicts an expected distance of 1. As I'll show below, the expected distance between two points in the unit square is less than 1, so whatever the actual answer is in general, it's not as simple as $1/(N-1)$.
The smartest way to show that the expected distance between two points is less than 1 is, I suppose, to explicitly compute it, calculating
$$\int_0^1\int_0^1\int_0^1\int_0^1 \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}dx_1dx_2dy_1dy_2.$$
The second smartest way, I imagine, would be to write a computer program that picks random points $P$ and $Q$ and keeps a running average of their distance apart until you feel confident in the approximation.
I decided to try the third (or maybe fourth or fifth or....) smartest way: Show that the expected distance is less than something that's less than 1, using the crudest upper bounds that work. I'll describe this in a somewhat prolix fashion, following my initial line of thought to a dead end, and then modifying it to get to the cheese. My real goal was to (dis)prove the result with as little hard work as possible, but I wound up spending an awful lot of time on it (mostly correcting mistakes).
To begin with, let's recast things from the "unit" square $[0,1]\times[0,1]$ to the "Unit" square, $[-1,1]\times[-1,1]$, which simply doubles the expected length. Calling the answer on the Unit square $E$, we now want to show that $E<2$.
It'll be helpful to draw the diamond connecting the midpoints of the sides of the Unit square, and refer to a point $(x,y)$ as being inner or outer depending on whether it's inside or outside the diamond, i.e. whether $|x|+|y|$ is less than or greater than 1. (You can assign the points with $|x|+|y|=1$ however you like, or ignore them altogether.)
Any two points are either in the Same quadrant, Adjacent quadrants, or polar Opposite quadrants, with probability $1/4$, $1/2$, and $1/4$ if the points are chosen at random. This gives
$$E = {1\over4}S + {1\over2}A + {1\over4}O,$$
where $S$, $A$, and $O$ are the expected distances in the three disjoint cases (ignoring the measure-0 overlaps). In each case, the two points will either both be inner, both be outer, or will be one of each, with corresponding probability $1/4$, $1/4$, and $1/2$. Let's look at the three cases in reverse order.
In case $O$, if the two points are both inner, the distance between them is at most 2. If they're both outer, the distance is at most $2\sqrt2$. And if they're one of each, the distance is at most $\sqrt5$. Hence
$$O \le {2\over4} + {2\sqrt2\over4} + {\sqrt5\over2}.$$
For case $A$, if the points are both inner, the distance between them is again at most 2, while if either one is outer, the distance is at most $\sqrt5$, so we have
$$A \le {2\over4} + {3\sqrt5\over4}.$$
Finally (modulo a refinement to come), in case $S$, the distance between two points, whether inner or outer, is at most $\sqrt2$, i.e.,
$$S \le \sqrt2.$$
Putting all this together gives
$$E \le {1\over4}(\sqrt2) + {1\over2}({2\over4} + {3\sqrt5\over4}) + {1\over4}({2\over4} + {2\sqrt2\over4} + {\sqrt5\over2})$$
The problem is, this simplifies to
$$E \le {3 + 3\sqrt2 + 4\sqrt5\over8} \approx 2.02336407,$$
which doesn't prove what we want. But there's a clever way out. That's to realize that case $S$ is simply the original problem, on the "unit" as opposed to "Unit" square. So instead of replacing $S$ with a crude upper bound, let's use
$$S={1\over2}E$$
and write
$$E = {1\over8}E + {1\over2}A + {1\over4}O,$$
which becomes
$$E = {4\over7}A + {2\over7}O.$$
This time, the crude upper bounds for $A$ and $O$ lead to
$$E \le {3+\sqrt2+4\sqrt5\over 7} \approx 1.90835507,$$
which is all we want.
If anyone can think of another way to show that $E<2$, please post it!
This is a continuation to Douglas Zare's answer. I believe his lower bound of $1/n\sqrt{2}$ is the correct asymptotic behaviour. To see that, notice that all in inequalities in the calculation of the lower bound tend to equalities as $n\to \infty$, with the possible exception of the first inequality.
But in fact, the first inequality also tend to an equality when $n\to \infty$. This is because the error term is the measure of the overlap between discs of radius $x$ around the $k$ points and for $x=O(1/n)$, which is the relevant order of magnitude, this overlap is negligible - it's $O(k^2/n^4)$ whereas the measure of the discs is $\Theta(k/n^2)$.
Some empirical data, with each point the average of 50 trials:
The curve $1/(\sqrt{2} n)$ (displayed) fits rather well. Congrats to Douglas Zare and Ori Gurel-Gurevich!
