CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Birds on a Wire"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #455
Reading Topic #455
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

  Subject     Author     Message Date     ID  
Birds on a Wire Sam May-21-04 TOP
  RE: Birds on a Wire alexb May-21-04 1
  RE: Birds on a Wire sfwc May-22-04 2
     RE: Birds on a Wire Sam May-22-04 3
  RE: Birds on a Wire Mark Huber May-24-04 4
  RE: Birds on a Wire Moshe Eliner Oct-18-04 5
     RE: Birds on a Wire Pierre Charland Dec-10-06 14
         RE: Birds on a Wire sfwc Dec-12-06 16
             RE: Birds on a Wire Pierre Charland Dec-15-06 20
  RE: Birds on a Wire r eidelman Dec-24-04 6
  RE: Birds on a Wire mr_homm Jul-01-05 7
     RE: Birds on a Wire mr_homm Jul-03-05 8
         RE: Birds on a Wire alexb Jul-03-05 9
             RE: Birds on a Wire mr_homm Jul-03-05 10
                 RE: Birds on a Wire alexb Jul-04-05 11
                 RE: Birds on a Wire Moshe Eliner Jul-27-05 12
                     RE: Birds on a Wire Pierre Charland Dec-10-06 15
                 RE: Birds on a Wire sfwc Dec-12-06 17
                     RE: Birds on a Wire sfwc Dec-13-06 18
                     RE: Birds on a Wire sfwc Dec-13-06 19
  RE: Birds on a Wire Mark Nov-17-06 13
     RE: Birds on a Wire - Message 13 Mark Dec-30-06 21
     RE: Birds on a Wire D. Hiersekorn Jan-06-07 22
         RE: Birds on a Wire Pierre Charland Jan-27-07 23
             RE: Birds on a Wire mr_homm Feb-03-07 24
                 RE: Birds on a Wire DHiersekorn Feb-03-07 25

Conferences | Forums | Topics | Previous Topic | Next Topic
alexb
Charter Member
1952 posts
May-21-04, 02:07 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail sfwc Click to send private message to sfwc Click to view user profileClick to add this user to your buddy list  
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
Sam
guest
May-22-04, 05:56 PM (EST)
 
3. "RE: Birds on a Wire"
In response to message #2
 
   Well, I'll have to sit for a while and ponder this, but thanks very much for the replies!


  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)
Click to EMail Pierre%20Charland Click to send private message to Pierre%20Charland Click to view user profileClick to add this user to your buddy list  
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
sfwc
Member since Jun-19-03
Dec-12-06, 08:33 PM (EST)
Click to EMail sfwc Click to send private message to sfwc Click to view user profileClick to add this user to your buddy list  
16. "RE: Birds on a Wire"
In response to message #14
 
   >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
<><


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Pierre Charland
Member since Dec-22-05
Dec-15-06, 02:45 PM (EST)
Click to EMail Pierre%20Charland Click to send private message to Pierre%20Charland Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
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
mr_homm
Member since May-22-05
Jul-03-05, 05:51 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
8. "RE: Birds on a Wire"
In response to message #7
 
   I see that alexb has linked my post on this topic back to the probability topic page. Thanks for taking an interest. You should notice that the text doesn't print properly when you access it from the probability/birdonwire page. Specifically, the third paragraph is cut off because a "less than " sign is read as an html tag opening symbol. In the forum, of course, it prints correctly.

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1952 posts
Jul-03-05, 05:53 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail Pierre%20Charland Click to send private message to Pierre%20Charland Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail sfwc Click to send private message to sfwc Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail sfwc Click to send private message to sfwc Click to view user profileClick to add this user to your buddy list  
18. "RE: Birds on a Wire"
In response to message #17
 
   >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.
Using the techniques in my previous post, it is in fact possible (by considering the error introduced at the endpoints) to find out the expected painted length for the original problem on a wire with n birds. The deviation from 7/18 of the expected value for n birds, where n is at least 5, is 22/(9(n+1)) - 2/n. So for example with 200 birds the expected painted length is 7/18 + 22/1809 - 2/200 = 70741/180900 = 0.391050... This agrees well with the result produced by the applet.

Thankyou

sfwc
<><


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
sfwc
Member since Jun-19-03
Dec-13-06, 03:16 PM (EST)
Click to EMail sfwc Click to send private message to sfwc Click to view user profileClick to add this user to your buddy list  
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
Mark
guest
Dec-30-06, 07:48 AM (EST)
 
21. "RE: Birds on a Wire - Message 13"
In response to message #13
 
   I realise now that I misread the question. Doh!


  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)
Click to EMail Pierre%20Charland Click to send private message to Pierre%20Charland Click to view user profileClick to add this user to your buddy list  
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
mr_homm
Member since May-22-05
Feb-03-07, 07:45 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
24. "RE: Birds on a Wire"
In response to message #23
 
   I agree with your conclusion, although there is a shorter way to prove it. It is true that the intervals are not independent, but the birds ARE independent, and the color of an interval depends only on the two birds at its ends. Each of these has a 1/2 chance of coloring it, so the chance that it is uncolored is 1/4. This is true for each interval separately.

The reasoning leading to 1/2 - 1/3^2 seems unjustified to me. I really do not see what the previous poster was thinking.

--Stuart Anderson


  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

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK