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.

Suppose I have a machine that processes units at a fixed rate. If I want to run it at a lower rate, I have to leave gaps in the infeed. For example, if you want to process 3/4, then you would feed in 3, leave a gap, then repeat. This could be encoded as a binary sequence: 1110.

If you want to process 3/5, then a simple sequence would be 11100. This however leaves an unnecessarily large gap. Perhaps they want as constant a rate as possible down the line. A better sequence would be 11010. Where the gaps are spread as far as possible (remembering that the sequence repeats).

Hopefully this has explained the problem. I shall now attempt to phrase it more mathematically.

Given a fraction $a/b$, generate a binary sequence of length $b$, that contains exactly $a$ ones, and where the distance between zeros is maximised if the sequence were repeated.

In my attempts so far, I've worked out the building blocks of the sequence, but not quite how to put it together. For instance, 77/100 should be composed of 8 lots of 11110 and 15 lots of 1110. Since $8\times5+15\times4=100$ and $8\times4+15\times3=77$. The next step of splicing together my group of 8 and my group of 15 eludes me (in general).

share|improve this question
    
What do you mean by "the distance between zeros is maximised"? Do you want the smallest distance to be as large as possible? –  Qiaochu Yuan Apr 10 '12 at 3:50
    
It's probably more like the sum of the distances, or the mean. For a small fraction you're undoubtedly going to have the minimum distance to be 1, but that doesn't mean they should all be 1. Feel free to make it more precise by interpreting the description! –  wxffles Apr 10 '12 at 3:58
    
Would it be fair to say that you’d like the zeroes to be as nearly uniformly distributed as possible when the string is repeated many times? –  Brian M. Scott Apr 10 '12 at 4:08
    
@BrianM.Scott That sounds good in a general interpretation, but I wouldn't want to comment if you are talking about applying statistics. –  wxffles Apr 10 '12 at 4:19

1 Answer 1

up vote 3 down vote accepted

Consider the following algorithm: let $a_i$ be the digit given on the $i$-th step; $b_i = b_{i-1}+a_i$ ($b_0 = 0$) the number of ones given until $i$-th step (and $i-b_i$ the number of zeros give until $i$-th step); define $a_{i+1}$ to be a zero iff $\frac{b_i}{i+1} > p$ (where $p$ is given probability); one otherwise.

This way, you'll get the zeros as far away from each other as possible, and also you'll get the irrational probabilities support. Also this algorithm is periodic for rational probabilities.

share|improve this answer
    
This works excellently. Just an additional note, one needs $a_0 = 1$. –  wxffles Apr 10 '12 at 20:25

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.