11
$\begingroup$

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.

enter image description here

$\endgroup$
  • 5
    $\begingroup$ related : math.stackexchange.com/questions/176383/… $\endgroup$ – mercio May 30 '14 at 20:49
  • 1
    $\begingroup$ I would guess it's $O(N^2 \log N)$ since it's effectively a continuous version of the coupon collector problem. $\endgroup$ – p.s. May 30 '14 at 20:59
  • 1
    $\begingroup$ @mjqxxxx's answer at mercio's link gives a simple way to bound $\mathbb E[T]$ that is easy to adapt to the case of squares (consider uniform square grids of side length $1/(2N)$ and $1/N$ respectively for upper and lower bounds). In any case, both bounds are $O(N^2\log N)$. $\endgroup$ – user856 May 30 '14 at 21:00
  • $\begingroup$ Ah! Makes sense the coupon collector's problem should come into this. $\endgroup$ – abnry May 30 '14 at 21:01
  • $\begingroup$ Moreover, the accepted answer at @mercio's link makes a strong case for the coefficient: the result should be $N^2 \log N^2 = 2N^2 \log N$ to leading order. $\endgroup$ – mjqxxxx Jun 9 '14 at 20:50
1
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ Can you explain the reformulation in more detail? It feels like you are flattening the problem to 1D and at the same time reducing it to the integers. I could maybe be convinced you can convert this to a 1D problem, but I am doubtful you can avoid everything but the integers. $\endgroup$ – abnry May 31 '14 at 0:36
  • 1
    $\begingroup$ For instance, you are taking the union of a sequence? That doesn't make sense. What is $m$? In essence you seem to have taken the coupon collectors problem and multiplied by $(N+1)$. $\endgroup$ – abnry May 31 '14 at 0:38
  • $\begingroup$ The second part of your first comment is spot on -- just because each integer grid point is covered, that does not imply that the space between them is covered. I will be modifying my answer, and now it is just bounds rather than a closed form answer. $\endgroup$ – Mark Fischler Jun 9 '14 at 19:13

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.