EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On the Algorithm Complexity of Generating Discrete Uniform Distribution from a Biased Coin

Mengqi Zhang, Guangqiang Teng, Xiaoyu Lei

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).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

Monte Carlo methodsalgorithm complexitybiased coincharacteristic functiondiscrete uniform distributionfairness in algorithmsnumber theoryrandom number generation

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}
}
Kostenlos starten →