Entropic Generation of Binary Words

Problem Statement
The paper addresses the uniform generation of binary words of length $n$ with a fixed Hamming weight $k$ (equivalent to sampling $k$-subsets from $n$ elements). While the time complexity of such generators is well-studied, the authors focus on the consumption of random bits as a critical resource, particularly in contexts relying on hardware true random number generators (TRNGs) where randomness is expensive.

The information-theoretic lower bound for generating a uniform sample from a state space of size $\binom{n}{k}$ is $H = \log_2 \binom{n}{k}$ bits. The goal is to design algorithms where the expected random bit consumption is asymptotically close to this entropy $H$. The paper specifically targets the "polynomially sparse regime," defined by $k \sim n^\beta$ for a fixed $\beta \in (0, 1)$. Existing methods often bifurcate: partial Fisher-Yates shuffles are efficient for highly sparse inputs ($k \ll n$), while adaptations of the MERGE algorithm work well for denser inputs ($k = \Omega(n^{2/3+\epsilon})$). However, no prior algorithm simultaneously achieved linear time complexity $O(n)$ and near-optimal entropic cost in the intermediate sparse regime where $\beta \in (0, 2/3]$.

Methodology: Random Bit Recycling
The core innovation is a paradigm of "random bit recycling." The authors observe that standard generation methods, such as the Fisher-Yates shuffle, implicitly generate internal structures (like permutations) that are discarded after the combinatorial object is formed. This process "wastes" entropy.

The proposed methodology inverts the standard generation process:

1. Deconstruction: Instead of only consuming bits to build a structure, the algorithm extracts independent random bits from the generated structure (or intermediate states) by conceptually reversing the generative process.
2. Recycling: These extracted bits are then reused ("recycled") to power subsequent generation steps, reducing the net consumption of fresh random bits.

The paper details two primary mechanisms for this:

• Balanced Binary Words: For balanced words ($k=n/2$), the authors reverse the "Balanced Merge" procedure. By sampling the depletion condition (modeled by a Banach Matchbox distribution) and reversing the Fisher-Yates insertion steps, they extract a sequence of independent uniform bits.
• Permutation Deconstruction: For general permutations, the algorithm recursively splits a permutation of size $n$ into a balanced binary word and two smaller permutations. The balanced word is deconstructed to yield bits, and the process recurses on the sub-permutations. This achieves an extraction rate of $n \log_2 n - O(n)$ bits from a permutation of size $n$.

Key Contributions and Algorithms
The paper presents a novel generator for uniform binary words that bridges the gap between linear time complexity and near-optimal entropic cost in the polynomially sparse regime.

1. Distinguishable Fisher-Yates with Deconstruction:
   To generate a word with weight $k$, the authors initialize the array with distinct identifiers $1, \dots, k$ rather than indistinguishable ones. They perform a partial Fisher-Yates shuffle. The resulting array indices define the binary word, while the sequence of non-zero elements forms a uniform random permutation of size $k$. This permutation is then fed into the DeconstructPermutation algorithm to recover the "wasted" entropy ($\log_2 k!$ bits).

   • Result: This yields a first-order entropic algorithm. The net bit consumption is $\log_2 \binom{n}{k} + O(k)$. Since $O(k) = o(\log_2 \binom{n}{k})$ in the target regime, the consumption asymptotically matches the entropy lower bound. The runtime is $O(n)$.

2. Chained Recycling for Near-Entropic Generation:
   To achieve near-entropic generation (where consumption is $(1+\epsilon)H$ for any $\epsilon > 0$), the authors propose an iterative approach (Algorithm 5: l-ChainedRecyclingFY).

   • The generation is split into $l+1$ steps. In each step $i$, a subset of $k_i$ elements is inserted using Fisher-Yates.
   • The permutation formed by these elements is immediately deconstructed to extract random bits.
   • These recycled bits are used to fund the insertions of the next step ($i+1$).
   • By tuning the parameter $l$, the multiplicative over-consumption of random bits can be bounded arbitrarily close to 1.
   • Result: This algorithm runs in $O(n)$ time and achieves a bit complexity of $\frac{1-\beta}{1-\beta^{l+1}} k \log_2 n + O(k)$, which approaches the entropy bound as $l$ increases.

Results

• Time Complexity: The proposed algorithms run in expected linear time, $O(n)$, in the polynomially sparse regime ($k \sim n^\beta, \beta \in (0,1)$).
• Bit Complexity:
  • The distinguishable insertion method is first-order entropic: consumption is $\log_2 \binom{n}{k} + O(k)$.
  • The chained recycling method is near-entropic: for any $\epsilon > 0$, the algorithm can be configured to consume $(1+\epsilon)\log_2 \binom{n}{k} + o(\log_2 \binom{n}{k})$ bits.
• Optimality: The algorithms are nearly optimal in terms of random bit consumption, closely matching the Shannon entropic lower bound derived from information theory.

Significance and Claims
The paper claims to provide the first algorithm that simultaneously achieves linear time complexity and near-optimal entropic cost for generating fixed Hamming weight binary words in the polynomially sparse regime.

The authors emphasize that treating random bits as a scarce resource provides a more precise analytical framework than standard runtime analysis alone. They posit that the paradigm of "entropy deconstruction" and recycling is generalizable. Specifically, they note ongoing work to adapt this mechanism to recycle "wasted" entropy from rejected structures in Boltzmann-type samplers for exact-size generation. The paper concludes that this approach allows for efficient entropic generation in large batches (by pooling recovered bits) or near-entropic generation for single instances via recursive chaining.