Concentration of $k$-th pairwise distance of random points in a unit square

Question

For $1\leq i \leq n$, let $X_i\sim \text{Uniform}(0,1)$, $Y_i \sim \text{Uniform}(0,1)$ be $n$ points chosen uniformly in the unit square. Denote the $k$-th smallest pairwise distances across the $n$ points as $d_k$ ($1\leq k \leq {n\choose 2}$). I am interested in literature on:

1. $\mathbb{E}(d_k)$, or at least a good bound on $\mathbb{E}(d_k)$.
2. The concentration of $d_k$ around $\mathbb{E}(d_k)$.

For 1, I was able to get the expectation for some $k$s such as $k=1,{n\choose 2}$, and some intermediate $k$ by complicated integrals. However, I can't seem to find a generalization of this.

For 2, my "computational experiments" indicate that $d_k$ is extremely concentrated around its expectation, but I'm clueless on a tail bound that might be useful to prove this considering the dependence of $d_k$ variables (I played with Talagrand and Chernoff but both do not work).

Any ideas?

Answer 1

Just came across this paper on arxiv and remembered I posted this question here last year. This is specifically regarding my Question 2. I thought to post an answer.

The authors studied a similar problem to what I was interested in. Specifically, for a set $P$ of $n$ points uniformly and independently chosen from $[0,1]^d$, and a distance $r\in [0,1]$, let $f_r$ denote the number of pairs from $P$ with toroidal distance $\leq r$ where the toroidal distance is the wrap around distance in $[0,1]^d$. Note that $f_r\in \{0, ..., {n\choose 2}\}$. Then they showed that $f_r$ is extremely concentrated:

$$Pr(|f_r-\mathbb{E}(f_r)| > c n\log n ) \leq \frac{1}{n^{O(1)}}$$

For a sufficiently large constant $c$ (e.g 100). They also wrote this specifically on my problem:

We believe the result is also true for the Euclidean distance, but handling the boundary cases proved significantly more difficult to tackle than one would expect. Hence the simplifying Toroidal topology was assumed.

Answer 2

(Too long for a comment)

I don't have good knowledge about literature on this problem, but here are some of my thoughts:

1) For the "typical" distances, the set of $n$ uniformly chosen points is not so different from $n$ points forming a lattice in the unit square. So we should expect that the profile of $t\mapsto d_{k(t)}$ for $k(t) = \bigl\lfloor\binom{n}{2}t\bigr\rfloor$ converges, in an appropriate sense, to the inverse CDF of the distance between two randomly chosen points in the unit square. Numerical simulations indeed support this picture:

I suspect that a kind of coarse-graining argument might help verify this, although this approach would be too crude for obtaining good concentration results.

2) The small values of $d_k$ will be achieved only for occasional pairs that are within $\mathcal{O}(1/n)$ distance to each other, and we would expect that such pairs occur almost independently of each other. More precisely, fix $\ell \gg 1$ and let $m \sim n/\ell $ as $n\to\infty$. Also, let $\mathsf{B}_{i,j} = [\frac{i-1}{m}, \frac{i}{m}]\times[\frac{j-1}{m}, \frac{j}{m}]$ be subsquares of $[0, 1]^2$. Then the event $A_{i,j}$ that there are at least two points lying in $\mathsf{B}_{i,j}$ is approximately $n^2/2m^4$, so there are typically $n^2/2m^2 \sim \ell^2/2$ number of subsquares containing two or more points.

This suggests that $n d_k$'s for "small" $k$'s will behave like the distance between the origin and the $k$-th closest point in the Poisson point process on $\mathbb{R}^2$ with intensity $\frac{1}{2}$, or equivalently, the arrivals in the inhomogeneous Poisson process on $[0, \infty)$ with intensity measure $\lambda(\mathrm{d}t) = \mathrm{d}(\pi t^2/2)$. A numerical simulation also confirms this heuristics:

(The blue dots are simulated values of $nd_k$'s for $k=1,2,\ldots,200$ with $n=1000$, and the orange line is the graph of the function $k\mapsto\sqrt{2k/\pi}$.)