Here is a nice math problem I encountered recently.
N painters arrive at random positions around a circular fence. Each paints the section of fence between them self and the nearest neighboring painter. As a result of this curious procedure some sections of fence are painted twice and some are not painted at all. In the limit as N goes to infinity what fraction of the fence on average will be painted (at least once)?
Actually as originally posed the fence was not circular which doesn't change the limit but is not as easy to deal with.
You can also ask the same question for the case where each painter paints the section of fence between them self and the farther of the two adjacent painters.
Raw data: A cautionary tale
7 hours ago
The fraction is equal to 1 minus the probability that the sum of 2 exponentially distributed variables is greater than both of 2 other exponentially distributed variables, where all 4 variables are independent, and have the same "rate" parameter. I.e. it is 1 minus the probability that [(a + b) > c and (a + b) > d], where a, b, c, and d are independent exponentially distributed variables with the same rate parameter. This gives roughly 0.39.
ReplyDeleteThis is of course equivalent to 1 - Prob [(a+b) > c]^2, where a, b, and c are exponentially distributed variables with the same rate.
ReplyDeleteActually, strike that last comment, its wrong.
ReplyDelete.39 is numerically correct (although I don't quite follow the argument in the first comment). However it is possible to find an exact answer.
ReplyDeleteI thought about this problem some and got Jonathan's result in terms of the exponentially distributed variables, but, being math challenged, was not sure how to compute the actual result. Now that James confirms it's correct, I'm willing to risk describing a little of my thought process. The key is to realize that if you pick a random point to consider, this additional point is really no different from any of the already existing N painter points (in the limit of large N, the additional point does not change the point density). This was non-intuitive to me at first and has interesting implications. For example, if buses leave a bus stop at random times (Poisson process, exponentially distributed) and you arrive at the bus stop at a random time, then your expected wait time is the same as if you get off an arriving bus and wait for the next bus. The fact that you have a shorter wait time than that counted from the previous bus is compensated for by the fact that you are more likely to arrive at one of the longer interval between buses. Anyway, for the new point on the fence to not be painted, it has to land in a section such that the segments to its right and left (call them a and b) total to more than either of the adjoining segments (c and d). This is exactly Jonathan's condition.
ReplyDeletePeter Shearer
Peter, that is the same logic that I used.
ReplyDeleteAlso, I have now calculated the probability explicitly and arrived at an answer of 7/18. This is, as mentioned above, 1 - prob[(a + b)>c and (a + b) > d], or equivalently 1 - prob[(a+b) > max(c,d)], where all variables are independent exponentially distributed variables with the same rate parameter r. We can can calculate prob[(a+b) > max(c,d)] as the integral of the pdf of (a+b) multiplied by the cdf of max(c,d), from 0 to infinity. (a+b) has a pdf of r^2*x*exp(-r*x). max(c,d) has a cdf of (1-exp(-r*x))^2. Thus the answer is 1 - the integral of r^2*x*exp(-r*x)*(1-exp(-r*x))^2 from 0 to infinity, which is 7/18.
The second part of the problem has not been mentioned in previous comments. The expression for the result in that case is 1 - the integral of r^2*x*exp(-3*r*x) from 0 to infinity, which is 8/9.
ReplyDelete7/18 and 8/9 are correct. The approach used by Jonathan and Peter is not the way I solved the problem but appears about as simple in the limit. However my approach will also give the exact answer for each finite value of n (for the case of a circular fence).
ReplyDeleteUpon rereading, my statement of the problem appears potentially ambigious in that it may not be totally clear that all the painters arrive before they start painting. Fortunately this doesn't seem to have confused anybody.
My approach to the original problem may be similar to James's, though I don't know whether all its assumptions hold for finite n:
ReplyDelete1) On a unit circle with n painters, the density function of segment length is f(s) = (n-1)(1-s)^(n-2)
2) The unpainted segments are those longer than both adjacent segments. So as n -> infinity, the number of unpainted segments is n/3 (by independence and symmetry)
3) The avg length of these unpainted segs is, by symmetry,
L = [integral over x>y>z of xf(x)f(y)f(z)] / pr{x>y>z}.
L's denominator is 1/6 by symmetry. A friend's Mathematica evaluates L's numerator as
(11n^2 - 16n + 6) / [6n(3n-2)(2n-1)]
which -> 11/36n as n -> infinity
4) So, L-> (11/36n)/(1/6) = 11/6n as n -> infinity
5) So, the total unpainted seg length is (n/3)(11/6n) = 11/18, and the total painted length is 1-(11/18)=7/18.
I peeked at the numerical answer before finishing the above calc. Now to try to understand other commenters' solutions, which look like they may be slicker than the above triple integral approach..