Mean maximum distance for N random points on a unit square

Question

Following up on Mean minimum distance for N random points on a one-dimensional line and Mean minimum distance for N random points on a unit square (plane), I have the following questions.

Given N random points in the unit square, what is the expected value of the Maximum distance between any two such points?

I know that the expected value of the distance is $\Big(2 + \sqrt{2} + 5 \log (1+ \sqrt{2}) \Big)$ and the (mysterious) distribution of the distances is given by the square line picking distribution (http://mathworld.wolfram.com/SquareLinePicking.html).

Thank you!

Answer 1

Here is a first approximation for large $n$.

The formulas are easier if we use the diamond whose whose corners are $(\pm 1,0)$, $(0,\pm 1)$. Then the pdf of the $x$-coordinate is just $1-|x|$.

The expected maximum distance is at least $2\, E[\max x]$. If $u>0$, $$P(\max x < u) = P(\text{all }x < u) = (1-(1-u)^2/2)^n \sim e^{-(1-u)^2 n/2}$$

So, ignoring the negligible possibility that the maximum might be negative, \begin{align} E[\max x] &= \int_0^1 u(1-u)n\,e^{-(1-u)^2 n/2} du\\ &=1 - \sqrt{\frac{\pi}{2n}}\text{erf}\left(\sqrt{\frac n2}\right)\\\ &\sim 1-\sqrt{\frac{\pi}{2n}} \end{align}

So the expected maximum distance on the diamond is at least $2-\sqrt{2\pi/n}$, and the expected maximum distance on the unit square is at least $\sqrt{2}-\sqrt{\pi/n}$.

Empirically the formula $\sqrt{2}-\sqrt{2/n}$ works well for $n=100$ or $n=1000$. So this rough estimation seems to get the right order of $n$, and better attention to using all four corners of the diamond would get a more accurate result.

Answer 2

Consider going a small distance $h$ along the diagonal away from a corner. The probability of finding a point in the corner triangle with height $h$ is $n h^2$, and such a point is at least $x = \sqrt{2} - 2h$ away from a point in the same triangle at the opposite corner. If $D$ is the maximum distance, we have for small enough $h$ $$\Pr[D > \sqrt{2} - 2h] \approx n h^2 .$$ Rewriting $h = (\sqrt{2}-x)/2$, we hence get the approximate distribution function $$F(x) = \Pr[D \le x] \approx 1 - \frac{n}{4} (\sqrt{2} - x)^2$$ with the lowest acceptable $x_0$ where $F(x_0) = 0$ or $x_0 = \sqrt{2} - 2/\sqrt{n}$. Integrating then gives the expectation, $$E[D] \approx \int_{x_0}^{\sqrt{2}} \! x \, F'(x) \, dx = \sqrt{2} - \frac{4}{3\sqrt{n}}.$$

The idea here is that there is a density $n_1$ of points for which the maximum distance is a.s. larger than unity. In that case, only points in opposing corners need to be considered. From the approximation above, $x_0 = 1$ implies $n_1 \approx 12 + 8\sqrt{2} \approx 23.3$, so that is where we can expect the result to become reasonable.

Here is a plot of the approximation and simulated distances, which seems to indicate that this is more or less what's actually going on:

Of course, there is then the further approximation of the true distance by the projection onto the diagonal. But the more we move into the corners, the better that approximation becomes.

Answer 3

I give a little more precised estimate from the arguments of N.T. and Matt in the case $N$ is large.

I assume the number of point $N$ is not fixed but given by a Poisson law of mean $N$. As $N$ is large this problem sould be completely equivalent to the original one but calculations are simpler.

The extrems points are in the corners and as Matt we use a diamant to simplify the notation. We note $X_1=(1-x_1, y_1)$, $X_2=(-1+x_2, y_2)$, $X_3=(x_3, 1-y_3)$ and $X_4=(x_4, -1+y_4)$ where we expect $x_1,\cdots,y_4$ to be small. We have that $$\|X_1-X_2\| = \sqrt{(2 -x_1-x_2)^2+(y_1-y_2)^2}\approx (2 -x_1-x_2) $$So it is enough to consider $(1-x_1,x_2-1)$ and $(1-y_3,y_4-1)$ the extrema for the $x$ and $y$ coordinates. Because our point process is a Poisson point process of constant density $\frac{N}{2}$. Its projection on the $x$ axis is a Poisson point process of density $N(1-|x|)$. From this we deduce that for $1\geq a\geq 0$ $$\mathbb{P}(x_1\geq a) = \exp(-\int_0^a N u du) =\exp(-\frac{Na^2}{2}) $$ And we also have that $x_2, y_3,y_4$ follow this same law by symetry. Moreover $(x_1,x_2,y_3,y_4)$ are independent. We can now conclude writing $\tilde{x}=\sqrt{N}x$ that for large $N$ the maximal distance between two points behave like $$ D = 2-\frac{1}{\sqrt{N}}\min(\tilde{x}_1+\tilde{x}_2,\tilde{y}_3+\tilde{y}_4)$$ where $\tilde{x}_1,\tilde{x}_2,\tilde{y}_3,\tilde{y}_4$ are iid random variables with law $\mathbb{P}(\tilde{x}_1\geq a)=\exp{-\frac{a^2}{2}}$