1 Introduction↩︎

The uniform generation of combinatorial structures is a cornerstone of computer science. In particular, the generation of binary words of length \(n\) with exactly \(k\) ones (or equivalently, random subsets of size \(k\) from a set of \(n\) elements) is an important primitive. While the time complexity of these generators has been studied extensively, a secondary cost metric has gained prominence in recent years: the consumption of random bits.

In many computing environments, pseudo-random bits are cheap. However, in high-security applications, cryptography, and embedded systems, randomness is often derived from hardware true random number generators (TRNGs) [@chai2025survey]. In these contexts, random bits are an expensive resource and can be a bottleneck for random generation. When generating a combinatorial structure uniformly at random from a finite set of \(F\) possibilities, the information-theoretic entropy [@shannon1948mathematical] of the generated object is \(\log_2 F\). By Shannon’s source coding theorem, this entropy establishes a lower bound: any algorithm relying on fair coin flips (unbiased random bits) must consume, on average, at least \(\mathcal{H} = \log_2 F\) bits to produce a perfectly uniform sample. For the problem at hand of generating binary words of length \(n\) with exactly \(k\) ones, the size of the state space is \(\binom{n}{k}\). Consequently, we strive to give algorithms whose expected random bit consumption is asymptotically close to \(\log_2 \binom{n}{k}\).

It is important to emphasize that all algorithmic complexities presented in this work–both in terms of execution time and random bit consumption–are stated as expected (average-case) bounds. This is a necessity as generating a uniform random integer over a range whose size is not a power of 2 (for instance, a uniform integer in \(\{1, 2, 3\}\)) from a stream of fair coin flips cannot be achieved in bounded time [@Knuth1976TheCO]. We call an algorithm first order entropic (resp. near-entropic) if its random bit consumption is asymptotically in \(\mathcal{H} + o(\mathcal{H})\) (resp. in \((1+\varepsilon)\mathcal{H} + o(\mathcal{H})\), for any \(\varepsilon > 0\)) where \(\mathcal{H} = \log_2 \binom{n}{k}\) is the entropy of our structure.

Generating fixed Hamming weight binary words is a two-parameter problem defined by length \(n\) and Hamming weight \(k\) (where we can assume \(k \le n/2\) by symmetry). To analyze our algorithms asymptotically, we evaluate complexities as \(n \to \infty\) along the trajectory \(k \sim n^\beta\) for a fixed \(\beta \in (0, 1)\). We call this setting the polynomially sparse regime. Current generation methods generally bifurcate based on the number of \(1\)s. For highly sparse inputs (\(k \ll n\)), the partial Fisher-Yates shuffle [@FisherYates] is efficient. Conversely, for denser inputs (\(k = \Omega(n^{2/3 + \varepsilon})\) for any \(\varepsilon > 0\)), an adaptation of the Merge algorithm [@bacher2015mergeshuffle] performs well by initially approximating the target word with Bernoulli(\(k/n\)) variables and subsequently correcting for bias.

To the best of our knowledge, no prior algorithm simultaneously achieves linear time complexity \(O(n)\) and near-optimal entropic cost in the polynomially sparse regime with \(\beta \in (0,2/3]\).

Our Contribution↩︎

In this paper, we present a novel algorithm that bridges this gap. We propose a generator for uniform binary words that is both entropically near-optimal and computationally linear.

We observe that the standard Fisher-Yates procedure, while inserting the \(k\) ones among the \(n-k\) zeros, implicitly constructs a uniform random permutation on these \(1\)s. In order to capitalize on this implicit uniform random permutation, we introduce an algorithm for deconstructing uniform random permutations. The procedure is an emulation of a generative process in reverse, transforming the uniform random permutation into independent random bits. In a way, we “recycle” the randomness usually discarded during the insertion process. It is worth noting that the broader paradigm of entropy recycling in random generation is concurrently being explored in some different frameworks, see [@draper2026efficient] for online sampling and [@DevroyeG15] for recycling bits while sampling batches of i.i.d variables.

The random bits obtained at the end of the generation can then be used to do something else, having an effective entropic random bit consumption (the number of random bit used in the process minus the number of random bits returned) that tightly matches the lower bound. This allows entropic generation of batches of binary words of size \(n\) with \(k\) ones, by using the random bits recycled for the previous words to generate the next one.

Alternatively, we can stop the insertions mid process, the smaller uniform random permutation can then be recycled mid-process, and the random bits reinjected into the generation procedure. Doing this multiple times allow a \(1+\varepsilon\) entropic generation for any \(\varepsilon > 0\), meaning that the generation algorithm is near-entropic. The algorithm remains linear.

The remainder of this paper is organized as follows. 2 presents two algorithms for sampling binary words that are we adapt in the subsequent sections. 3 details our “entropy recycling” mechanism for uniform random permutations. 4 presents the full sampling algorithm and its complexity analysis.

2 Existing Algorithm↩︎

2.1 The Fisher-Yates Insertion Algorithm↩︎

A standard algorithm for generating a uniform random permutation is the Fisher-Yates shuffle, also known as the Knuth shuffle [@FisherYates]. While typically used to permute \(n\) distinct elements, the procedure can be adapted to generate random binary words of length \(n\) with fixed Hamming weight \(k\).

The adaptation exploits the indistinguishability of the 0s. Instead of performing a full shuffle of \(n\) elements, we perform a partial shuffle restricted to the \(k\) ones. The array is initialized with \(n-k\) zeros followed by \(k\) ones. The algorithm then iterates backwards from \(n\) down to \(n-k+1\). In each step \(i\), the element at position \(i\) (guaranteed to be a 1 prior to the swap) is exchanged with an element at a uniformly selected index \(j \in \{1, \cdots, i\}\).

2.2 The Balanced Merge Procedure↩︎

The core of the MergeShuffle algorithm from [@bacher2015mergeshuffle] is the BalanceMerge procedure, which combines two previously shuffled sub-arrays of size \(n/2\) into a single randomly shuffled array of size \(n\). When the input sub-arrays are of equal size (the “balanced” case), this procedure is highly efficient in terms of random bits. This corresponds to generating a balanced binary word (i.e. with \(k=n/2\)).

The algorithm proceeds in two distinct phases:

1. Bit-Driven Selection: We iterate through the target array. At each step, a random bit is generated (a coin flip). If the bit is 0, we select the next element from the left sub-array; if 1, we select from the right. This loop continues until one of the two sub-arrays is completely exhausted.

2. Fisher-Yates Completion: Once one sub-array is empty, the remaining elements from the other sub-array are not simply appended. To ensure a uniform distribution, they are inserted into the final array using a partial Fisher-Yates shuffle. Specifically, each remaining element is swapped with a randomly selected position in the valid range processed so far.

When \(k=n/2\) generating a uniform binary balanced word using this method consumes \(n + \Theta(\sqrt{n} \log n)\) random bits on average. [@bacher2015mergeshuffle].

3 Random Bit Recycling↩︎

3.1 Random Bit Extraction↩︎

In the standard paradigm of random generation, an algorithm consumes a stream of independent, uniform random bits to produce a combinatorial structure [@Knuth1976TheCO]. Here, we invert this process: in the case of a uniform random permutation, we map the uniform combinatorial structure back into a sequence of independent, uniform random bits. We call this random bit extraction or random bit recycling as we give back some of the bits used to generate the structure.

Consider a uniform balanced binary word \(W \in \{0,1\}^{n}\), which consists of exactly \(n/2\) zeros and \(n/2\) ones. The entropy of this structure is \(\log_2 \binom{n}{n/2}\), which by Stirling’s approximation is \(n - \frac{1}{2}\log_2(\pi n) + O(1)\). Our goal is to extract a sequence of independent random bits from \(W\) whose expected length is as close as possible to \(\mathcal{H}\), the entropy of the structure, which, by Shannon’s source coding theorem [@shannon1948mathematical], is the maximum amount that one could extract.

We achieve this by conceptually reversing the generative BalancedMerge procedure. To do so, we first sample the simulated depletion condition: the number of remaining elements \(M\) whose distribution is given by 1, then emulate in reverse the \(M\) Fisher-Yates insertions. The resulting word is composed of independent unbiased bits.

The full extraction procedure is detailed in Algorithm 3.

3.2 Recursive Deconstruction of Uniform Permutations↩︎

Using the recycling mechanism for balanced binary words, we deconstruct uniform random permutations. The core idea is to split the permutation of size \(n\) into one balanced binary word and two uniform permutations of size \(n/2\). This gives algorithm 4.

The entropy of such a uniform permutation is \(\log_2(n!) = n \log_2 n - O(n)\). We demonstrate that our algorithm achieves this optimal bound up to a linear error term.

4 Entropic Sampling of Sparse Binary Words↩︎

4.1 Extracting Fisher-Yates Entropy via Distinguishable Insertions↩︎

Morally, the reason the partial Fisher-Yates shuffle fails to be entropic for generating combinations is that it implicitly generates an ordering on the \(1\)s that are inserted, from their order of insertion. This wastes \(\log_2(k!)\) random bits on an internal ordering that is ultimately ignored. We can recover this “wasted” entropy by making this ordering explicit, extracting it, and recycling it.

Instead of initializing the array with indistinguishable \(1\)s, we initialize it with distinct identifiers \(1, 2, \cdots, k\). We then run the partial Fisher-Yates shuffle as before. Once the \(k\) insertions are complete, the array indices containing non-zero elements dictate the generated binary word. Additionally, the sequence of these non-zero elements, when read from left to right, forms a uniform random permutation of the set \(\{1, \cdots, k\}\).

By isolating this permutation and feeding it into the DeconstructPermutation algorithm, we “give back” the excess random bits consumed during the generation phase. This coupling of Fisher-Yates generation with recursive deconstruction yields an effective algorithm for the polynomially sparse regime.

4.2 Near Entropic Binary Word Sampling↩︎

We now present a linear-time, near-entropic algorithm that generates a uniform binary word of length \(n\) with \(k \sim n^\beta\) \(1\)s (where \(\beta \in (0,1)\)). Algorithm 5 simply consumes a small number of random bits, and it does not “give back” random bits. It works by chaining generation and deconstruction phases across \(l+1\) discrete steps. The entropy “wasted” on the internal ordering of the \(1\)s inserted during step \(i\) is extracted and recycled to power the insertions of step \(i+1\). We define the constant \(\alpha := \frac{1-\beta}{1-\beta^{l+1}}\). On the \(i\)-th step (for \(i=0, \cdots, l\)), we insert \(k_i = \alpha \beta^i k\) elements. The procedure is described in algorithm 5.

5 Conclusion↩︎

We presented a linear-time (in the length of the generated word) algorithm for the uniform generation of fixed Hamming weight binary words in the previously untreated polynomially sparse regime. Our method achieves a random bit consumption that matches the information-theoretic lower bound up to a multiplicative factor of \(1+\varepsilon\) for a chosen \(\varepsilon > 0\).

The algorithm is based on a random bit recycling procedure. We believe this paradigm of entropy deconstruction is generalizable to other combinatorial contexts. Most notably, we are currently working to adapt this mechanism to recycle the “wasted” entropy from the rejected structures that inherently occur during exact-size generation with Boltzmann-type samplers. We believe that there is practical relevance to this recycling paradigm: it allows for entropic generation when sampling structures in large batches (by pooling recovered bits across iterations), or almost-entropic generation for single instances when the recycling is chained recursively within the generation procedure itself like done in algorithm 5.

More broadly, we believe that evaluating randomized algorithms through the lens of random bit consumption provides a more precise analytical framework than standard runtime analysis alone. Treating random bits as a resource, can expose inefficiencies of standard methods and provides a guide for the conception of new algorithms.

Acknowledgments: The authors would like to express their gratitude to Étienne Objois for many valuable and careful comments. This research was supported by anr-fwf project PAnDAG ANR-23-CE48-0014-01.