What is the largest disk that will be completely covered by randomly placed disks of areas $1,\frac12,\frac13,\dots$ with probability $1$?

Question

On a "bottom" disk of area $A$, we place "top" disks of areas $1,\frac12,\frac13,\cdots$ such that the centre of each top disk is an independent uniformly random point on the bottom disk.

Find the maximum value of $A$ such that the bottom disk will be completely covered by the top disks with probability $1$, or show that there is no maximum.

The harmonic series diverges, but the problem here is that the top disks overlap, so it is not clear to me whether a bottom disk of a given area will be completely covered by the top disks, with probability $1$.

I made a desmos graph to help visualise the disks.

(This question was inspired by a question about rain droplets falling on a table.)

Answer 1

EDIT: The second to last line in my answer is flawed, as pointed out by @Dominik Kutek.

---

Consider a fixed point on the bottom disk. The probability that it is covered by the top disk of area $\frac{1}{k}$, is at least $\frac{1}{2kA}$. (The $2$ is there because the fixed point might be near the edge of the bottom disk.)

So the probability that the fixed point is not covered by the top disk of area $\frac{1}{k}$, is less than or equal to $1-\frac{1}{2kA}$.

So the probability that the fixed point is not covered by any of the top disks, is less than or equal to

$$\prod\limits_{k=1}^\infty\left(1-\frac{1}{2kA}\right)=\exp \sum\limits_{k=1}^\infty \ln \left(1-\frac{1}{2kA}\right)\le \exp \sum\limits_{k=1}^\infty\left(-\frac{1}{2kA}\right)=0$$

So for any value of $A$, every fixed point on the bottom disk will be covered with probability $1$.

So for any value of $A$, the probability that there will be an uncovered region of positive area, is $0$.

So for any value of $A$, the probability that the bottom disk will be completely covered, is $1$.

Answer 2

$\newcommand{\bB}{\mathbf{B}}$ $\newcommand{\PP}{\mathbb{P}}$ $\newcommand{\EE}{\mathbb{E}}$ $\newcommand{\Var}{\text{Var}}$ $\newcommand{\Cov}{\text{Cov}}$

Update: It looks like the case $A > 1$ is essentially contained in Proposition 11.5 of Kahane's book Some Random Series of Functions. The proof given there is much more beautiful, utilizing the second moment method in a very simplistic yet ingenious way.

More specifically, let $S_N$ be the area remaining after placing the first $N$ balls. Then Kahane used the inequality $$\PP(S_N \neq 0) \geq \frac{\EE[S_N]^2}{\EE[S_N^2]}.$$ One can compute that $\EE[S_N]$ grows like $N^{-1/A}$, while $\EE[S_N^2]$ grows like $N^{-1/2A}$. So this shows that $\PP(S_N \neq 0)$ is lower bounded by a constant.

---

By $\odot(p, r)$, I mean the closed disk centered at $p$ of radius $r$.

I believe we can argue that when $A < 1$ such covering happens with probability $1$, and when $A > 1$ such covering happens with probability less than $1$. I don't have an answer when $A = 1$.

Throughout, let $T_1, T_2, \cdots$ denote the "top disk", with $T_i = \odot(t_i, \frac{1}{\sqrt{\pi i}})$. Let $B$ denote the "bottom disk". Assume $B$ is centered at the origin $0$.

---

The part when $A < 1$ has a relatively straightforward proof. The idea is to discretize Dan's original answer.

Let $E_N$ denote the event that the first $N$ circles cover the bottom disk. It suffices to show that $$\lim_{N \to \infty} \PP(E_N) = 1.$$ To prove this, we take an optimal $(\sqrt{4\pi N})^{-1}$-net inside the bottom disk, which is defined as the largest set of points $\bB = \{b_1, \cdots, b_k\}$ inside the bottom disk that are at distance at least $\frac{1}{\sqrt{4\pi N}}$ from each other. Here are two facts about such nets

1. The disks $B_i = \odot(b_i, \frac{1}{\sqrt{4\pi N}})$ cover the entire bottom disk.

2. The disks $B_i' = \odot(b_i, \frac{1}{\sqrt{16\pi N}})$ are disjoint.

Let $E_{iN}$ denote the event that circle $B_i$ is completely covered. To carry out the analysis below, we use a trick known as dyadic partitioning: for each $0 \leq k \leq \log_2 N$, let $\bB_k$ denote the points in $\bB$ at distance between $[2^{-k-1}, 2^{-k}]$ from the boundary of the base circle, with $\bB_{\log_2 \sqrt{N}}$ also including all the points in $\bB$ at distance less than $\sqrt{N}^{-1}$ from the boundary of the base circle.

Let $b_i$ lies in $\bB_k$. Note that for each $1 \leq j \leq N$, the top disk $T_j$ covers $B_i$ completely iff $t_j$ lies in $C_{ij} = \odot(b_i, \frac{1}{\sqrt{\pi j}} - \frac{1}{\sqrt{4\pi N}})$.

We now need to understand the intersection between $C_{ij}$ and the bottom disk $B$. Note that $C_{ij}$ has radius at most $\frac{1}{\sqrt{\pi j}}$, so when $j$ is larger than a constant, its intersection with the base circle is at least $1/2 - O(j^{-1})$ the area of the whole circle. Furthermore, when $j \geq 2^{2k}$, the entire $C_{ij}$ is contained in the base circle. We can write this as $$\text{Area}(C_{ij} \cap B) \geq \begin{cases} (1/2 - O(j^{-1})) \left(\frac{1}{\sqrt{j}} - \frac{1}{\sqrt{4N}}\right)^2, j < 2^{2k} \\ \left(\frac{1}{\sqrt{j}} - \frac{1}{\sqrt{4N}}\right)^2, j \geq 2^{2k} \end{cases}.$$ So we conclude that $$\mathbb{P}(\overline{E_{iN}}) \leq \prod_{j = 1}^N (1 - \PP(B_i \subset T_j)) = \prod_{j = 1}^N \frac{A - \text{Area}(C_{ij} \cap B)}{A} \leq \exp\left(- A^{-1}\sum_{j = 1}^N \text{Area}(C_{ij} \cap B)\right).$$ We analyze the sum as follows $$\sum_{j = 1}^N \text{Area}(C_{ij} \cap B) \geq \sum_{j = 1}^{2^{2k}} (1/2 - O(j^{-1})) \left(\frac{1}{\sqrt{j}} - \frac{1}{\sqrt{4N}}\right)^2 + \sum_{j = 2^{2k} + 1}^N \left(\frac{1}{\sqrt{j}} - \frac{1}{\sqrt{4N}}\right)^2.$$ We need to understand this asymptotically. Fortunately, it is not too hard to check that $$\sum_{j = 1}^{2^{2k}} (1/2 - O(j^{-1})) \left(\frac{1}{\sqrt{j}} - \frac{1}{\sqrt{4N}}\right)^2 \geq \frac{1}{2} \log(2^{2k}) - O(1).$$ $$\sum_{j = 2^{2k} + 1}^N \left(\frac{1}{\sqrt{j}} - \frac{1}{\sqrt{4N}}\right)^2 \geq \log(N / 2^{2k}) - O(1).$$ So, substituting this back in, we conclude that $$\mathbb{P}(\overline{E_{iN}}) = O\left(\frac{2^{k / A}}{N^{1/A}}\right).$$ We now use the union bound on these events. Using dyadic summation, we need to estimate $$\sum_{b_i \in \bB_k} \mathbb{P}(\overline{E_{iN}}) = O\left(|\bB_k| \frac{2^{k / A}}{N^{1/A}} \right).$$ We can estimate $|\bB_k|$ using the second property of nets above. The circles $B_i' = \odot(b_i, \frac{1}{\sqrt{16\pi N}})$ are disjoint, and they must be contained in a ring of width $O(2^{-k})$ around the boundary of $B$. So we conclude that $$|\bB_k| = O(N 2^{-k}).$$ Thus, we conclude that $$\sum_{b_i \in \bB_k} \mathbb{P}(\overline{E_{iN}}) = O\left(\frac{2^{k(1/A - 1)}}{N^{(1/A - 1)}} \right).$$ Finally, we have $$\mathbb{P}(\overline{E_{N}}) \leq \sum_{k = 0}^{\log_2 \sqrt{N}} \sum_{b_i \in \bB_k} \mathbb{P}(\overline{E_{iN}}) \leq O\left(\sum_{k = 0}^{\log_2 \sqrt{N}} \frac{2^{k(1/A - 1)}}{N^{(1/A - 1)}}\right).$$ We find that each sum inside the big $O$ is $O(N^{-(1/A - 1) / 2})$. So we conclude that $$\mathbb{P}(\overline{E_{N}}) = O(\log N \cdot N^{-(1/A - 1) / 2}).$$ Thus $$\lim_{N \to \infty} \mathbb{P}(\overline{E_{N}}) = 0$$ as desired.

---

The part when $A > 1$ is more difficult. My idea is to show that with nonzero probability, after we have placed disks $T_1,T_2,\cdots,T_N$, the uncovered region contains many disjoint, microscopic disks.

To make the rigorous, let $K = 10^{10}$ and $Q = K^{A / (A - 1)}$. We consider the following event:

$E_t$: For each $Q \leq s \leq t$ the following holds. After we have placed $T_1, \cdots, T_{Q^s}$, we can find $2^s$ closed disks of area $Q^{-s}$ inside $\odot(0, 0.1)$, such that all of them are completely uncovered, and each pair of these disks are at a distance at least $2\pi^{-1/2}Q^{-s/2}$ apart from each other. Furthermore, if $U_s$ denotes the union of these disks, then $U_s \subset U_{s - 1}$.

Then my main observation is

Lemma: Assume $t \geq Q$. Condition on the placement of disk $T_1, \cdots, T_{Q^t}$, and suppose $E_t$ happens. Then the probability that $E_{t + 1}$ happens is at least $1 - \frac{Q}{2^t}$.

Proof: The main method we use to prove this is called the second moment method.

Let $B_1, \cdots, B_{2^t}$ be the $2^t$ disks of area $Q^{-t}$ inside $\odot(0, 0.1)$, such that all of them are uncovered, and each pair of these disks are at a distance at least $2\pi^{-1/2}Q^{-t/2}$ apart from each other.

It is not hard to show that, in each $B_i$, we can fit at least $R = \lceil{Q / 100\rceil}$ disks $B_{i1}, \cdots, B_{iR}$ inside $B_i$, such that they have area $Q^{-t-1}$ each and are distance at least $2\pi^{-1/2}Q^{-(t + 1)/2}$ apart from each other. Let $b_{ij}$ be the center of $B_{ij}$. Let $I_{ij}$ be $1$ if none of the disks $T_{Q^t + 1}, \cdots, T_{Q^{t + 1}}$ touch $B_{ij}$, and $0$ otherwise.

We first compute the expectation of $I_{ij}$. Note that for each $k \in [Q^t + 1,Q^{t + 1}]$, $T_{k}$ touches $B_{ij}$ if and only if $t_k$ lies in a circle $C_{ijk}$ of radius $\pi^{-1/2}(k^{-1/2} + Q^{-(t + 1) / 2})$ centered at $b_{ij}$. Note that we assumed that $B_{ij}$ are all far away from the boundary of $B$. So we have $$\PP(T_k \text{ touch }B_{ij}) = \frac{1}{A} \left(k^{-1/2} + Q^{-(t + 1) / 2}\right)^2.$$ Thus, we have $$\EE[I_{ij}] = \prod_{k = Q^t + 1}^{Q^{t + 1}}\left(1 - \frac{1}{A} \left(k^{-1/2} + Q^{-(t + 1) / 2}\right)^2\right).$$ Before we simplify this, we compute the covariance of $I_{ij}$ and $I_{i'j'}$ when $i \neq i'$. Note that by the separation condition on $B_i$ and $B_{i'}$, the circles $C_{ijk}$ and $C_{i'j'k}$ are disjoint. So we have $$\PP(T_k \text{ touch }B_{ij}\text{ or }B_{i'j'}) = \frac{2}{A} \left(k^{-1/2} + Q^{-(t + 1) / 2}\right)^2.$$ Thus we have $$\EE[I_{ij} I_{i'j'}] = \prod_{k = Q^t + 1}^{Q^{t + 1}}\left(1 - \frac{2}{A} \left(k^{-1/2} + Q^{-(t + 1) / 2}\right)^2\right).$$ The crucial observation is that we can, using the relation $1 - 2x \leq (1 - x)^2$, compute that $$\EE[I_{ij} I_{i'j'}] \leq \EE[I_{ij}] \EE[I_{i'j'}].$$ So we conclude that $$\text{Cov}(I_{ij}, I_{i'j'}) \leq 0.$$ In other words, if a $T_k$ does not cover $I_{ij}$, it is more likely to cover $I_{i'j'}$. This is crucially what makes the second moment argument work! We can now estimate the expectation $\EE[I_{ij}]$. Recall $$\EE[I_{ij}] = \prod_{k = Q^t + 1}^{Q^{t + 1}}\left(1 - \frac{1}{A} \left(k^{-1/2} + Q^{-(t + 1) / 2}\right)^2\right).$$ Note $\left(k^{-1/2} + Q^{-(t + 1) / 2}\right)^2 = k^{-1} + 2 k^{-1/2}Q^{-(t + 1) / 2} + Q^{-(t + 1)}$, so $$\EE[I_{ij}] \geq \prod_{k = Q^t + 1}^{Q^{t + 1}}\left(1 - \frac{1}{A}(k^{-1} + 2 k^{-1/2}Q^{-(t + 1) / 2} + Q^{-(t + 1)})\right).$$ Using the estimate $1 - x \geq e^{-x-x^2}$ when $x \leq 1/2$, we get $$\EE[I_{ij}] \geq \exp\left(-\sum_{k = Q^t + 1}^{Q^{t + 1}}\frac{1}{A}(k^{-1} + 2 k^{-1/2}Q^{-(t + 1) / 2} + Q^{-(t + 1)}) + 4k^{-2}\right).$$ Now using familiar results about Harmonic series, we conclude that $$\EE[I_{ij}] \geq \exp\left(-\frac{1}{A} \log Q - 10\right) = e^{-10} Q^{-1/A}.$$ Now, let $$X = \sum_{i, j} I_{ij}.$$ There are $R 2^i$ terms in this sum. By linearity of expectations, we have $$\EE[X] \geq e^{-10} Q^{-1/A} R 2^t \geq 100^{-1} e^{-10} Q^{1-1/A} 2^t \geq 2^{t + 2}.$$ We note that $$\Var[X] = \sum_{i,j,i',j'} \Cov[I_{ij}, I_{i'j'}].$$ The vast majority of terms in this sum has $i \neq i'$! We have $$\sum_{i,j,j'} \Cov[I_{ij}, I_{ij'}] \leq \sum_{i,j,j'} \EE[I_{ij}] \leq R \EE[X].$$ And $$\sum_{i,j,i',j': i\neq i'} \Cov[I_{ij}, I_{i'j'}] \leq 0.$$ So we have $$\Var[X] \leq R \EE[X].$$ Our hard work has finally paid off! By Chebyshev's inequality, recalling that $\EE[X] \geq 2^{t + 2}$, we have $$\PP[X < 2^{t + 1}] \leq \frac{\Var[X]}{(\EE[X] - 2^{t + 1})^2} \leq \frac{4R\EE[X]}{\EE[X]^2} \leq \frac{4R}{\EE[X]} \leq \frac{4R}{2^t}.$$ If $X \geq 2^{t + 1}$, then $E_{t + 1}$ happens, as desired. We have completed the proof of the lemma.

Note that $E_Q$ happens with non-zero probability, since it happens whenever the first $Q^Q$ circles all lie in a semi-circle of $B$. The lemma tells us that $$\PP(E_{i + 1}) \geq \PP(E_i) \cdot \left(1 - \frac{Q}{2^i}\right).$$ So telescoping gives $$\PP(E_i) \geq \PP(E_Q) \cdot \prod_{Q \leq j \leq i} \left(1 - \frac{Q}{2^j}\right).$$ Thus we have $$\PP(\cap_{i = Q}^\infty E_i) \geq \PP(E_Q) \cdot \prod_{j = Q}^\infty \left(1 - \frac{Q}{2^j}\right) > 0.$$ Finally, if $\cap_{i = Q}^\infty E_i$ happens, then the circle is not covered (thanks to Cantor's intersection theorem). So the circle is not covered with non-zero probability as desired.