A Generalization of Peres’s Algorithm for Generating Random Bits From Loaded Dice

摘要

Peres’s algorithm produces unbiased random bits from biased coin tosses, recursively, using the famous von Neumann’s method as its base. The algorithm is simple and elegant, but, at first glance, appears to work almost like magic and its generalization is elusive. We generalize the method to generate unbiased random bits from loaded dice, i.e., many-valued Bernoulli source. The generalization is asymptotically optimal in its output rate as is the original Peres’s algorithm. Three-valued case is discussed in detail, and then other many-faced cases are considered.