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)