9
$\begingroup$

Suppose you have a circular table of radius $R$. This table has been left outside, and it begins to rain at a constant rate of one droplet per second. The drops, which can be considered points as they fall, can only land in such a way such that they impact the surface of the table. Once they strike the table, they form a puddle of radius $r$, centered at their point of impact. What is the expected number of droplets it takes to cover the table in water?

The answer should be left in terms of $R$ and $r$.

I have tried decomposing the problem by considering only the 1-dimensional case with line segments, but even its solution has eluded me. A potential starting point could be the discrete case of marbles falling into buckets.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Cross-posted on MSE: math.stackexchange.com/questions/176383/… $\endgroup$
    – SBF
    Commented Jul 29, 2012 at 8:18
  • $\begingroup$ Yes, thank you Ilya, I forgot to mention. I posted it here because there haven't been any responses on MSE so far. $\endgroup$
    – Nicolas Kim
    Commented Jul 29, 2012 at 8:21
  • 8
    $\begingroup$ After a WHOLE hour there have been no answers on MSE yet? And you homework is due very soon, I suppose. I voted to close. $\endgroup$
    – Angelo
    Commented Jul 29, 2012 at 8:25
  • 1
    $\begingroup$ Train your patience. I agree 100% with Angelo's comment. $\endgroup$
    – Martin Brandenburg
    Commented Jul 29, 2012 at 9:58
  • 1
    $\begingroup$ The discrete version is called the coupon collector problem and the answer is well known to be $n(1+1/2+...+1/n)$ when there are $n$ buckets. However, the continuous versions seem interesting. $\endgroup$
    – Douglas Zare
    Commented Jul 29, 2012 at 10:04

2 Answers 2

Reset to default
6
$\begingroup$

One can get upper and lower bounds by reducing to the coupon-collector's problem. Let's say for simplicity that $r=1$. If we divide the surface of the table into squares of side 2, then in order to cover the table, we must have at least one droplet in each square. Since there will be about $\pi R^2 /4$ squares, we get a lower bound of roughly $(\pi R^2 /4)\log(\pi R^2 /4)$. Conversely, if we divide the surface into squares of side $1/\sqrt{2}$ so that the diagonal is 1, then to cover the table it suffices to have at least one droplet in each square, and we get an upper bound of roughly $(2\pi R^2)\log(2\pi R^2)$.

I know that a substantial number of papers have been devoted to this sort of problem, so I guess there are more precise results available, but I don't have a reference off the top of my head.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Actually, if you do this argument more carefully, you get the right asymptotics $2R^2\log R$ as $R\to\infty$. However, I doubt that the exact value is possible to find. $\endgroup$
    – fedja
    Commented Jul 30, 2012 at 13:08
  • $\begingroup$ @fedja: See my answer at math.SE, where I derive an expansion up to $O(R^2)$ and compare with simulation results. $\endgroup$
    – joriki
    Commented Aug 7, 2012 at 10:46
  • $\begingroup$ @fedja: The lower bound can be improved to $2R^2 \log R$ and the upper bound can be improved to about $9.68 R^2 \log R$ by using hexagons instead of squares; do you have reason to think that the lower bound is tight? $\endgroup$
    – mjqxxxx
    Commented Aug 7, 2012 at 16:46
  • $\begingroup$ @mjqxxxx: I've now updated my answer at math.SE to give a more rigorous proof of the asymptotic $2R^2\log R$ behaviour (which shows that the lower bound is tight). $\endgroup$
    – joriki
    Commented Aug 7, 2012 at 23:08
3
$\begingroup$

The expected number of droplets it takes is the sum of the probabilities that $n$ droplets don't suffice for $n \ge 0$. For the $1$-dimensional version of the problem, you can determine this probability by inclusion-exclusion.

Geometrically, the set of $n$ impact locations corresponds to a point in a simplex with $n+1$ vertices by using barycentric coordinates, and the density is uniform. Two of the vertices are special because they correspond to the first and last segments, which have to have length at most $r$ instead of $2r$ for all points to be covered. (You can avoid this complication by covering a circle instead.) The probability that something is left uncovered is the normalized volume of the points within $R-2r$ of at least one regular vertex (by the $L^1$ distance), or within $R-r$ of one of the two special vertices.

$$P(n~ \text{cover})= \sum_{i=0}^{n-1} \sum_{j=0}^2 (-1)^{i+j}{n-1 \choose i}{2\choose j} \max(0,(1-jr/R-2ir/R)^n)$$

so, the expected number of droplets it takes to cover a line segment is

$$\sum_{n=0}^\infty \bigg(1-\sum_{i=0}^{n-1} \sum_{j=0}^2 (-1)^{i+j}{n-1 \choose i}{2\choose j} \max(0,(1-jr/R-2ir/R)^n)\bigg).$$

For a particular value of $r/R$, a fixed number of terms are nonzero so this series can be simplified. For example, if $r/R = 1/3$, then the expected value is

$$\sum_{n=0}^\infty \bigg(1 - (1^n - (n-1)(\frac13)^n - 2(\frac23)^n + (\frac13)^n)\bigg) =\frac{15}{4}.$$

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Of course, this assumes that the table is so cold that the water freezes solid immediately. $\endgroup$
    – Douglas Zare
    Commented Jul 29, 2012 at 11:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .