  The problem of random number generation from an uncorrelated random source
(of unknown probability distribution) dates back to von Neumann's 1951 work.
Elias (1972) generalized von Neumann's scheme and showed how to achieve optimal
efficiency in unbiased random bits generation. Hence, a natural question is
what if the sources are correlated? Both Elias and Samuelson proposed methods
for generating unbiased random bits in the case of correlated sources (of
unknown probability distribution), specifically, they considered finite Markov
chains. However, their proposed methods are not efficient or have
implementation difficulties. Blum (1986) devised an algorithm for efficiently
generating random bits from degree-2 finite Markov chains in expected linear
time, however, his beautiful method is still far from optimality on
information-efficiency. In this paper, we generalize Blum's algorithm to
arbitrary degree finite Markov chains and combine it with Elias's method for
efficient generation of unbiased bits. As a result, we provide the first known
algorithm that generates unbiased random bits from an arbitrary finite Markov
chain, operates in expected linear time and achieves the information-theoretic
upper bound on efficiency.
