An improved method to extract quasi-random sequences from generalized semi-random sources

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 elem ents over a finite set. Our model is as follows: Let A be a finite set whos e number of elements is a power of 2. Let 1/\A\ less than or equal to delta < 1 be a constant. The source outputs an element on A with probability at most delta, depending on outputs made by itself so far. From the definition , our sources output at least two elements with nonzero probability. This m odel is very general, because the source may output only two elements of A with nonzero probability, and the other elements with probability 0. This a bility becomes a big difficulty for generating quasi-random sequences. All the methods for the existing models such as PRE-models and delta-sources fa il to generate quasi-random sequences from our models. We here give a new a lgorithms which generates almost unbiased elements over A from such models.