The Von Neumann Extractor

We can always do mutation efficiently in a Genetic Algorithm if we could generate a random stream of bits (machine words, really) of some arbitrary distribution equal to the probability of mutation by xoring the stream and the individual. In other words, we want a sequence of Bernoulli trials for some probability of success p, rather then fixed as a coin flip as a random number generator will give you. First lets look at the Von Neumann Extractor, which allows you to do the opposite- given a stream of bits where the probability of a 1 for any given bit is some probability p, it generates a stream where each bit has a 50% chance of being a 1.

This is a pretty simple technique. We take the stream of bits, and pair them up. For the stream starting with 001011101001, we pair up as (00)(10)(11)(10)(10)(01). Then we drop all (11)s and (00)s, and drop the second bit from all remaining pairs. This turns our resulting stream into the smaller stream 1110. In this example there happen to be more 1s then 0s, but the probability of 1 is equal to the probability of a 0 given some fixed original probability (assuming each trial is independent).

To see that this is true, recall that for a pair of bits, the probability that they are 10, with p as the probability of a 1 and q = 1-p, the probability of a 0, is equal to p*q. The probability of 01 is q*p, and by the commutativity of multiplication these are the same. This means that it must be just as likely to get 01 as 10, and since we drop the second bit, just as likely to get 0 and 1. Obviously we lose some of the stream in the process, but thats really not a big deal.

Okay- so we can take a stream of trials with probability of success p and turn it into one with probability success 0.5- in the next post we will look into going the other way.