Subject: Re: Redundancy eliminator
Summary: Removing bias
From: hrubin@pop.stat.purdue.edu (Herman Rubin)
In article <665619179@weevil.cs.duke.edu>, srt@duke.cs.duke.edu (Stephen R. Tate) writes:
> In article <695@hhb.UUCP> istvan@hhb.UUCP (Istvan Mohos) writes:
> >In article <1991Feb1.081237.27790@santra.uucp>, 
> >t31694c@kaira.hut.fi (Tapani Lindgren) writes:
> 
> >>There is a simple way to get an unbiased random sequence from a
> >>biased one.  It has been described in several recent postings,
> >>so I won't repeat it here.
> >
> >A number of us have apparently missed these articles.
> >Re. article <14983@smoke.brl.mil> gwyn@smoke.brl.mil (Doug Gwyn):
> >>...I would find the existence of such an algorithm most surprising.

There are two distinct types of bias problems.  If there is a constant
bias, and otherwise the bits are independent, then depending on how
complicated an alogrithm is used, one can get as efficient a bias
remover as one wishes.

If the bits are independent with differing bias, the problem is very
much harder.  The XOR method works well if the bias is small, but is,
of course, inefficient.  The XOR method on blocks can be used to remove
local bias, and various designs can get efficiency at the expense of
some global lack of independence.

If the bits may have local dependence, but very little global dependence,
then these methods may be combined.  Given the probability assumptions,
and what is wanted, it is usually possible to do something reasonable.
--
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet)   {purdue,pur-ee}!l.cc!hrubin(UUCP)