6
$\begingroup$

Let $\mathcal{B} \subseteq \mathbb{R}^n$ be an $n$-dimensional solid body. Assume that we sample $N$ points, say $S = \{ x_1, ..., x_N \}$, from $\mathcal{B}$ uniformly at random. Consider the following random variable:

$$ D \equiv \sup_{x \; \in \; S} \; \inf_{y \; \in \; S} \; d(x, y) \; . $$

Intuitively, this variable measures the distance of the "worst" outlier to the rest of the sample set. The distribution of $D$, say $p(D)$, obviously depends on $N$ and $\mathcal{B}$. I am curious about the following:

(1) Are there any closed form expressions known for certain special cases like $\mathcal{B} = [0, 1]^n$ or $\mathcal{B}$ being the unit $n$-ball?

(2) Can we say anything about the dependence of $p(D)$ on $N$ without fixing $\mathcal{B}$? Obviously, $D \to 0$ as $N \to \infty$, but can we say more?

$\endgroup$
9
  • $\begingroup$ In other terms, you seek the maximum nearest-neighbor distance. It may be already somewhat interesting to restrict to points selected from an interval of $\mathbb{R}^1$. (And note that the "worst" outlier could be in the center of the set.) $\endgroup$ May 11, 2015 at 22:55
  • $\begingroup$ @JosephO'Rourke Agreed. A succinct result for an interval of the form $[0, U]$ could be illuminating for the purposes of estimating the dependence of $p(D)$ on $\mathcal{B}$'s size (represented by $U$ in this case) and sample count $N$. $\endgroup$ May 11, 2015 at 23:08
  • $\begingroup$ @JosephO'Rourke I changed the title of the question to use the wording you mentioned. It definitely sounds more natural than what I had in the first place. $\endgroup$ May 12, 2015 at 1:37
  • $\begingroup$ In the case of the interval, the maximum is $2/N,$ roughly. What this tells you about the general case is anyone's guess :) $\endgroup$
    – Igor Rivin
    May 12, 2015 at 1:38
  • 1
    $\begingroup$ Call the $i$th gap $X_i$. Set $Y_i=\min(X_i,X_{i+1})$. Then $Y_i$ is independent of $Y_j$ whenever $|i-j|>1$. Given $N/2$ independent $\text{Exp}(2N)$ random variables, the maximum is approximately $\log N/(2N)$. $\endgroup$ May 12, 2015 at 5:33

1 Answer 1

3
$\begingroup$

You can make the calculations for a cube with the $L_\infty$ distance and the uniform distribution and you simplify the problem a little bit by letting $X_i$ be independent of $Y_i$ you can say the following: let $X = (x_1, \ldots, x_n)$ then

$$d(X,Y) = \max_i |y_i - x_i|. $$

By letting $a_i = \min(x_i, 1 - x_i)$ and $b_i = \max(x_i, 1-x_i)$, we see the distribution of $d(X, Y)$ is given by

$$F_X(z) := P(d(X,Y) \leq z) = \prod_{i=1}^n 2 z 1_{z \leq a_i} + (z + a_i) 1_{z \in [a_i, b_i]} \geq 2^n \prod a_i 1_{z \in [a_i, b_i]}$$

This implies that $P(\max_{i \in 1, \ldots, N} \min_{j \in 1, \ldots, N} d(X_i, Y_j) \leq z) = \prod_{i=1}^N 1 - \int_{[0,1]^n} (1 - F_{X_i}(z))^N dX_i$, which we can lower bound by $\prod_{i=1}^N 1 - \int_{[0,1]^n} ( 1 - 2^n \prod_{j=1}^n a_j 1_{z \in [a_j,b_j]})^N dx_1, \ldots dx_n$. We can now upper bound the integral by $$\int_{[0,1]^n} \exp \Big(-N 2^n \prod a_j 1_{z \in [a_j, b_j]}\Big)$$

Now, using the fact that the product is smaller than $z^n$ when $z <1/2$ and the convexity of the exponential function it is easy to see that the above integral is bounded by $$ 1 - \frac{\int \prod a_j 1_{z \in [a_j, b_j]}}{z^n} + \frac{e^{-N (2z)^n} \int \prod a_j 1_{z \in [a_j, b_j]}}{z^n}$$. A straightforward calculation shows that the integral above is equal to $z^n$ therefore the previous expression is equal to $e^{-N (2 z)^n}$

We therefore have $$P(\max_{i \in 1, \ldots, N} \min_{j \in 1, \ldots, N} d(X_i, Y_j) \leq z) \geq (1 - e^{-N (2 z)^n})^N \approx e^{-N \exp(-N (2z)^n)}$$

This tells you that roughly the distance of the maximum outlier to the rest of the points is $\frac{\log N}{N^{1/n}}$ this will be true for any norm because they are all equivalent up to a n^{1/2} factor. It seems the dependency on $n$ is terrible by the way which makes you wonder why people use nearest neighbor algorithms. I am not sure how much more you can improve the bound. Then only place where I was extra generous with my bound was in (1), so maybe there you can tighten it a little more but honestly I do not see how you can get rid of the $z^n$ factor in the bound.

$\endgroup$
1
  • $\begingroup$ Actually I just realized that F_x(z) \leq z^n all the time so I think you can in fact not get rid of the z^n factor. $\endgroup$ May 13, 2015 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.