An Improved Method to Extract Quasi-Random Sequences from Generalized Semi-Random Sources

Hiroaki YAMAMOTO, Hideo KASUGA

Summary :

In this paper, we consider new and general models for imperfect sources of randomness, and show how to obtain quasi-random sequences from such sources. Intuitively, quasi-random sequences are sequences of almost unbiased elements over a finite set. Our model is as follows: Let A be a finite set whose number of elements is a power of 2. Let 1/|A| δ 1 be a constant. The source outputs an element on A with probability at most δ, depending on outputs made by itself so far. From the definition, our sources output at least two elements with nonzero probability. This model is very general, because the source may output only two elements of A with nonzero probability, and the other elements with probability 0. This ability becomes a big difficulty for generating quasi-random sequences. All the methods for the existing models such as PRB-models and δ-sources fail to generate quasi-random sequences from our models. We here give a new algorithms which generates almost unbiased elements over A from such models.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.3 pp.512-519
• Publication Date: 1999/03/25
• Type of Manuscript: PAPER
• Category: Algorithms and Data Structures

Authors

Hiroaki YAMAMOTO
Hideo KASUGA

Keyword

unbiased random number,  semi-random source,  probabilistic algorithm,  quasi-random generator