Most computers use a pseudorandom number generator to mimic random numbers. While such pseudorandom numbers are sufficient for many applications, they may not suffice when more secure randomness is needed, such as when you are generating a cryptographic key. For example, years ago the security of the Netscape browser was broken when people found how the seed for the pseudorandom number generator was created.
When better randomness is required, software can be used to obtain randomness from the computer system, including behaviors such as disk movement, user keystrokes, mouse clicks, or sounds recorded by microphones. While many of these physical phenomena can produce random events that are hard to predict, it is not clear how to distill this randomness into something useful, such as random bits that are "0" half the time and "1" the other half. For example, you might try using the number of microseconds between keystrokes to generate random numbers, outputting a 0 if the number of microseconds is even and 1 if the number is odd. While it might be hard to accurately predict the number of microseconds between user keystrokes, it may happen that some users consistently end up with an odd number of microseconds between key strokes 70 percent of the time.
In this article, I'll present a means of efficiently extracting random bits from a possibly biased source of bits. I focus on a simple model of a random source: It generates bits that are 0 with probability p and 1 with probability q=1-p. Here, p should be strictly between 0 and 1. Each bit is independent; that is, whether it is 0 or 1 is not correlated with the value of any of the other bits. What you want is to generate fair bits that are independent and take on values 0 and 1, each with probability 1/2.
For a more physical interpretation, consider this: You have a coin and would like to use it to generate random bits. Unfortunately, the coin may be dented or weighted in some way you do not know, so it might be that it comes up heads with some probability p that does not equal 1/2. Can you use this coin to generate fair bits? Interestingly, you can even if you do not know the value of p. This procedure has practical applications to software that extracts randomness from biased sources, and also leads to some fun mathematics. The approach described here is based on work by Yuval Peres (see "Iterating von Neumann's Procedure for Extracting Random Bits," Annals of Statistics, March 1992).
Extracting Single Bits
The first question to consider is how you can use the possibly biased coin to generate a single fair bit. For convenience, assume coin flips as coming up either heads or tails and the bits produced as being 0s and 1s. The key insight you need (which has been attributed to John von Neumann) is to use symmetry. Suppose you flip the coin twice. If the coin lands heads and then tails, you should output a 0. This happens with probability pq. If instead the coin lands tails and then heads, you should output a 1. This happens with probability qp=pq. In the case where the coin provides two heads or two tails, you simply start over. Since the probability you produce a 0 or 1 is the same for each pair of flips, you must be generating fair bits. This procedure does not even need to know the value of p.
Listing One is the process just described. The procedure looks at consecutive pairs of flips and determines if they yield a fair bit. The variable NumFlips represents the number of biased flips available.
Listing One
Function ExtractBits ( Flips[0,NumFlips-1] )
for (j = 0; j < (NumFlips-1)/2; j++) {
if ( Flips[2*j] == Heads ) and ( Flips[2*j+1] == Tails ) print 0;
if ( Flips[2*j] == Tails ) and ( Flips[2*j+1] == Heads ) print 1;
}
}
While this function provides a good first step, it doesn't seem efficient. The function discards pairs of flips when there are two heads (probability p2) or two tails (probability q2=(1-p)2). Using calculus or a graphing calculator reveals that p2+(1-p)2 achieves its minimum value of 1/2 when p=1/2. Hence, no matter what the value of p is, the function throws away a pair of flips at least half of the time.
Suppose you define a function B(p) to represent the average number of fair bits per coin flip when the coin lands heads with probability p. You should note that 0
B(p)1; you can't get more than one fair bit out of even a fair coin! Also, B(p) is meant to represent a long-term average; it ignores issues such as when you have an odd number of coin flips, the last one is useless under this scheme. For every two flips, you get a fair bit with probability 2pq, so B(p)=pq. When p=q=1/2, so that my coin is fair and I could conceivably extract one full fair bit per flip, B(p) is just 1/4.
Making More Use of Symmetry
A better approach also uses symmetry beyond pairs of flips. For example, suppose you flip two heads followed by two tails. In the original extraction scheme, you obtain no fair bits. But if you decide that two heads followed by two tails produces a 0, while two tails followed by two heads produces a 1, then you maintain symmetry while increasing the chances of producing a fair bit.
There is a nice way to visualize how to do this. Consider the original sequence of flips. You build up a new sequence of flips in the following way: Whenever you get a pair of flips that are the same in the original sequence of flips, you introduce a new flip of that type into the new sequence; see, for example, Table 1.
Table 1: Generating a new sequence.
Whenever a pair of flips is heads-tails or tails-heads, you generate a fair bit using von Neumann's approach. Whenever a pair is heads-heads or tails-tails, add a new coin flip to the new sequence. After you finish with the original sequence of flips, turn to the new sequence of flips to get more fair bits. You append the fair bits from the new sequence to those produced by the original sequence. In Table 1, the final output would be 010101. The new sequence looks for the symmetry between the sequences heads-heads-tails-tails and tails-tails-heads-heads.
There is no reason to stop with just a single new sequence. You can use the new sequence to generate another new sequence, recursively. For example, suppose you change the previous example to Table 2. In this example, the second level produces no extra fair bits, but if you generate a further new sequence recursively, you obtain one more fair bit.
Table 2: Recursively generating bits.
