  Generating random bits from a source of biased coins (the biased is unknown)
is a classical question that was originally studied by von Neumann. There are a
number of known algorithms that have asymptotically optimal information
efficiency, namely, the expected number of generated random bits per input bit
is asymptotically close to the entropy of the source. However, only the
original von Neumann algorithm has a `streaming property' - it operates on a
single input bit at a time and it generates random bits when possible, alas, it
does not have an optimal information efficiency.
  The main contribution of this paper is an algorithm that generates random bit
streams from biased coins, uses bounded space and runs in expected linear time.
As the size of the allotted space increases, the algorithm approaches the
information-theoretic upper bound on efficiency. In addition, we discuss how to
extend this algorithm to generate random bit streams from m-sided dice or
correlated sources such as Markov chains.
