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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.