Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!cmcl2!yale!leichter
From: leichter@yale.UUCP (Jerry Leichter)
Newsgroups: comp.arch
Subject: Re: random number generator in hardware (XOR scheme)
Message-ID: <4691@yale-celray.yale.UUCP>
Date: Mon, 1-Dec-86 09:42:27 EST
Article-I.D.: yale-cel.4691
Posted: Mon Dec  1 09:42:27 1986
Date-Received: Mon, 1-Dec-86 20:01:27 EST
References: <317@zuring.mcvax.UUCP> <267@bath63.UUCP> <7334@utzoo.UUCP> <3915@columbia.UUCP> <533@vaxb.calgary.UUCP>
Reply-To: leichter@yale-celray.UUCP (Jerry Leichter)
Organization: Yale University, New Haven, CT
Lines: 33


Josh Benaloh (decvax!yale!benaloh, or benaloh@Yale) has a tech report on the
subject of combining "poor" random number generators to make better ones.
(He calls the process "coin fairing".)  It turns out that XOR isn't always the
best approach (where you measure "fairness" of the resulting coin with the
number of tosses of the unfair coin you had to take).

Simple way to see the general model:  Suppose you decide to toss your poor
coin 10 times.  This gives you 10 bits, in one of 1024 combinations.  List
them in numeric order (as binary numbers) along a line, and plot the proba-
bility of each combination, given the unfairness of the coin, above its
value.  Now, what you want to do is divide the area under your curve into
two regions, one that you will consider a total toss of 0, another that you
will consider a total toss of 1.  You want the areas of the two regions to be
as close as possible.

XOR'ing simply uses the parity of the 10 bits to divide the regions.  Majority
vote uses the total number of bits (you have to decide on some rule to deal
with 5 of each).  There are many other possibilities; most, of course, require
too much computation, relative to any possible improvement, to be of much
value.

I stated the example using 10 tosses of the same biased coin, but of course I
could as well have used 10 coins, or 5 coins each tossed twice, and so on.

In general, you can do quite well IF the various "poor" random numbers you
start with are not correlated with each other.  Getting rid of correlations
is very difficult; if you don't know the correlations, it may not be possible.
There's some general theoretical work on this, in a model that's probably not
too useful for building hardware, but Vijay and Umesh Vazirani.  (Sorry, I don't
have a reference - try the last couple of STOC and FOCS conferences.)

							-- Jerry