Efficient Techniques for Unbiasing a Bernoulli Generator,
Abstract
Consider the problem of operating on a sequence of i.i.d. Bernoulli variables with unknown mean p to produce a sequence of symmetric Bernoulli variables. Define the efficiency of any proposed method to be the average number of output digits per input digit. The following results are proved: (A) No method exists having efficiency greater than -p (log of p to the base 2) - q (log of q to the base 2), where q is identically equal to 1 - p. (B) Methods do exist with efficiency arbitrarily close to the bound just given. Examples are given, and compared with other methods in the literature. A technique for finding the methods of (B) is given. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1971
- Accession Number
- AD0721101
Entities
People
- James A. Lechner