|
|
|
|
|
|
|
|
CTK Exchange
Sam
guest
|
May-21-04, 01:40 PM (EST) |
|
"Birds on a Wire"
|
The Birds on a Wire question you have on this site is quite amazing, and the applet you have set up does a really good job of arriving at the answer through brute force. Is the formal proof that is hinted at in the question anywhere to be found? I haven't been able to make any headway at all on it. Thanks! Sam |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
alexb
Charter Member
1952 posts |
May-21-04, 02:07 PM (EST) |
|
1. "RE: Birds on a Wire"
In response to message #0
|
>The Birds on a Wire question you have on this site is quite >amazing, For the curious: https://www.cut-the-knot.org/Curriculum/Probability/BirdsOnWire.shtml >and the applet you have set up does a really good >job of arriving at the answer through brute force. Is the >formal proof that is hinted at in the question anywhere to >be found? I haven't been able to make any headway at all on >it. I believe that at the time I had a pretty good idea of how to approah the problem. I never went through with it. Mark Galecki, who contributed the problem, was probably awaiting for a request for a solution, which had never arrived ... |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
sfwc
Member since Jun-19-03
|
May-22-04, 11:24 AM (EST) |
|
2. "RE: Birds on a Wire"
In response to message #0
|
The following argument, although non-rigorous, gives the right answer and shows why it is true (and I guess with a bit of effort you could make it rigorous). Consider a wire with lots of birds on it, and scale it up so that there is one bird per unit length. Consider a bird at b. I shall assume that b is far enough away from the ends that they make no difference. For any interval , then number of birds in that interval has about a poisson distribution with parameter x. So in particular the interval is empty with probability 1 - exp(-x). So the distance to the nearest bird to the right has an exponential distribution with parameter 1. The same may be said for the nearest bird to the left. So the distance to the nearest bird overall has an exponential distribution with parameter 1+1 = 2. W.l.o.g. the neasrest bird, at b' satisfies b' - b = x > 0. Then b is the nearest bird to b' with probability exp(-x). Give bird b a paintbrush, and let it paint half of the interval (b, b+x) if it is the nearest bird to b', and the whole interval otherwise. A simple combinatorial argument shows that if each bird on the wire does this, then the wire will be painted as in the question. So we are interested in the expected length painted by bird b since this is (after scaling) the required value. However, the comments in the first paragraph allow us to evaluate it as a simple integral: p = Int<0 to infinity, x * exp(-2x) * (1/2(exp(-x) + (1 - exp(-x)))dx> =Int<0 to infinity, x * (2*exp(-2x) - exp(-3x))dx> = 2/4 - 1/9 = 7/18 using Int = 1/(k^2)This value is 0.38888888..., which seems to fit with the results produced by the applet. I must admit, at first I thought the answer was going to be something nice like 1/e, but 7/18 is what the algebra gives. Thankyou sfwc <>< |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
Mark Huber
guest
|
May-24-04, 07:29 PM (EST) |
|
4. "RE: Birds on a Wire"
In response to message #0
|
Here's another way of thinking about it. Suppose that for a bird at position a on the wire we assign a random variable L_a that is the length of the yellow line to the left of a. So if a is closest to it's bird on the right, and if the bird to the left of a is closer to it's left bird, L_a = 0, otherwise it's some positive number. What is the probability that L_a is in some tiny little interval around h? Or in probability notation, P(L_a in dh) = ? There are two ways L_a can be close to h. One case is there is a bird at a - h, no bird in the interval (a-h,a), and no bird in (a,a + h). This occurs with probabilitty (1 - 2h)^{n-2} n dh. Another case is when there is a bird at a - h, no bird from (a - 2h,a), and at least one bird in (a,a+h). This occurs with probability ((1 - 2h)^{n-2} - (1 - 3h)^{n - 2}) n dh. To find the expected value of L_a, this probability can multiplied by h, then integrated for h from 0 to 1/2. This gives an expected value of about (7/18)(1/n). Since there are n birds, the total yellow line is then 7/18 in expectation. A variant of the Strong Law of Large Numbers then completes the proof that as the number of birds goes to infinity, the amount of line colored yellow is 7/18. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
Moshe Eliner
guest
|
Oct-18-04, 08:29 AM (EST) |
|
5. "RE: Birds on a Wire"
In response to message #0
|
here is another solution : lets pass through all birds, starting , say, from the left, stopping every fourth bird. I'll call this segments 4b.notice a delicate point : denote the shortest connecting segments sc (i.e. yellow lines) each 4b has 3 inner connecting segments (average 2). since : 1.the states of sc=1 and sc=3 force inner point positions on the neighboring 4b's. 2. on a uniform wire birds tend to have unfiorm distribution, hence inner point positions cannot be predefined. 3. so there cannot be sc=1 or 3 more than average. this implies that each 4b has on average sc=2. now it's enough to calulate the density when sc=2 : there are 3 possible sc=2's , but since one can rearrange segments inside the 4b, all have the same density, let's choose one of then e.g. the one with two shortes at first : integrate ydxdy: 1.y=1/2..2/3,x=2y-1..1-y 2.y=0..1/2,x=0..y this yields 7/108, but since the total integration area is 1/6,the result density is: 7/18 |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
Pierre Charland
Member since Dec-22-05
|
Dec-10-06, 08:15 AM (EST) |
|
14. "RE: Birds on a Wire"
In response to message #5
|
I had a hard time understanding this solution, until I realised we have to stop at every 3 birds (not 4).So a so-called 4b segment looks like this: A---------B---------------C............................D 0---------0---------------0............................0 0----x----0-------y-------0............1-x-y...........0 where we have x<=y (because we set them this way) and y<=1-x-y (or else C would be closer to D) we need the average value of (x+y) ```````````1/3 ``````````⌠`````⌠(1 - x)/2 ``````````|`````|`````````v dy dx ``````````⌡`````⌡x ```````````0 mean(v) ≔ ---------------------------- ```````````1/3 ``````````⌠`````⌠(1 - x)/2 ``````````|`````|`````````1 dy dx ``````````⌡`````⌡x ```````````0 mean(x) = 1/9 = 0.1111111111 mean(y) = 5/18 = 0.2777777777 mean(x + y) = 7/18 = 0.3888888888 (this is the answer) surprising to me, note that mean(x+y) = mean(x)+mean(y) (I have an image and a Derive file, but it's too big) (the preview of this message looks wrong, if you email me at pierrecharland@hotmail.com I will send you my original file) AlphaChapMtl |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
Pierre Charland
Member since Dec-22-05
|
Dec-15-06, 02:45 PM (EST) |
|
20. "RE: Birds on a Wire"
In response to message #16
|
My solution is a repeat of Moshe Eliner's solution. In Moshe Eliner's message, he says: "there are 3 possible sc=2's , but since one can rearrange segments inside the 4b, all have the same density, let's choose one of then e.g. the one with two shortest at first". This means: cosider a 4b segment with A,B,C,D the 4 birds on that segment. A.....B.....C.....D in a 4b, there are 3 sub-segments: AB,BC,CD. we choose 2 of them among AB,BC,CD, it could be {AB,BC},{AB,CD},{BC,CD} (the 3 possible sc=2's). By rearranging the choosen sub-segments, we make AB the shortest ones, and BC the other one. Calling AB=x, BC=y, we have x<=y. A.......B............C.....................D |--x--|----y----|.....(1-x-y)......| We set AD=1, so CD=(1-x-y). Of course 0<=x<=1 , 0<=y<=1, 0<=(x+y)<=1 Now by definition, the chosen segments are the shortest ones from each bird. If C's closest neighbor is D, then CD would be a chosen sub-segment. But it is not (AB and BC are the choosen sub-segments), so C's closest neighbor is B, (not D), so BC<=CD, so y<=(1-x-y). .. When we integrate later, we consider the full range 0<=x<=1 , 0<=y<=1, which is a square in the xy Plane. But with the constraints x<=y and y<=(1-x-y), a much smaller triangle is left. (check the attached .gif image, drawn with Derive-6)----------------------------------------------------------------- >>where we have x<=y (because we set them this way) >>and y<=1-x-y (or else C would be closer to D) >I'm having a bit of trouble following the argument at this >point. Could you explain this in a bit more detail? > >Thankyou > >sfwc ><><
AlphaChapMtl |
Attachments
https://www.cut-the-knot.org/htdocs/dcforum/User_files/4582b92d3d2597d5.gif
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
r eidelman
guest
|
Dec-24-04, 05:42 PM (EST) |
|
6. "RE: Birds on a Wire"
In response to message #0
|
here is a rough intuitive solution. lets find the probability that a segment between two birds is coloured we use 1 for coloured segment and 0 for uncoloured segment after 1 the next segment can be 1 or 0 after 0 the next segment must be 1 when the number of birds becomes infinitly large all the possible series of 0's and 1's give a probability of 1/fi for a segment to be coloured where fi = (1+ sqrt(5))/2 is the golden ratio. now lets find the average length of the short segment between two birds suppose all the segments are standard (with equal length) every line segment (that can contain infinitly many segments) is 1/fi coloured down to any scale. the length of a short segment is less than a standard segment and therefor the average length of a short segment is 1/fi of a standard segment (the average length of a long segment is 1+(1-1/fi)) now the wire is a <0,1> segment divided to infinitly many standard segment every segment is 1/fi coloured with probability 1/fi the wanted size of coloured part is S(0,1)<1/fi^2 dx> = x/fi^2 |0,1 = 1/fi^2 = 0.38196... |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
mr_homm
Member since May-22-05
|
Jul-01-05, 02:56 PM (EST) |
|
7. "RE: Birds on a Wire"
In response to message #0
|
I was recently looking at the solutions posted here to the bird on the wire problem, and was particularly struck by the third solution, which did not involve the notion of an exponential distribution at all. I found it'somewhat hard to follow, so I started looking at the assumptions behind the other solutions, to see why you could solve the problem without the exponential distribution. Here is the surprising result: part of the solution REALLY IS independent of the distribution, although the final answer does depend on the distrbution. Let L be the length of an interval between adjacent birds. Suppose that the P(L<x) = F(x) for an arbitrary cumulative probability function F. Then the density function f(x) = F'(x) gives the probability density for the interval to have length x. A given interval will be painted twice if it is "small" i.e. shorter that both its neighbors, once if "medium", i.e. shorter than one and longer than the other neighbor, and not painted if "big", i.e. longer than both neighbors. What is the probability of each case and its expected length? For the interval that is longer than its neighbors, the probability is integral_0^infinity(F(x)*F(x)*f(x))dx = integral_0^1(F^2)dF = 1/3. Similar calculations for the other two cases, using 1-F(x) in place of F(x) when we want the neighboring interval to be longer instead of shorter, give the same result. This is rather surprising in itself: regardless of the distribution, the probabilities P(big), P(medium), and P(small), are all exactly 1/3. The expected length of an interval that is longer than both neighbors is integral_0^infinity(x*F(x)*F(x)*f(x))dx/(1/3), which we integrate by parts (very carefully!): let u=x, and dv = (F(x))^2*f(x)dx = d((F(x))^3 - 1)/3. (We can choose any antiderivative we like when integrating by parts, and this one allows the u*v term to vanish at infinity.) Then we get eval_0^infinity(x*(F^3 - 1)) - integral_0^infinity(F^3-1)dx = integral_0^infinity(1-F^3)dx if F(x) approaches 1 sufficiently quickly for the eval term to vanish and the integral to converge. Let's call this number B (for "Big interval). A similar but simpler calculation shows that the expected length of an arbitrary interval (no conditions as to its size relative to its neighbors) gives integral_0^infinity(1-F)dx. Let's call this number A (for "Average interval). Since all but the "big" intervals are painted, the expected fraction painted is 1 - (B*P(Big))/A = 1 - B/(3A). When F(x) = 1- exp(-kx) is the exponential distribution, B = integral_0^infinity(3exp(-kx) - 3exp(-2kx) + exp(-3kx))dx = (3 - 3/2 + 1/3)/k = 11/(6k), while A = integral_0^infinity(exp(-kx))dx = 1/k. Therefore, the expected fraction painted is 1-(11/6k)/(3/k) = 1 - 11/18 = 7/18. A more detailed calculation shows that 2/18 if the length is painted twice (small intervals), 5/18 is painted once (medium) and 11/18 is unpainted (big intervals). Since these types of intervals occur with equal probability, this also shows that the ratio of mean sizes of small, medium, and big intervals is 2:5:11. Of course, if we took 1/3 of the intervals completely at random, we would expect them to cover 1/3 = 6/18 of the wire, so we can extend the ratio to include the overall average length: S:M:B:A = 2:5:11:6. Therefore, medium intervals are slightly shorter than the average length. --Stuart Anderson |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
|
alexb
Charter Member
1952 posts |
Jul-03-05, 05:53 AM (EST) |
|
9. "RE: Birds on a Wire"
In response to message #8
|
>I see that alexb has linked my post on this topic back to >the probability topic page. Why, I just love it. Hope you do not mind. >You should notice that the text doesn't print properly when >you access it from the probability/birdonwire page. Thank you. It is fixed now. Alex |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
mr_homm
Member since May-22-05
|
Jul-03-05, 01:57 AM (EST) |
|
10. "RE: Birds on a Wire"
In response to message #9
|
>>I see that alexb has linked my post on this topic back to >>the probability topic page. > >Why, I just love it. Hope you do not mind. > I am glad you liked it. I post here just for the fun of it (the best reason to study mathematics anyway, in my opinion), and the more people see my posts, the more fun it is. Please feel free to use anything I post anywhere on your site, in any form you like.By the way, further consideration shows that there is a non-probabilistic reason why the "small" and "big" intervals are equally numerous: If you look at the intervals in order from left to right, and make a plot of interval length L(n) vs. interval number n, then the small intervals appear as local minima, while the big intervals are local maxima. The medium intervals are points interior to monotonic regions of the graph. This means that the big and small intervals must alternate. There is no possibility of having two big or two small in a row. Therefore, the number of big and small intervals must differ by at most one. For a very large number of intervals, this forces P(big) = P(small). It doesn't of course prove that these probabilities are exactly 1/3. This is the sort of thing that makes some probability problems very interesting: if the theory is applied correctly, it must agree with facts we can prove by other considerations, yet if we don't happen to notice those other considerations, the probabilistic result looks very puzzling. One would expect, after all, that since the smaller intervals are more numerous than larger ones, the number of small intervals might exceed the number of big intervals. That they are equal seems coincidental when you look for an explanation within probability theory, because the really clear explanation is external to probability. Which brings up the next obvious question: is there a clear extra-probabilistic reason for the exact split of intervals into equal thirds? In other words, is there a structural reason why the medium intervals are exactly as numerous as the big intervals? I don't think it can be as simple as the reason for big and small being equinumerous, but I suspect that there is some structural reason (perhaps based on symmetry rather than alternation) because the 1/3 split holds for arbitrary probability distributions. Any ideas, anyone? --Stuart Anderson |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
alexb
Charter Member
1952 posts |
Jul-04-05, 08:02 AM (EST) |
|
11. "RE: Birds on a Wire"
In response to message #10
|
>Please feel free to use anything I post anywhere on >your site, in any form you like. Thank you. >This means that the big and small intervals must alternate. >There is no possibility of having two big Unless they are equal. > or two small in a row. Same here. But this does not affect the basic idea of the message. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
Moshe Eliner
guest
|
Jul-27-05, 09:28 AM (EST) |
|
12. "RE: Birds on a Wire"
In response to message #10
|
Hi Stuart, By some odd coincidence I stumbled into your write up,than I saw it wasn't So long ago,so I decided to clear thing up.
You had some trouble reading my solution,and at second look it's not so clear,I hope this will help: But first I word about my motivation for solving it, When I first saw this problem I thought it wasn’t too complex,per se,still It'seemed that every one had an “I would expect…” problem with it, which Drove them to a solution, in my opinion, unnatural to the problem. So I wanted to give a solution, that seemed to me more natural. Now for the solution itself. It’s composed of two parts: 1.dividing the birds into cells of 4 birds, and showing that this cells are the Same and independent of each other, so reducing the problem into a single 4 birds cell (e.g. 4b) problem. 2. a calculation, which is rather trivial, and probably you had no trouble with. So let me elaborate on my first move: Put an arrow on every fourth bird head (hopefully they wouldn't mind) pointing To it’s nearest neighbor, the number on left and right arrows should be the same. Now put arrows on the inner two birds, and use same argument. In other words, there is no favorite cell configuration. In calculating the density (e.g. average yellow line length) there is no need for Direction, every cell has, on average, 2 yellow segments, and so now we Can use my second move. Hope this helps. moshe
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
Pierre Charland
Member since Dec-22-05
|
Dec-10-06, 08:15 AM (EST) |
|
15. "RE: Birds on a Wire"
In response to message #12
|
From my understanding, you are putting an arrow on every 3rd bird, (not 4th)^.........................^......................^.......... 1........2........3.......4......5.......6.......7.......8.. so what you call a 4b look like this: 0........0........0.......0 with x and y defined this way: 0---------0---------------0............................0 0----x----0-------y-------0............1-x-y...........0 where x<=y and y<=1-x-y
AlphaChapMtl |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
sfwc
Member since Jun-19-03
|
Dec-12-06, 11:29 PM (EST) |
|
17. "RE: Birds on a Wire"
In response to message #10
|
>Which brings up the next obvious question: is there a clear >extra-probabilistic reason for the exact split of intervals >into equal thirds? In other words, is there a structural >reason why the medium intervals are exactly as numerous as >the big intervals? I don't think it can be as simple as the >reason for big and small being equinumerous, but I suspect >that there is some structural reason (perhaps based on >symmetry rather than alternation) You are right: There is a neat symmetry consideration which makes this clear. However, it does involve some basic probability.>because the 1/3 split >holds for arbitrary probability distributions. About this, I am not so sure. You seem to assume that the distribution of lengths the intervals can have is independent of position, and in particular that the distributions of the lengths of intervals adjacent to a given one are independent of the length of that given one. Of course, this is true for the uniform distribution in the original question. Here is a way to rephrase your argument which makes some of this reliance clearer, and gives 3 solutions to the original problem: For convenience, I shall work with a slightly different problem, where the wire is considered as a loop, with the two end posts replaced by a new bird. I shall suppose throughout that n - 1 other birds may sit on the loop, and that the distribution of each is uniform. Let X be the space of maps from <n-1> to <0, 1>, and let the function L:X->R take such a map to the length of wire coloured if the birds sit in those n places. So the desired value is the limit as n tends to infinity of E(L(f)). For any permutation σ on n elements, and any map f in X, let σ(f) be the new map produced by permuting the lengths of the intervals between successive birds with the permutation σ, keeping the order of the birds constant. If σ is a transposition of adjacent intervals, then on each subspace with the order of the birds constant, σ(f) is uniformly distributed in each variable. As X is spanned by these subspaces, and σ takes each such subspace into itself, σ(f) is uniformly distributed on X. But transpositions of adjacent intervals span the group of permutations, so for any permutation σ, σ(f) is uniformly distributed. This is the desired symmetry property. In particular, for any fixed σ, E(L(f)) = E(L(σ(f))). So this is also true if σ is chosen at random from the group S(n), as well as the positions of the birds being chosen at random. Now choose an interval at random and a permutation at random. Consider the interval and it's neighbours after the permutation. For n>2, this amounts to choosing three different intervals at random. So the probability that the middle one is the longest is 1 in 3, and similarly the probability that the middle one is the shortest is also 1 in 3. From now on, again for convenience, I will work with M = 1-L, the total length of the big intervals, rather than with L. Let x(i) be the length of the ith longest interval: So the lengths of the intervals are x(1), x(2), ... x(n) in some order, and x(1) >= x(2) >= ... >=x(n). Now E(M(&sigma(f))) = E(sum(σ in S(n), M(f))/n!) = E(sum(i = 1 to n, (n-i)C2 x(i))/((n-1)C2))). Using this we can obtain the result by considering the exponential distribution as before: The above sum is the expected value for a randomly chosen point p of (n-i)C2/(n-1)C2, where p is in interval number i. For n large, (i-1)C2/(n-1)C2 is approximately (1-(i/n))^2. So suppose we pick such a point p. Let the nearest birds on the left and right be at distances a and b respectively. Then since the lengths of the intervals have an exponential distribution with parameter 1, i/n, the proportion of the intervals which are longer than that containing p, is e^(-a-b). But a and b are also exponentially distributed, so the expected value wanted is Integral(0 to infinity, Integral(0 to infinity, e^(-a)*e(-b)*(1-e^(-a-b))^2 db) da) = 1 - 2/4 + 1/9 = 11/18. But we can actually do a little better: We can find the expected value of M exactly for any particular value of n. Define random vectors y(i) = x(i) - x(i-1) for i >1, y(1) = x(1). Let z(i) = i*y(i). Let D be Integral(Sum(i = 1 to n, x(i)) = 1 and all x(i) >=0, x(1) dx). Then we have: Integral(Sum(i = 1 to n, x(i)) = 1 and all x(i) >=0, dx) = Integral(Sum(i = 1 to n, x(i)) = 1 and all x(i) >=0, Sum(i = 1 to n, x(i)) dx) = nD. And so: E(M) = E(sum(i=1 to n, (n-i)C2 x(i))/((n-1)C2))) = (n!/((n-1)C2*nD))*Integral(x(n)>=x(n-1)>=...>=x(1)>=0 and Sum(i=1 to n, x(i)) = 1, Sum(i=1 to n, (n-i)C2 x(i)) dx) = (n!/((n-1)C2*nD))*Integral(Sum(i=1 to n, i*y(i)) = 1 and all y(i)>=0, Sum(i=1 to n, Sum(j=1 to i, (n-j)C2) y(i)) dy) = (1/((n-1)C2*nD))*Integral(Sum(i=1 to n, z(i)) = 1 and all z(i)>=0, Sum(i=1 to n, (nC3 - (n-i)C3)/i * z(i)) dz) = (1/((n-1)C2*n))*Sum(i=1 to n, (i^2 - (3n-3)i + 3n^2-6n+2)/6) = (n(n+1)(2n+1) - 3(3n-3)n(n+1) + 6(3n^2-6n+2)n)/(18n(n-1)(n-2)) = 11/18 independently of n, for n > 2. This independence is of course highly suggestive that there ought to be a simpler way to do this. First, the calcuation is simple in the case n = 3. See for example post #14. So consider k(1) = x(1)/x(3) and k(2) = x(2)/x(3). By a similar argument to that for the permutations, these are uniformly distributed in the interval <0, 1> with the restriction k(1) < k(2). So the expected value of the length of the longest of the first three intervals is 11/18 of the expected value of the sum of their lengths. Now as before choose a permutation of the first three intervals at random. The expected contribution to M from the second interval after the permutation is then 1/3 of 11/18 of the sum of the lengths of the first 3 intervals; or 11/18 of the expected value of the length of an interval. Now by averaging this result over all permutations and all intervals, we have the desired result. sfwc <>< |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
sfwc
Member since Jun-19-03
|
Dec-13-06, 03:16 PM (EST) |
|
19. "RE: Birds on a Wire"
In response to message #17
|
Ooops: I just realised I made a mistake in my algebra. The correct formula for the discrepancy is 22/(9(n+1)) - 2/(n+1), or 4/(9(n+1)). So with 200 birds the expected painted length is 7/18 + 4/1809 = 1415/3618 = 0.391100..., or with just 5 birds the expected painted length is 25/54 = 0.4(629) Sorry about that, sfwc <>< |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
Mark
guest
|
Nov-17-06, 07:52 AM (EST) |
|
13. "RE: Birds on a Wire"
In response to message #0
|
Has anyone tried to write their own simulation? I ask because I tried using an Excel spreadsheet and got an answer that the yellow painted length equaled about half the wire length for a large number of birds.Also, if you imagine that the ends of the wire are attached in a loop; then the posts can be represented by a dot on the loop. Before you choose the posts position (the dot): If you place an even number of birds on the loop of wire; then add the length covered by every other pair of birds; then by symmetry this length will tend to half the full loop length. The post position can then be selected by choosing a random point.
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
|
D. Hiersekorn
guest
|
Jan-06-07, 08:18 AM (EST) |
|
22. "RE: Birds on a Wire"
In response to message #13
|
OK, so I'm not a mathematician. But, I see this problem as being a lot simpler than what is being discussed. First, as the number of birds approaches infinity, it is clear that painted portion must be less than half of the wire. Painting random intervals would approach half of the wire being painted. So, it follows that painting only the shorter intervals would result in something less than half. The question is how much. As has been pointed out, the distributions must be analyzed in groups of three, and there are three possible results for any given interval. (i.e. painted 0, 1, or 2 times.) So, I get 1/2 minus 1/3^2 or 7/18. Why is this not correct? |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
Pierre Charland
Member since Dec-22-05
|
Jan-27-07, 08:11 AM (EST) |
|
23. "RE: Birds on a Wire"
In response to message #22
|
I am puzzled by your reasoning, although you do get 7/18 which is the right answer.You say: "Painting random intervals would approach 1/2 of the wire being painted." Suppose from each point we paint either left or right at random. Let L,R on a point if from it we paint left or right. Consider 1 interval, we have 4 cases for the 2 points: (.n == # colored intervals) (LR.0,LL.1,RR.1,RL.1), whith probability(interval colored) = (0+1+1+1)/4 = 3/4. This is an approximation cause consecutive intervals are not independant. Let's try a better approximation: Consider 2 consecutive intervals, we have 8 cases for the 3 points: (.n == # colored intervals) (LLL.2,LLR.1,LRL.1,LRR.1,RLL.2,RLR.1,RRL.2,RRR.2), whith probability(interval colored) = (2+1+1+1+2+1+2+2)/(2*8) = 12/16 = 3/4. Let's try a better approximation: Consider 3 consecutive intervals, we have 16 cases for the 4 points: (.n == # colored intervals) (LLLL.3,LLLR.2,LLRL.2,LLRR.2,LRLL.2,LRLR.1,LRRL.2,LRRR.2,RLLL.3,RLLR.2,RLRL.2,RLRR.2,RRLL.3,RRLR.2,RRRL.3,RRRR.3), whith probability(interval colored) = (3+2+2+2+2+1+2+2+3+2+2+2+3+2+3+3)/(3*16) = 36/48 = 3/4. So: painting random intervals would approach 3/4 of the wire being painted. AlphaChapMtl |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
DHiersekorn
guest
|
Feb-03-07, 01:00 AM (EST) |
|
25. "RE: Birds on a Wire"
In response to message #24
|
I appreciate the criticisms, but I don't think I did a good enough job of explaining my reasoning. I attempted to simplify my approach when I suggested that random interval painting would approach half of the wire. That is incorrect, and I would agree that it would produce 3/4 of the wire being painted. However, leaving the random approach aside, I still think there is validity to my approach. Unfortunately, I'm much better picturing this in my mind than expressing it in mathematical models. Is it agreed that painting the SHORTER intervals will result in something less than half of the wire being painted? If so, the question is how much less than half. I would submit that the answer to that question can be found by looking at the IMPACT of adding a bird to an already-painted wire. In other words, paint the wire according to the rules, then add a bird and look at the likelihood that the additional bird produces a change in the pattern. Bear in mind, however, that the added bird doesn't follow the general rules, because he exists in a finite space. Maybe a better way of explaining this is to point out that there are not simply three possible conditions for any span of wire. It's not simply that it can be painted 0, 1 or 2 times. It's more complicated than that. Each span of paint ORIGINATES with a bird. It's more accurate to think of the painted span as an arrow, not a line. i.e.: 1 2-->3<-->4<--5 Next, it must be recognized that, while there may be four conditions of the wire, and three of them are painted, that does not mean that 3/4ths of the wire would be painted. The more times a span is painted, the SHORTER it would tend to be. Moreover, the more times a span is painted, the greater the likelihood that the adjacent span is not painted. Necessarily, a painted span must be shorter than an adjacent unpainted span. Every time you paint a span of line, you must create a LONGER span of line that isn't painted. That's unavoidable, notwit'standing the simplistic 3-out-of-4 argument. It is definitionally required by the problem. A span cannot be painted unless it is shorter than an adjacent span. To me, this means less than half of the wire will be painted. Back to the approach of adding a bird to an existing wire. There are nine possible results, four of which result in more painted wire, and five of which result in less painted wire. That's how I arrive at 1/2 minus 1/9. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Copyright © 1996-2018 Alexander Bogomolny
|
|