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
    @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