{"id":"arxiv/2608.20234","url":"https://arxiv.org/abs/2608.20234","tags":["cs.IT","math.PR"],"score":0,"title":"Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction","domain":"cs.IT","source":"arxiv","authors":["Claude Gravel"],"reviews":0,"subject":"cs.IT","summary":"Bernard and Letac (1971) introduced a method for uniform random sampling among $m$ outcomes from an unknown biased source of independent and identically distributed symbols. The process terminates when the multinomial coefficient of the cumulative symbol counts equals zero modulo $m$. This study extends the computational and information-theoretic analysis of their construction by presenting five algorithms with formal correctness guarantees and comprehensive complexity analyses. For prime $m=p$, the Bernard-Letac framework is analyzed in greater detail. The Rényi entropies of the source…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-20","reactions":{}}