3
$\begingroup$

$n$ points $\{X_i\}$ are drawn at random from a uniform distribution over a domain $\Omega\subset \mathbb{R}^m$ with a Lipschitz boundary. $D_n$ is defined as $$D_n = \sqrt{\frac{1}{\sum\limits_{1\le i,j \le n,i \ne j} \frac{1}{\|X_i-X_j\|_2^2}}}$$

I want help in finding the convergence rate of $D_n$ as $n\to\infty$, in terms of $n$ and $m$.

$\endgroup$
2
  • $\begingroup$ $D_n$ is not well-defined as written as whenever $i = j$ you have zero in the denominator. Maybe you wanted to sum only over $i < j$? $\endgroup$ Commented Aug 1 at 9:32
  • $\begingroup$ @MartinModrák : Thank you. I have edited to make $i$ not equal to $j$. $\endgroup$
    – Rajesh D
    Commented Aug 1 at 13:00

1 Answer 1

4
+50
$\begingroup$

This is a partial answer, not sure a complete proof covering the case $m=2$ would fit within an MO answer. Let's look at $A_n = 1/(2D_n^2) = \sum_{i<j} |X_i - X_j|^{-2}$, so the question is how fast does $A_n$ diverge.

When $m > 2$, the function $X \mapsto |X|^{-2}$ is integrable so that, by the law of large numbers, $A_n$ is of order $n^2$ with a prefactor you can easily guess. When $m \le 2$ on the other hand, $A_n$ has infinite expectation and the sum will be influenced by extreme events. In dimension $1$, points are ordered and distances between consecutive points are well approximated by i.i.d. $\exp(1/n)$ random variables. The minimum of $n$ such random variables is of order $1/n^2$, so one would expect to have $A_n \approx n^4$ in that case. (Not in the sense of having expectation of that size, but in the sense that the laws of $A_n/n^4$ are tight.)

Dimension $2$ is the most delicate case. By performing again a Poisson approximation and chopping up $\Omega$ into about $n^2$ disjoint boxes of area about $1/n^2$, one finds that with order $1$ probability each box contains only one of the $X_i$'s. On larger domains however a law of large numbers kicks in, so the expectation would be that $A_n$ is of order of its expectation, provided that we force the $X_i$'s to be at least at distance $1/n$ from each other, which yields $A_n \approx n^2\log n$.

$\endgroup$
2
  • $\begingroup$ What is the prefactor for the $m>2$ case. My guess is $\frac{1}{3}$ $\endgroup$
    – Rajesh D
    Commented Aug 17 at 6:26
  • $\begingroup$ there is no $\log(n)$? $\endgroup$
    – Rajesh D
    Commented Aug 17 at 6:28

You must log in to answer this question.

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