On the Algorithm Complexity of Generating Discrete Uniform Distribution from a Biased Coin
Entropy · 17.07.2026 · 28 (7) · 817
DOI: 10.3390/e28070817 ↗Kurz gefasst
Fachartikel in der Zeitschrift Entropy, online erschienen am 17.07.2026. Verfasst von Mengqi Zhang und 2 weiteren Autor:innen. Beteiligte Einrichtung: School of Economics, Peking University, Beijing 100871, China. Die Arbeit nennt 10 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Lei proposed an algorithm Algorithm A3 in 2023 to generate an exact discrete uniform distribution from an unknown biased Bernoulli source. The present paper does not claim a new extraction algorithm. Its contributions are analytical: first, we provide a Fourier-analytic proof of the uniformity mechanism based on roots of unity and coefficient extraction; second, we derive explicit acceptance-probability and expected-runtime bounds, with a rigorous treatment of composite moduli; third, we show how independent accepted A3 digits yield a continuous Uniform(0,1) limit through a base-n expansion and quantify the cost of finite-digit simulation.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- School of Economics, Peking University, Beijing 100871, China.
- School of Mathematics, Harbin Institute of Technology, Harbin 150001, China.
- Department of Statistics, University of Wisconsin-Madison, 1205 University Ave, Madison, WI 53706, USA.
Zitieren
APA
Zhang, M., Teng, G., & Lei, X. (2026). On the Algorithm Complexity of Generating Discrete Uniform Distribution from a Biased Coin. Entropy, 28(7), 817. https://doi.org/10.3390/e28070817
Vancouver
Zhang M, Teng G, Lei X. On the Algorithm Complexity of Generating Discrete Uniform Distribution from a Biased Coin. Entropy. 2026;28(7):817. doi:10.3390/e28070817
BibTeX
@article{Zhang2026,
author = {Zhang, Mengqi and Teng, Guangqiang and Lei, Xiaoyu},
title = {On the Algorithm Complexity of Generating Discrete Uniform Distribution from a Biased Coin},
journal = {Entropy},
year = {2026},
volume = {28},
number = {7},
pages = {817},
doi = {10.3390/e28070817}
}
EUVIMED