Packing a larger sphere with smaller spheres in high dimensions

385 Views Asked by At

We were discussing today the probability of leaving a point uncovered while trying to fill a larger sphere by randomly throwing in smaller spheres. Here's the argument:

We are working in $\mathbb{R}^d$. The radius of the larger sphere is 1 and the radius of the smaller spheres is $\frac{1}{4}$. So the volume of the larger sphere is $c\cdot 1^d=c$ and the radius of the smaller sphere is $c\cdot \left( \frac{1}{4} \right)^d$. Now a point A will be left uncovered if no smaller sphere has its center within a ball of radius $\frac{1}{4}$ around A. So the probability that A is uncovered after $N$ throws is $$p=\left( \frac{c-c\cdot \left( \frac{1}{4} \right)^d}{c} \right) ^N = \left( 1-\left( \frac{1}{4} \right)^d \right)^N$$

Now if $N=5^d$, $$p=\left( \left( 1-\frac{1}{4^d}\right)^{4^d} \right)^{\frac{5^d}{4^d}} \approx e^{-\frac{5^d}{4^d}}\rightarrow 0 \text{ as } d\rightarrow \infty$$

The claim then was that if you throw $5^d$ balls, the probability that a point will be left uncovered $\rightarrow 0$.

The question I have is: Isn't this the probability that a particular point A is uncovered? To make the claim that no point will be left uncovered, wouldn't we need a union (possibly over an infinite set)? The professor said no, but without any explanation. If not, the probability that a particular point is uncovered is the same as the probability that there exists a point uncovered, which seems paradoxical.