19
$\begingroup$

This question was inspired by an earlier question that I answered but would like a more precise bound for.

Consider random points $x_1, \dots, x_n$ in the unit ball in $\mathbb R^d$, uniformly and independently distributed. What is the probability that they form a set of diameter at most $1$?

A lower bound, noted by Ricardo Andrade, comes from observing that $x_1,\dots,x_n$ will always form a set of diameter at most $1$ if they all lie in the ball of radius $1/2$ centered at the origin, so the probability is at least $1/2^{nd}$. I showed this was correct up to a subexponential factor. What is that factor?

In other words, let

$$f(n) = \frac{ \left| \left\{ (x_1,\dots,x_n) \in (\mathbb R^d)^n \mid |x_i|<1, |x_i-x_j| <1 \right\} \right|}{ \left(\left| \left\{ x \in \mathbb R^d \mid |x|<1/2 \right\}\right|\right)^n }$$

What are the asymptotics of $f(n)$? I gave an upper bound of $e^{ O (n^{d/(d+1)})}$, and I know how to give a lower bound proportional to $n^d$, but these are obviously quite far apart.

It should be possible to replace ball of radius $1$ with any other reasonably large set and change the asymptotics by only a constant.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You have two variables, $n$ and $d$. Are you interested in knowing what happens if you fix $d$ and let $n$ increase? If you want both $n$ and $d$ to increase, how quickly relative to each other? $\endgroup$
    – Douglas Zare
    Commented Apr 5, 2016 at 22:51
  • $\begingroup$ @DouglasZare I'm primarily interested in the case when $d$ is fixed and $n$ is increasing. I also expect this to be the easiest case. $\endgroup$
    – Will Sawin
    Commented Apr 6, 2016 at 0:24
  • $\begingroup$ @WillSawin: Should $<1$ in the denominator be $<1/2$? $\endgroup$
    – D_809
    Commented Dec 24, 2019 at 13:01
  • $\begingroup$ @D_809 Yes, sounds right. $\endgroup$
    – Will Sawin
    Commented Dec 24, 2019 at 16:59

1 Answer 1

Reset to default
1
$\begingroup$

See Theorem 1.1 in

Mayer, Michael; Molchanov, Ilya, Limit theorems for diameter of a random sample in the unit ball, Extremes 10, No. 3, 129-150 (2007). ZBL1164.62003.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Igor, I don't see how this result applies here. Will is asking about the probability in Theorem 1.1 with $t=n^{\frac{4}{d+3}}$ while $t$ is fixed there as $n\to\infty$. $\endgroup$
    – D_809
    Commented Dec 24, 2019 at 20:18

You must log in to answer this question.

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