Entropic Generation of Binary Words

Francis Durand (Universit\'e Sorbonne Paris-Nord); Olivier Bodini (Universit\'e Sorbonne Paris-Nord)

Entropic Generation of Binary Words

T0 review · 0 major / 1 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random bit recycling generates uniform k-subset binary words in linear time while consuming nearly the Shannon lower bound of random bits.

desk verdict The paper gives an explicit linear-time algorithm using random bit recycling to sample uniform k-subsets with bit usage close to the Shannon bound. read the letter →

arxiv 2606.13157 v1 pith:7V56K3HC submitted 2026-06-11 cs.DM cs.ITmath.IT

Olivier Bodini (Université Sorbonne Paris-Nord) , Francis Durand (Université Sorbonne Paris-Nord) This is my paper · ORCID

classification cs.DMcs.ITmath.IT

keywords randombitrecyclinguniformgenerationHammingweightbinarywordsShannonentropylineartimealgorithmk-subsetscombinatorialsampling

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Generating binary words of length n with exactly k ones is equivalent to uniformly sampling k-subsets and requires random bits whose cost can be high. The paper introduces random bit recycling as a way to reuse bits during generation. This produces the desired words in linear time with bit consumption that approaches the information-theoretic minimum set by the entropy of the binomial coefficient. A sympathetic reader cares because the method directly attacks the practical expense of randomness while preserving exact uniformity.

What carries the argument

Random bit recycling, a paradigm that reuses portions of previously consumed random bits to minimize total consumption while enforcing uniformity and linear runtime.

What would settle it

Run the algorithm on large n and k near n/2, measure the exact average number of random bits consumed per generated word, and compare it to log2(binomial(n,k)); if the measured consumption stays bounded away from the entropy value by a constant factor, the near-optimality claim fails.

Watch

Extended reading notes

Core claim

The authors introduce the random bit recycling paradigm and use it to build an algorithm that generates uniform random binary words of length n with Hamming weight k in linear time, with the number of random bits consumed made arbitrarily close to the Shannon entropy lower bound log2(binomial(n,k)).

Load-bearing premise

The recycling mechanism can be realized in an algorithm that simultaneously achieves linear runtime, exact uniformity of the output, and random-bit consumption arbitrarily close to the entropy bound without hidden overheads or correctness violations.

Editorial extensions

If this is right

Uniform sampling of k-subsets becomes practical in settings where random bits are expensive or limited.
The generation procedure matches the information-theoretic minimum up to an arbitrarily small additive overhead.
The linear-time guarantee makes the method suitable for large-scale combinatorial sampling tasks.
The same recycling idea can be applied to other uniform generation problems whose entropy is known.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The technique may reduce the randomness requirement in downstream randomized algorithms that rely on subset sampling.
In hardware or embedded contexts the method could lower the demand on true random number generators.
Extensions to approximate sampling or to weighted subsets appear compatible with the recycling structure.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main takeaway is that this paper turns random bit recycling into a practical linear-time algorithm for uniform generation of k-weight binary words, getting the random bit count within an additive o(log of the binomial coefficient) of the Shannon lower bound.

They back this with an explicit construction and proofs for uniformity, O(n) runtime, and the entropy closeness. That's the solid part: no circularity, direct comparison to the external bound, and the stress-test note indicates the argument holds without hidden overheads or bias.

The soft spots are limited. The o term is asymptotic, so for concrete instances the actual overhead might not be negligible, and the paper doesn't include any experimental validation or direct comparisons to prior samplers like those based on combinatorial number systems or rejection methods. That leaves the practical impact a bit open, but the theoretical claims seem to stand on their own.

This kind of work is for people in discrete algorithms and combinatorics who need efficient ways to sample subsets or generate words with exact weight. It would be of interest to those optimizing randomness in applications like cryptography or Monte Carlo methods.

The paper shows clear engagement with the problem through its construction and proofs, so it merits a serious referee even if revisions are needed for comparisons or experiments.

I would recommend sending it to peer review.

Referee Report

0 major / 1 minor

Summary. The paper introduces a novel paradigm called random bit recycling for generating uniform random binary words of length n with exactly k ones. The algorithm runs in linear time and consumes a number of random bits that is within an additive o(log binom(n,k)) of the Shannon entropy lower bound.

Significance. If the claims are correct, this provides a practical and theoretically near-optimal method for a core problem in sampling and combinatorics. The explicit construction with proofs of uniformity, linear runtime, and near-optimality in bit consumption is a strength, addressing the initial concern from the abstract alone.

minor comments (1)

[Abstract] The abstract is very brief and does not mention the proofs or construction details, which could be expanded for clarity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation to accept the manuscript. No major comments were raised.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The manuscript supplies an explicit construction realizing the random bit recycling paradigm, together with proofs establishing uniformity of the output distribution, O(n) runtime, and random-bit consumption within an additive o(log binomial(n,k)) of the external Shannon entropy lower bound. The claimed near-optimality is measured against this independent information-theoretic quantity, not against any fitted parameter or self-referential quantity internal to the paper. No self-citations, ansatzes smuggled via prior work, or definitional reductions appear in the derivation chain.

Assumptions & free parameters 0 free parameters · 1 assumptions · 1 invented entities

The claim rests on the correctness of an unnamed recycling mechanism whose internal steps are not described; the only explicit external anchor is the Shannon entropy lower bound.

assumptions (1)

standard math Shannon entropy supplies the information-theoretic lower bound on random bits needed for uniform generation of k-subsets.
Invoked directly in the abstract as the optimality target.

invented entities (1)

random bit recycling
purpose: A technique that reuses random bits to achieve near-minimal consumption while preserving uniformity and linear runtime.
Presented as the core novel paradigm; no independent evidence or construction details given.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Entropic Generation of Binary Words." pith.science (2026). https://pith.science/paper/7V56K3HC

@misc{pith2026260613157,
  author       = {Pith},
  title        = {Pith review of: Entropic Generation of Binary Words},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7V56K3HC}},
  note         = {Machine review of arXiv:2606.13157}
}

read the original abstract

The uniform generation of k Hamming weight binary words, equivalent to sampling k-subsets from n elements, relies on random bits, which can be expensive. We introduce a novel paradigm, random bit recycling, and use it to generate such binary words in linear time while consuming as few random bits as possible. The resulting algorithm is nearly optimal in terms of random bit consumption, meaning that it closely matches the Shannon entropic lower bound coming from information theory.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 11 canonical work pages

[1]

MergeShuffle: A Very Fast, Parallel Random Permutation Algorithm

Axel Bacher, Olivier Bodini, Alexandros Hollender & Jérémie Lumbroso (2015): Mergeshuffle: a very fast, parallel random permutation algorithm. arXiv preprint arXiv:1508.03167, doi:10.48550/arXiv.1508.03167

work page Pith review arXiv doi:10.48550/arxiv.1508.03167 2015
[2]

Security and Safety 4, p

Haozhe Chai, Qianqian Pan & Jun Wu (2025): A survey of random number generator: Approaches, tests, novel applications in block-chain and AI driven industrial networks . Security and Safety 4, p. 2025015, doi:10.1051/sands/2025015

work page doi:10.1051/sands/2025015 2025
[3]

Computing 39(1), pp

Luc Devroye (1987): A simple generator for discrete log-concave distributions. Computing 39(1), pp. 87–91, doi:10.1007/BF02307716

work page doi:10.1007/bf02307716 1987
[4]

CoRR abs/1502.02539, doi:10.48550/arXiv.1502.02539

Luc Devroye & Claude Gravel (2015): Sampling with arbitrary precision . CoRR abs/1502.02539, doi:10.48550/arXiv.1502.02539. arXiv:1502.02539

work page doi:10.48550/arxiv.1502.02539 2015
[5]

Efficient Online Random Sampling via Randomness Recycling

Thomas L Draper & Feras A Saad (2026): Efficient Online Random Sampling via Randomness Recycling . In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , SIAM, pp. 2473–2511, doi:10.48550/arXiv.2505.18879

work page Pith review arXiv doi:10.48550/arxiv.2505.18879 2026
[6]

Journal of the ACM (JACM)60(3), pp

Michael Drmota & Wojciech Szpankowski (2013): A master theorem for discrete divide and conquer recur- rences. Journal of the ACM (JACM)60(3), pp. 1–49, doi:10.1145/2487241.2487242

work page doi:10.1145/2487241.2487242 2013
[7]

Richard Durstenfeld (1964): Algorithm 235: Random permutation . Commun. ACM 7(7), p. 420, doi:10.1145/364520.364540

work page doi:10.1145/364520.364540 1964
[8]

1, John Wiley & Sons, New York

William Feller (1968): An Introduction to Probability Theory and Its Applications, 3rd edition. 1, John Wiley & Sons, New York

1968

Show all 13 references

[9]

Available at https://api.semanticscholar.org/CorpusID:115400979

Donald Ervin Knuth & Andrew Chi-Chih Yao (1976): The complexity of nonuniform random number gener- ation. Available at https://api.semanticscholar.org/CorpusID:115400979

1976
[10]

arXiv preprint arXiv:1304.1916, doi:10.48550/arXiv.1304.1916

Jérémie Lumbroso (2013): Optimal discrete uniform generation from coin flips, and applications . arXiv preprint arXiv:1304.1916, doi:10.48550/arXiv.1304.1916

2013 doi arXiv
[11]

Journal of the ACM (JACM) 48(2), pp

Salvador Roura (2001): Improved master theorems for divide-and-conquer recurrences. Journal of the ACM (JACM) 48(2), pp. 170–205, doi:10.1145/375827.375837

2001 doi
[12]

Feras Saad, Cameron Freer, Martin Rinard & Vikash Mansinghka (2020): The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete Probability Distributions. In Silvia Chiappa & Roberto Calandra, editors: Proceedings of the Twenty Third International Conference on Art...

2020 doi
[13]

The Bell system technical journal 27(3), pp

Claude Elwood Shannon (1948): A mathematical theory of communication. The Bell system technical journal 27(3), pp. 379–423, doi:10.1002/j.1538-7305.1948.tb01338.x

1948 doi

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.

[1] [1]

MergeShuffle: A Very Fast, Parallel Random Permutation Algorithm

Axel Bacher, Olivier Bodini, Alexandros Hollender & Jérémie Lumbroso (2015): Mergeshuffle: a very fast, parallel random permutation algorithm. arXiv preprint arXiv:1508.03167, doi:10.48550/arXiv.1508.03167

work page Pith review arXiv doi:10.48550/arxiv.1508.03167 2015

[2] [2]

Security and Safety 4, p

Haozhe Chai, Qianqian Pan & Jun Wu (2025): A survey of random number generator: Approaches, tests, novel applications in block-chain and AI driven industrial networks . Security and Safety 4, p. 2025015, doi:10.1051/sands/2025015

work page doi:10.1051/sands/2025015 2025

[3] [3]

Computing 39(1), pp

Luc Devroye (1987): A simple generator for discrete log-concave distributions. Computing 39(1), pp. 87–91, doi:10.1007/BF02307716

work page doi:10.1007/bf02307716 1987

[4] [4]

CoRR abs/1502.02539, doi:10.48550/arXiv.1502.02539

Luc Devroye & Claude Gravel (2015): Sampling with arbitrary precision . CoRR abs/1502.02539, doi:10.48550/arXiv.1502.02539. arXiv:1502.02539

work page doi:10.48550/arxiv.1502.02539 2015

[5] [5]

Efficient Online Random Sampling via Randomness Recycling

Thomas L Draper & Feras A Saad (2026): Efficient Online Random Sampling via Randomness Recycling . In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , SIAM, pp. 2473–2511, doi:10.48550/arXiv.2505.18879

work page Pith review arXiv doi:10.48550/arxiv.2505.18879 2026

[6] [6]

Journal of the ACM (JACM)60(3), pp

Michael Drmota & Wojciech Szpankowski (2013): A master theorem for discrete divide and conquer recur- rences. Journal of the ACM (JACM)60(3), pp. 1–49, doi:10.1145/2487241.2487242

work page doi:10.1145/2487241.2487242 2013

[7] [7]

Richard Durstenfeld (1964): Algorithm 235: Random permutation . Commun. ACM 7(7), p. 420, doi:10.1145/364520.364540

work page doi:10.1145/364520.364540 1964

[8] [8]

1, John Wiley & Sons, New York

William Feller (1968): An Introduction to Probability Theory and Its Applications, 3rd edition. 1, John Wiley & Sons, New York

1968