16
$\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 \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.

$\endgroup$
  • $\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 Apr 5 '16 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 Apr 6 '16 at 0:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.