Bounds on fixed-length post-processing functions for stationary biased random number generators
Koji Nuida · 2008
We investigate post-processing functions with fixed-length inputs/outputs for reducing biases of random bits. When original random bits are i.i.d., biases of the post-processed sequences are polynomials in bias of the original bits, and a function is regarded as better if least degrees of those polynomials are larger. In this article we give upper and lower bounds of the optimal least degree for such post-processing functions, and in some cases determine the optimal degree precisely.