11
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Nice question. For all of the related questions, I would really like to see the exact results, since I could not find them worked out or even discussed anywhere. The distribution of distances between $n > 2$ random points over the unit square would be a start, but I cannot find that either, and it does not seem simple. $\endgroup$ – student Dec 12 '18 at 11:39
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Empirically it seems something like $\sqrt{2}-\dfrac{\sqrt{2}}{\sqrt{n}+\frac14}$ may do even better $\endgroup$ – Henry Dec 12 '18 at 11:14
5
$\begingroup$

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:

simulation

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.

$\endgroup$
  • $\begingroup$ Thanks, nice intuition. However, there are some steps which I do not follow. $n h^{2}$ cannot be a probability (choose $h=2/\sqrt{n}$ and you get a probability equal to 4). Indeed, $n h^{2}$ is only the expected value of the number of points in the corner triangle. The number of points in such a triangle follow a Bernoulli distribution with probability $p=h^{2}$. It follows that $P(D > \sqrt{2} - 2h)$ is approximately $(1-e^{-h^{2}n})^{2}$... $\endgroup$ – Silvia Dec 12 '18 at 13:32
  • 1
    $\begingroup$ Worth noting: you and I have converged on essentially the same argument in different language. Your “in the corner triangle with height $h$” corresponds to my “max x > u” with the change of variables $h=\sqrt 2-u/\sqrt 2$; and then your pdf is the linear approximation to mine, which makes your integral easier. $\endgroup$ – Matt F. Dec 12 '18 at 13:36
  • $\begingroup$ @MattF. That's a good point, actually, and I would not have added an answer had I noticed. I was blindsided by the fact that the linear approximation gives a coefficient that ends up being much closer. $\endgroup$ – student Dec 12 '18 at 13:51
  • $\begingroup$ @Silvia Oh, I think I see now where you are coming from! The probability of finding no point in the area $h$ is given by $\Pr[X <= 0]$ for $X$ following a Bernoulli distribution of $n$ trials with probability $h$, which is $(1-h^2)^n$, so $\Pr[D > \sqrt{2}-2h] \approx 1 - (1 - h^2)^n$ which has the expansion $n h^2$ for small $h$. $\endgroup$ – student Dec 12 '18 at 17:19
  • $\begingroup$ @N.T. precisely. I think that is a more rigorous way of proceeding but it is true that, in the limit, the approximation works either way (and indeed agrees with Matt's answer). An interesting challenge would be to find accurate results for $n$ small. $\endgroup$ – Silvia Dec 12 '18 at 17:55
3
$\begingroup$

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}}$

$\endgroup$

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.