2
$\begingroup$

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).

  • 0
    What do you mean by "the distance between zeros is maximised"? Do you want the smallest distance to be as large as possible?2012-04-10
  • 0
    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!2012-04-10
  • 0
    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?2012-04-10
  • 0
    @BrianM.Scott That sounds good in a general interpretation, but I wouldn't want to comment if you are talking about applying statistics.2012-04-10

1 Answers 1

3

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.

  • 0
    This works excellently. Just an additional note, one needs $a_0 = 1$.2012-04-10