bks@ski.UUCP ( Bruce K. Smith) (03/20/85)
henry@utzoo.UUCP (Henry Spencer) writes (Message-ID: <5219@utzoo.UUCP>): > > ... Why no hardware random numbers? > > Because it's hard to build a hardware random-number generator that > will be unbiased and STAY unbiased. There are any number of things > you can use as a source of random analog garbage -- I seem to recall > that thermal noise in a suitable semiconductor is a reasonable choice -- > but converting them into bits that are reasonably evenly distributed > (and will stay that way without constant readjustment) is harder. If your biased random bits are independent and come from the same distribution (ie, each has the SAME bias), you can derive from them a stream of independent unbiased (ie, exactly 50% probability of 1, 50% of 0) random bits. Just divide the biased bits into pairs, throw away all 00s and 11s, and output the first bit only from each 01 or 10 pair. The average number of input (biased) bits needed to make a single output (unbiased) bit will be 1/p(1-p), where p is the probability of each of the biased bits being 1. (Thus, if the original bits were in fact unbiased, you'd need an average of 4 of them to make one output bit that you KNOW is unbiased.) The proof of correctness is simple (if you understand probability) and is left to the reader. I learned of this technique from a "Mathematical Games" column (by Martin Gardner) in Scientific American. I don't recall the date, or to whom he credited the idea. Warning: typical hardware sources of random bits probably produce bits that are correlated, not merely biased. In that case, this technique may improve them but won't make them perfectly uncorrelated or unbiased. -- Bruce K. Smith Smith-Kettlewell Institute of Visual Sciences, San Francisco dual!ptsfa!ski!bks or {ucbvax, dual, sun} !twg!ski!bks (415) 561-1713 (work) (415) 479-4917 or 499-0292 (home)
rej@cornell.UUCP (Ralph Johnson) (03/27/85)
I believe that von Neumann is usually credited with the idea of using 01 and 10 pairs to unbias independent random bits, so this idea is probably 50 years old. The most recent FOCS had several articles that used this idea and expanded on it.
cooper@pbsvax.DEC (Topher Cooper HLO2-3/M08 DTN225-5819) (04/06/85)
> ...The most recent FOCS had several articles that used this > idea and expanded on it. I give up -- what is FOCS? Topher Cooper USENET: ...{allegra,decvax,ihnp4,ucbvax}!decwrl!dec-rhea!dec-pbsvax!cooper ARPA/CSNET: cooper%pbsvax.DEC@decwrl