Expected time to completely cover a square with randomly placed smaller squares

Suppose I have the unit square $[0,1]^2$ and I choose a point $(x_1, y_1)$ randomly in a uniform manner inside $[0,1]^2$ and draw a filled in square of side length $1/N$ with center $(x_1, y_1)$. And suppose I do this again and again, picking points $(x_n, y_n)$ and filling in squares with side length $1/N$. What is the expected time $T(N)$ it takes to completely fill in the unit square?

Restated somewhat more formally, if $S_N(x,y) = [x-2/N, x+2/N] \times [y-2/N, y+2/N]$, then I am asking for $X_i$, $Y_i$, I.I.D. and uniformly distributed and $T$ the minimal $n$ such that $[0,1]^2 \subseteq \cup_{i=1}^n S_N(x_i, y_i)$, what is the expected value of $T$?

I'll probably be happier with a less technical answer at the expense of nailing down the exact function $E[T(N)]$. Clearly there is the lower bound $E[T(N)] \geq N^2$. But, this problem may be simple enough, compared to the circle problem mentioned in the comments, to get an exact solution.

P.S. I was motivated to ask this question from some fooling around I have done with programming. Specifically, this image which is composed in the manner just described but using many, many circles. Notice the gaps in the circles even though there is a lot of overlap elsewhere.

Solution 1:

We can get uppper and lower bounds on the expected number of small squares needed to cover an $N \times N$ large square. For the lower bound:

Consider the set $K$ of points $(k_x,k_y)$ with $k_x$ and $k_y$ both integers in $[0,N]$. There are $(N+1)^2$ such points. Any complete covering will at least cover all of the points in $K$, and any placed small square will with almost surely (that is, with probability 1) cover exactly one point in $K$. So a lower bound for the problem reduces to the following:

Given a sequence $s_i$ of integers $n_i$ uniformly random in interval $J \equiv [1,j]$. Find the expected value $T_j$ of the minimum value of $i$ such that $\bigcup s_i = J$.

We can find that expected value by looking at the function $t_j(p)$, the expected time to cover the set $J$ if $p$ of the integers are already covered. (Thus $T_j = t_j(0)$. It takes at average $\frac{j}{j-p}$ tries to hit on a number that was not among those already covered. So $t_j(j-1) = j$ and for all $0 \leq p < j-1$ $$ t_j(p) = \frac{j}{j-p} + t_j(p+1) $$ So $$ t_j(p) = \sum_{q=p}^{j-1} \frac{j}{j-q} = j \sum_{q=p}^{j-1} \frac{1}{j-q} = j \sum_{i=1}^{j-p} \frac{1}{i} = j H_{j-p} $$ where $H_n$ is the harmonic sum $\frac{1}{1}+\frac{1}{2} +\ldots + \frac{1}{n}$.

Notice that by isolating the effect we care about of any one small square to only one point in $K$, we have changed a harder 2-D problem to an easier 1-D problem.

However, those $1\times 1$ squares, while covering all the grid points in $K$, might leave gaps in points between the grid points.
Thus a lower bound for the expected time for covering the square is $$ T_{(N+1)^2} = t_{(N+1)^2}(0) = (N+1)^2 H_{(N+1)^2} $$ which grows as $2N^2 \log N$.

Now to obtain an upper bound:

Consider the set $M$ of points $\left(\frac{m_x}{2}+\frac{1}{4}, \frac{m_x}{2}+\frac{1}{4}\right)$ with $m_x$ and $m_y$ both integers in $[0,2N-1]$. There are $(2N)^2$ such points. Any unit square will with probability 1 entirely cover the $\frac{1}{2}\times\frac{1}{2}$ square centered a the point in $M$ nearest the unit square's center. Thus if every member of $M$ is covered by a square for which it is the closest to the center, then the entire $N\times M$ square is covered.

So an upper bound for the problem reduces to the same problem of finding the expected covering time for a set of integers, only this time we need $T_{4N^2}$. Thus an upper bound for the expected time for covering the square is $$ T_{4N^2} = 4N^2 H_{4N^2} $$ which grows as $8N^2 \log N$.

So as you expected, the expectation of the covering time grows as $N^2 \log N$, and as a matter of fact, the coefficient is between $2$ and $8$.