Fast and efficient construction of an unbiased random sequence

The problem of efficiently converting an input sequence of symbols generated by a stationary random process into a sequence of independent, equiprobable output symbols was considered by von Neumann. Elias (1972) proposed a method in which the sequence of symbols was divided into blocks of length N. Elias´ method requires one to store all 2^N code words. That is why the memory size of the encoder increases exponentially when N grows. We suggest a new method of constructing an unbiased random sequence which requires the memory size of O(Nlog²N) bits and has a time of calculation O(log³ Nloglog(N)) bit operations per letter as N→∞