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.

  • 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 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
  • $\begingroup$ @WillSawin: Should $<1$ in the denominator be $<1/2$? $\endgroup$ – D_809 Dec 24 '19 at 13:01
  • $\begingroup$ @D_809 Yes, sounds right. $\endgroup$ – Will Sawin Dec 24 '19 at 16:59

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.

| cite | improve this answer | |
  • $\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 Dec 24 '19 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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