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.
How to quantify uniform distribution?
-
1
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. – 2011-07-30
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).
-
0Thanks 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. – 2011-07-30
The phrase you are looking for is combinatorial discrepancy. Type that into Google and it will point you to many expositions.
-
0Thank 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 https://ics-web.sns.ornl.gov/timing/Rep-Rate%20Tech%20Note.pdf – 2011-07-31
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.)