Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a real-world situation with a machine that lays a layer of wires on a high-pressure hose. The machine has S "slots" (approx 200), and each slot could have one wire or be empty. Typically there are about 100 - 180 wires (W). The objective is to uniformly distribute the wires over the slots, so the best hose is manufactured. The company uses a schedule on how to put the wires on the machine. For each value of W it shows how to distribute the wires. This distribution has been used for two decades or more "because we always done things that way". I came up with a different and I think more uniform distribution calculation using my Excel programming skills. Now I want to mathematically prove mine is better. My question is how to do that. Example of company distribution with S=144 and W=80: (1 indicates a slot with wire present; 0 is an empty slot) A section of 17: 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 with 6 evenly distributed sections of 1 0 1 0 1 0 1 My solution: 1 0 1 0 1 0 1 0 1 (divide both numbers by 16, then it becomes a "distribute 5 in 9" question) There must be some way to calculate the evenness of distribution. One thought I had is that an even distribution has the same percentage of 1's regardless of the size of the sample. Can you point me in the right direction? Thanks, Tom in Phoenix.

share|improve this question
    
When you say "uniform" do you mean you want everything to be as evenly spaced as possible? (In mathematics "uniform" sometimes means "every possibility happens with equal probability" which is actually very different from "evenly spaced.") –  Qiaochu Yuan Jul 30 '11 at 5:02
1  
Also, it's not clear to me how to "mathematically prove" that your distribution is better without knowing why and in what way a more even spacing of the wires leads to a better product. –  Qiaochu Yuan Jul 30 '11 at 5:03
    
Yes, evenly spaced. Even spacing leads to more even spacing of the wires on the hose, less tangling, less wires on top of each other. –  Tom van Stiphout Jul 30 '11 at 5:04
1  
Then isn't there some kind of performance test you can do on the different distributions? That seems like it would be more convincing than a mathematical argument in this context. –  Qiaochu Yuan Jul 30 '11 at 5:11
1  
<smile> Yes we are now building a few test hoses using my distribution. They are then tested at above 20,000 PSI until they burst. The math proof was more to satisfy my curiosity. –  Tom van Stiphout Jul 30 '11 at 5:14
add comment

3 Answers

As Qiaochu said, you can't mathematically prove that your spacing is better without specifying some physical model; but perhaps some thoughts about possible definitions of a measure of uniformity might be of use.

The first thought one might have would be to minimize the variance of the distances between adjacent wires. However, every half-way sensible solution (including yours and theirs) will have the same variance; they will only differ by how these distances are arranged.

I see two basic directions you could go from there. One would be to define the measure globally instead: Each wire has an "ideal" location, which is just its index times the average distance. You could define the quality as the root mean square distance from these ideal positions.

Or you could go from nearest-neighbour distances to distances to further neighbours. The first thing to try in this direction might be to minimize the variance in the distances between second-nearest neighbours (under the constraint that the solution is optimal in the more trivial nearest-neighbour sense as above).

share|improve this answer
    
Thanks joriki, the "ideal location" plus "banker's rounding" is indeed the foundation of my Excel program. (oops - [Enter] gets away from me) I am indeed also interested in the optimal value, to find out how close my solution is to it. –  Tom van Stiphout Jul 30 '11 at 5:53
add comment

The phrase you are looking for is combinatorial discrepancy. Type that into Google and it will point you to many expositions.

share|improve this answer
    
Thank you. Your hint led me to an article describing the perfect algorithm: E. Bjorklund The Theory of Rep-Rate Pattern Generation in the SNS Timing System ics-web.sns.ornl.gov/timing/Rep-Rate%20Tech%20Note.pdf –  Tom van Stiphout Jul 31 '11 at 0:49
add comment

The problem of distributing things as nearly uniformly as possible also arises in musical rhythms. This paper shows how Euclid's algorithm accomplishes that task.

(I heard a song on the radio that went on for about 10 minutes in which, while the melody went through all sorts of different variations and had lots of variety, the rhythm continued throughout the whole thing as follows: 1110111011111110 (three 1s, one 0, three 1s, one 0, seven 1s, one 0, then repeat). That's the notation used both in this question and in the paper linked to above.)

share|improve this answer
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.