4

Suppose I have a binary vector of sample size N with each of the two possible values (e.g., 0 and 1 occurring equally often).

For example, if N=10, the binary vector is: 0 0 0 0 0 1 1 1 1 1

Suppose I have another parameter called 'limit' which indicates the maximum amount of times that the same number can occur consecutively in the randomized vector when read from left to right.

For example, if limit=3, two 0s or two 1s after each other are ok and three 0s or three 1s are ok but no more.

Some randomizations of the vector above according to these constraints (limit = 3) would be:

1 0 1 0 1 0 1 0 1 0 or 1 1 1 0 0 0 1 1 0 0 or 0 1 0 1 1 1 0 0 1 0

Does anyone know how to program a simple algorithm that randomizes a binary vector according to the method above with 'N' and 'limit' as input parameters?

  • 1
    Do you require that each possible output gets chosen with the same probability? Or are biases acceptable? – CodesInChaos Mar 10 '16 at 11:27
  • Biases are acceptable. I suppose you mean an approach where you for example shuffle the vector using unrestricted randomization and then adjust the vector at each part where the restrictions are not met? – Bart Mar 10 '16 at 12:03
  • For very small N values a brute force method would do the trick; just randomize the vector without restrictions until you happen to get one that complies with the posed restrictions. Unfortunately, I need it to work for rather large N. For example N=40. In this case, a brute force method would be terribly slow. – Bart Mar 10 '16 at 14:06
1

What you could do (in close to O(n) time, if I'm not mistaken) is, parameterizing it with "limit", prepare / pre-compute an epsilon-free context-free grammar such as (for limit = 3),

Upto3 -> LimitOnes | LimitZeros
LimitOnes -> Zeros Ones LimitOnes | Zeros Ones | Zeros
LimitZeros -> Ones Zeros LimitZeros | Ones Zeros | Ones
Zeros -> Zero | Zero Zero | Zero Zero Zero
Ones -> One | One One | One One One
Zero -> 0
One -> 1

(please note: I don't claim it's the correct or simplest grammar you will want you use, but you can always fiddle / experiment with your own using the nifty Grammophone tool, by Michael Daines)

where "Upto3" is the grammar's axiom / start symbol.

(The only two rules depending on N being Zeros -> ... and Ones -> ...)

Then, using such a pre-computed grammar (that you'll use for generation purposes instead of parsing), you can write a simple recursive function, which, starting from the start symbol, randomly picks one of the alternatives of the rules and applies it, by string concatenation, on an accumulator that it passes to itself (and that you'll have passed as the empty string for the top level call).

At each recursive call, it is trivial to decide (depending on N and the last known length of the accumulator) which alternative branch of the rules (aka, productions) -- LimitOnes, LimitZeros, Ones, or Zeros -- it is meaningful to follow (to not exceed N).

Eg,

N = 10, limit = 3:

start with Upto3 : accumulator = ""

from "Upto3", randomly pick "LimitZeros"

from "LimitZeros", apply "Ones", "Zeros" in "Ones Zeros LimitZeros" : accumulator = "100"

from "LimitZeros", apply "Ones", "Zeros" in "Ones Zeros LimitZeros" : accumulator = "100110"

etc, etc.

I let you figure out the implementation details.

'Hope this helps,

1

The general approach to tackle a problem of this kind is to think about the combinatorics. How would you answer the question "How many 40-bit binary strings are there with no runs of more than 3 of the same bit?"

Answer: structural decomposition. A 40-bit binary string with no runs of more than 3 of the same bit ends in a run of 1, 2, or 3 bits; in general we can define a function f(n) counting n-bit binary strings which no run of more than 3 bits, and derive the recurrence f(1) = 1, f(0) = 1 (very important!), f(-1) = 0, and for larger n, f(n) = f(n-1) + f(n-2) + f(n-3).

Now, extend that to the question "How many 40-bit binary strings are there with Hamming weight of 20 bits and no runs of more than 3 of the same bit?". This time the structural decomposition needs to take into account the Hamming weight by some means or other. One way would be to consider the excess of the final bit: e.g. in 0010110 the final bit is 0 and the excess is 1 because there is one more 0 than 1. This time let's call our function g. We want to know g(40, 0) (40-bit string with 0 excess).

To derive the recurrence for g(n, e) we first suppose that the final run is of length r. If the total number of bits of the same value as the final run is b and the number of the other bit is a then by definition e = b - a. If we remove the run, we're left with n - r bits and the subtraction for the excess flips (remember that it's the excess of the last bit, and by removing the final run we flip the last bit) to become a - (b - r) = r - e.

So we get the recurrence g(n, e) = g(n - 1, 1 - e) + g(n - 2, 2 - e) + g(n - 3, 3 - e). Base cases are left as a detail which must be filled in.

Note that we can use a standard dynamic programming table approach to calculate g(n, e) in O(ne) space and time.

Having filled that table, we can address the original question: how to generate one of the g(40, 0) strings. We simply decide whether the final run will be of 0 or 1 (by a simple call to rand()), and decide whether it will be of length 1, 2, or 3 (ideally weighting the random choice in proportion to the contributions of each of the three: g(n - r, r - e)). Then we step down to that g(n', e') and apply the same process with the minor difference that rather than randomly deciding the value of the final run we flip it from the suffix.

The key point I want to make is that this process of first using a structural decomposition to answer the combinatoric question is a very general technique which applies to many many combinatorial structures. You can use it to uniformly generate a random partition of an integer, a random binary tree with a given number of nodes, etc.

0

Consider the following approach:

  1. Create a random vector without limitations
  2. Use a predefined line code in a way similar to 4B5B (https://en.m.wikipedia.org/wiki/4B5B) to make the above satisfy your limitations.

There is a general problem in the area of communication, there are many reasons for which we want to transform a string of bits into another string such that the amount of repetitions of each bit is limited (e.g avoid long substring that is all zeros or all ones). I am certain that if you review the subject you'll find what you're looking for,I believe that the 4B5B method can be generalized to achieve what you need as well, so that's a good starting point

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.