l
is a poor variable name. It doesn't convey any information about what it is and it is easy to confuse with the number 1
. I'll use nbits
.
If nbits
is not too large, it might make sense to precompute a table of possible bit flips and their probablities. For a probability of mu that a bit flips, the probability that it doesn't flip is (1 - mu)
. The probability that no bits are flipped is (1 - mu)**nbits
; that only 1 bit flips is mu*(1 - mu)**(nbits - 1)
; that two are flipped is (mu**2)*(1 - mu)**(nbits - 2)
; and so on. For each number of flipped bits, each pattern is equally likely.
For the sample problem above, nbits
is 3, and there are 8 possible bit flips: [0b000, 0b001, 0b010, 0b011, 0b100, 0b101, 0b110, 0b111]. There is one possibility of no bits flipped which has a probability of (1 - mu)**3
. There are 3 possibilities with 1 bit flipped; each with a probablility of (mu*(1 - mu)**2)
. For 2 bits, there are also 3 possibilities, each with a probability of (mu**2)*(1 - mu)
. Lastly, the probability that all bits are flipped is mu**3
. So we get:
p = [(1-mu)**3, (mu*(1-mu)**2), ((mu**2)*(1-mu)), mu**3]
flips = [0b000, 0b001, 0b010, 0b011, 0b100, 0b101, 0b110, 0b111]
weights = [p[0], p[1], p[1], p[2], p[1], p[2], p[2], p[3]]
Obviously, for larger nbits
, you would have a function that calculates the probabilities and weights.
Then use random.choices()
to pick the bit flips based on the weights:
for number in range(N):
intList[number] ^= random.choices(flips, weight=weights)[0]
According to the docs, it is a bit more efficient to use cumulative weights.
import itertools
cum_weights = list(itertools.accumulate(weights))
Note that flips
is the same as range(8)
, so we can do:
for number in range(N):
intList[number] ^= random.choices(range(2**nbits), cum_weights=cum_weights)[0]
Lastly, if N
isn't too big, we can use the k
parameter to pick all the flips for the entire list in one call.
for index, bits in enumerate(random.choices(range(2**nbits), weights=weights, k=N)):
intList[index] ^= bits
It nbits
is too large to make a table for all possible bit flips, make a smaller table. Then use bit-shifts and or-operations to get the required number of bits. For example, with a table for 8-bits, a 16-bit flip can be calculated like this:
hi, lo = random.choices(range(2**nbits), cum_weights=cum_weights, k=2)
flip = hi << 8 | lo
n
andl
? \$\endgroup\$