Pseudo Random Number generator with fixed density of 1s

Question

Hi!

I'm searching for way to generate pseudo random numbers [possibly of low "randomness"] or pseudo random bit sequences with a fixed Hamming weight [ a fixed density of 1s]. I found some suggestion about using a simple linear congruential generator with a seed having the Hamming weight I need, but no reasoning was given why this is correct [why the hamming weight is invariant under the linear congruential transformation]

Could anyone reason that point or give me another way?

Thanks...

Answer 1

I've not heard about using a LCG to generate a fixed hamming weight (I didn't get that deep into hamming codes at school, so I'm not too surprised either :).

In any case, it's fairly straightforward to generate a bunch of bits with a fixed hamming weight. Here's a bit of python code that will return an n-bit number with a particular weight. This should translate easily into other languages too (aside from the fact that python integers are arbitrarily large).

from random import randrange

def get_ham_and_bits(weight, nbits=32):
    "Get n-bits with a fixed hamming weight"
    if weight > nbits: 
        return 1 < nbits

    result = 0
    for i in xrange(weight):
        bit = 1 << randrange(nbits)

        # only flip bits that aren't already flipped. delete the loop to
        # make this return a random weight instead of a fixed weight
        while bit & result != 0: 
            bit = 1 << randrange(nbits)

        # An XOR might be a better idea here, especially if you remove the loop.
        result |= bit
    return result

Answer 2

Using a pseudo random number generator (PRNG) even a simple one with a low weight seed is definitely NOT a a good solution. The PRNG do not keep the Hamming weight of the seed constant, and the whole idea of a PRNG is to remove the information of the seed.

If you want to have exacly bits sets to 1 out of n, your question is a variant of these two questions. If k is much smaller than n, the shuffling solution is O(n). I think that the following solution is O(k).

It is based on this answer, in python

from random import sample

def konesoutofn(k, n):
    output=0
    for d in sample(xrange(n), k):output+=(1<<d)
    return output

x=konesoutofn(4,32)
print(bin(x))

If you want to have to have approximately k bits sets to one, with k/n being the probability of each bit to be one then you have to look at Bernouilli and Geometric distributions.