Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.20234
curl -X POST /api/v1/records/arxiv/2608.20234/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.20234/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'