Suppose I sample $n$ points independently and uniformly at random in the unit square, and then I select the $pn$ shortest edges between all pairs of points, for fixed $0<p<1$. For large $n$ and small $p$, what does the sum of the lengths of these edges look like (in a distributional sense)? Geometric intuition says that the sum looks like $C(p)\sqrt{n}$ and that $C(p)\to0$ as $p\to0$, and I'm wondering what $C(p)$ looks like (say to first order)
$\begingroup$
$\endgroup$
7
-
$\begingroup$ How does $pn$ grow? $\endgroup$– LeechLatticeCommented Aug 24, 2018 at 22:52
-
$\begingroup$ @Bullet51 hopefully I've clarified with the edit? $\endgroup$– Tom SolbergCommented Aug 24, 2018 at 23:07
-
$\begingroup$ The probability distribution of the distance of two random points in the unit square looks locally like $P(x)=6x$ for small $x$. Does it show that $C(p)=cp$ for some constant $c$ as $p→0$? $\endgroup$– LeechLatticeCommented Aug 24, 2018 at 23:25
-
$\begingroup$ @Bullet51: I don't think that is what is being asked. The question is: pick points $X_1,\ldots,X_n$ in the unit square and generate random variables $(Y_{ij})_{i<j}=|X_i-X_j|$. Finally, let $Z_1,\ldots,Z_{\binom n2}$ be these random variables sorted into increasing order. The OP is asking about the limit (if it exists) of $(Z_1+\ldots+Z_{pn})/\sqrt n$, and in particular how that limit depends on $p$. $\endgroup$– Anthony QuasCommented Aug 24, 2018 at 23:28
-
$\begingroup$ Numeric intuition suggests there is a small clique of about sqrt(pn) points that fits inside a square of side 1/sqrt(sqrt(n/p)) (and probably smaller), which would give an upper bound like (sqrt p) (np)^(3/4), but this is using just combinatorics and the geometry of a square, and nothing about probability, so is likely to be improved. Gerhard "Not Using Really Small Squares" Paseman, 2018.08.24. $\endgroup$– Gerhard PasemanCommented Aug 24, 2018 at 23:31
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
1
Here is a heuristic that agrees with the power proposed by @Bullet51 in the comments above, showing that $C(p)$ should grow like $p^{3/2}$. The sum should look like $pn$ times the typical order of the $(pn)$th smallest distance.
To estimate that distance, consider a simpler problem, where the points are put in $Kn$ bins (each representing a sub-square of the unit square of side $(Kn)^{-1/2}$). Of course, this ignores the possibility that two points could be in neighbouring bins, and closer than points in their own bin, but I don't think it changes the order.
If $n$ points are distributed between the $Kn$ bins, the distribution is approximately that each bin receives a Poisson number of points with mean $1/K$. Let $X_1,\ldots, X_{Kn}$ be the number of points in each bin, and assume these are independent Poisson random variables with mean $1/K$. Now the number of pairs of points lying in the same bin is $\sum_{i=1}^{Kn} \frac 12X_i(X_i-1)\sim Kn/2(\mathbb EX^2-\mathbb EX)$. For a Poisson with mean $1/K$, the term in parentheses is $1/K^2$, so the expected number of pairs of points lying in the same bin is $n/(2K)$.
If we set this equal to $pn$, it tells you how big the bins have to be in order to have $pn$ pairs, that is $K=1/(2p)$. Hence our crude model suggests that the $(pn)$th smallest distance is of size roughly $\sqrt {1/(Kn)}\sim \sqrt{p/n}$. So the sum of the first $pn$ distances should grow like $p^{3/2}\sqrt n$.
answered Aug 24, 2018 at 23:51
-
$\begingroup$ Thanks, that's perfect. One thing I find interesting about your answer is that it seems not to work if I change the question to ask for the $pn$ points whose nearest-neighbor distance sum is as small as possible, since we no longer have the quadratic term in the summation. That's surprising to me! $\endgroup$ Commented Aug 26, 2018 at 15:44