6
$\begingroup$

I am reading "Probability theory and combinatorial optimization" by J.M. Steele and am hung up on a statement made in Section 2.2 of Chapter 2, "Easy size bounds", in which it is stated (paraphrasing for brevity) that for a set of $n$ points $\{X_1,\dots,X_n\}$ independent and uniformly distributed in $[0,1]^2$, there exists a constant $c>0$ such that $$\mathbf{E} \min\{ |X_i-X_j| : X_i,X_j \in\{ X_1,\dots,X_n \} \}\geq c/\sqrt{n} $$. The author says that it is due to "a computation that perfectly parallels the proof of Lemma 2.1.1". Is there a direct reference, or an obvious proof, for this result somewhere? I would think the lower bound would be $c/n$ because there are $n(n-1)/2$ total pairs that we're looking at.

I looked at Lemma 2.1.1 in this book, which basically puts an upper bound on the quantity $ \mathbf{E} \min_i \| x-X_i \| $ for an arbitrary point $x\in [0,1]^2$, and the details of how one might recover a proof of the above result are not clear to me. The two seem quite different because the above result deals with $n*(n-1)/2$ total edges, whereas Lemma 2.1.1 deals only with $n$ edges between the point $x$ and the other points $X_i$.

Improve this question
$\endgroup$
2
  • $\begingroup$ I'd like to see an answer to this too. My heuristic agrees with yours. The probability that a particular $X_i$ does not lie within $r$ of another $X_j$ is essentially $(1-r^2)^n\approx e^{-r^2n}$. Assuming the distances to the nearest $X_j$ are independent for different $i$ and $i'$, the probability that no pair of $X_i$'s are within a distance $r$ is approximately $e^{-r^2n^2}$. If $r\approx 1/\sqrt n$, this is outrageously small. $\endgroup$
    – Anthony Quas
    Commented Aug 22, 2013 at 0:00
  • $\begingroup$ My simulations give an average minimum distance of very close to 1/n (and nowhere near $1/\sqrt{n}$) for n in [20, 40, 80, 160, 320, 640, 1280]. The minimum distances, averaged over ten thousand trials at each value of n, were [0.0515, 0.0245, 0.0120, 0.00599, 0.00296, 0.00147, 0.000738]. For comparison, 1/n is [0.05, 0.025, 0.0125, 0.00625, 0.003125, 0.0015625, 0.00078125] and $1/\sqrt{n}$ is [0.224, 0.1587, 0.112, 0.079, 0.056, 0.040, 0.028]. $\endgroup$
    – usul
    Commented Aug 22, 2013 at 2:40

1 Answer 1

Reset to default
1
$\begingroup$

The most natural way (to me) of thinking about this question is the following: think of your points as complex numbers. Then, the set of points (ignoring the unit square condition for the moment) where the min is smaller than some $x$ is the tubular neighborhood of radius $x$ around the union of hyperplanes $x_i=x_j,$ of which there are $n(n-1)/2.$ Now, the area of a disk of radius $c$ is proportional to $c^2,$ and the $(n-1)$-dimensional measure of the intersection of each such hyperplane with the product of unit squares, each of which is bounded above and below by some constant. So, the probability that you lie in that tubular neighborhood is proportional to $n^2c^2.$ A similar argument works in any dimension (and actually gives the distribution of the minimimum distance).

Improve this answer
$\endgroup$
7
  • $\begingroup$ I don't understand this. If I read it right, you're saying the expected minimum distance is $\Omega(1)$ irrespective of the number of points. Of course, this violates the pigeonhole principle. $\endgroup$
    – Anthony Quas
    Commented Aug 21, 2013 at 23:55
  • $\begingroup$ That's because there was a typo :( $\endgroup$
    – Igor Rivin
    Commented Aug 22, 2013 at 0:07
  • $\begingroup$ so it sounds like you're agreeing with the OP, that the minimum distance between a pair of points should be $1/n$ not $1/\sqrt n$? $\endgroup$
    – Anthony Quas
    Commented Aug 22, 2013 at 0:12
  • $\begingroup$ Yes, but in one dimension it is $1/n^2,$ I believe. $\endgroup$
    – Igor Rivin
    Commented Aug 22, 2013 at 0:20
  • $\begingroup$ I think it's $n^{-2/d}$ (which captures both of these) $\endgroup$
    – Anthony Quas
    Commented Aug 22, 2013 at 1:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .