Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
Cross-posted on MSE: math.stackexchange.com/questions/176383/… –  Ilya Jul 29 '12 at 8:18
    
Yes, thank you Ilya, I forgot to mention. I posted it here because there haven't been any responses on MSE so far. –  Nicolas Kim Jul 29 '12 at 8:21
8  
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. –  Angelo Jul 29 '12 at 8:25
1  
Train your patience. I agree 100% with Angelo's comment. –  Martin Brandenburg Jul 29 '12 at 9:58
1  
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. –  Douglas Zare Jul 29 '12 at 10:04
show 3 more comments

2 Answers 2

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.

share|improve this answer
    
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. –  fedja Jul 30 '12 at 13:08
    
@fedja: See my answer at math.SE, where I derive an expansion up to $O(R^2)$ and compare with simulation results. –  joriki Aug 7 '12 at 10:46
    
@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? –  mjqxxxx Aug 7 '12 at 16:46
    
@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). –  joriki Aug 7 '12 at 23:08
add comment

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

share|improve this answer
1  
Of course, this assumes that the table is so cold that the water freezes solid immediately. –  Douglas Zare Jul 29 '12 at 11:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.