Accession Number : AD0721101

Title :   Efficient Techniques for Unbiasing a Bernoulli Generator,

Corporate Author : RESEARCH ANALYSIS CORP MCLEAN VA

Personal Author(s) : Lechner,James A.

Report Date : MAR 1971

Pagination or Media Count : 23

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)

Descriptors :   (*RANDOM VARIABLES, SEQUENCES(MATHEMATICS)), BINARY ARITHMETIC, PROBABILITY, SAMPLING, THEOREMS

Subject Categories : Statistics and Probability

Distribution Statement : APPROVED FOR PUBLIC RELEASE