0
$\begingroup$

Let $C_n$ be the hypercube $[-1,1]^n$. For $a_1,\cdots,a_s \in C_n$, define its dispersion $D(a_1,\cdots,a_s)$ as $\max_{x \in C_n}\min_{i \in [s]} \|x-a_i\|_{2}$. Let $0< \lambda < 1$ be a constant. How small can $s(n)$ be so that $$ \lim_{n\rightarrow \infty}\{ \Pr_{a_1,\cdots,a_s \sim C_n}\left[ D(a_1,\cdots,a_{s}) \leq \lambda \right] \} \geq 2/3 \;? $$

Upper bound: $O(n^{cn})$ for some constant $c$

Proof: Divide $C_n$ into subcubes, each with side length $l$. The number of subcubes is $\left(\frac{2}{l} \right)^n$. By Coupon Collector's, if $s(n) = \left(\frac{2}{l} \right)^n\log\left(\left(\frac{2}{l} \right)^n \right) + K\left(\frac{2}{l} \right)^n$ (for a large enough constant $K$), then all subcubes will be hit with probability at least $2/3$. If all subcubes are hit, the dispersion is at most $\frac{l\sqrt{n}}{2}$. Taking $l=\frac{2\lambda}{\sqrt{n}}$, we get an $O(n^{cn})$ upper bound.

Lower bound: $\Omega(e^{cn})$ for a constant $c$

Proof: Divide $C_n$ into subcubes, each with side length $l$. By Coupon Collector's, if $s(n) = \left(\frac{2}{l} \right)^n \log\left(\left(\frac{2}{l} \right)^n \right) + k\left(\frac{2}{l} \right)^n$ (for some small enough constant $k$), then the probability of hitting all subcubes is at most 0.6. Hence, the probability of missing at least one subcube is greater than 0.4. If you miss at least one subcube, then the dispersion is greater than $\frac{l}{2}$. Hence, $$ \lim_{n\rightarrow \infty}\{ \Pr_{a_1,\cdots,a_s \sim C_n}\left[ D(a_1,\cdots,a_{s}) \leq \frac{l}{2} \right] \} \leq 0.6 . $$ Taking $l = 2\lambda$, we get an $\Omega(e^{cn})$ lower bound.

$\endgroup$

1 Answer 1

1
$\begingroup$

The packing number of the cube with L2 balls of radius $\lambda$ is at least $ \lambda^{-n} C^n (n/2)! \approx \lambda^{-n} C^n n^{n/2} $. By the argument you had before you get the upper bound in the question is tight.

$\endgroup$
10
  • $\begingroup$ But some of the balls could be partially outside the cube. So, the "actual volumes" (volume of the ball inside the cube) of each ball is not the same. Hence, I don't see how we can apply coupon collector's. Variations of the Coupon Collector problem where coupons have different probabilities have been studied, but I don't see how we can estimate the "actual volumes" of a maximal (or "approximately" maximal) $\lambda$-ball packing. $\endgroup$ Mar 31, 2023 at 9:46
  • $\begingroup$ The maximum number of $\lambda$-balls that can be "fully packed" (packed with the additional constraint that each ball is completely inside the cube) should be $(1/\lambda)^n$. We can apply coupon collector on this construction to get the $e^{cn}$ lower bound. $\endgroup$ Mar 31, 2023 at 15:27
  • $\begingroup$ Maybe I am misunderstanding something. Regardless of whether partial or not, if you want dispersion less than $\lambda$ you need to hit every ball in the covering else the missed ball will witness large dispersion. Now the set of balls in the covering are disjoint events. So you need at least as many points to hit all of them. $\endgroup$ Mar 31, 2023 at 15:43
  • $\begingroup$ That is correct, but you may not need $n^{cn}$ points sampled uniformly from the cube to hit all the (partial and full) balls. I don't see how we can apply Coupon Collector's here, since the probabilities of hitting each ball is not the same. $\endgroup$ Mar 31, 2023 at 15:53
  • $\begingroup$ This is what I am not understanding. There are roughly $n^{cn}$ disjoint balls. Each new point can hit at most one of the balls (appropriately switching between $\lambda$ and $\lambda/2$ if necessary). If a ball is not hit, there is no point at distance $\lambda$ from the corresponding center, and thus the dispersion is greater than $\lambda$. $\endgroup$ Mar 31, 2023 at 15:58

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.