Entropy Optimal Discrete Sampling and Randomness Extraction

This direction is merged into another direction: randomness extraction. Its last version stays readable and citable here.

Version 1 of 127 papers66 conceptsfrozen 2026-10-04

In computational science, we often treat randomness as a free resource. We call rand() and assume a stream of perfect bits is available. However, in high-stakes environments—such as cryptography, large-scale Monte Carlo simulations, or hardware-constrained devices—randomness is an expensive commodity.

Recent research has converged on a singular challenge: how can we generate complex probability distributions while consuming the absolute minimum number of random bits, without requiring an impractical amount of memory? This direction bridges the gap between the theoretical limits of Shannon entropy and the practical constraints of modern hardware.

The Hidden Inefficiency of Standard Sampling

To understand the problem, consider the task of simulating a "loaded die" with specific weights. The industry-standard Alias method allows us to sample in constant time, but it is "entropy-blind." It typically consumes a fixed number of bits (often 32 or 64 bits from a floating-point number) to make a single decision, even if the underlying distribution only requires 2 bits of information to resolve.

As Feras Saad, Cameron Freer, and Martin Rinard point out in their work on the Fast Loaded Dice Roller (FLDR), this creates a hidden bottleneck. When the source of randomness is a slow physical process—like the avalanche photodiodes described by Fang‐Xiang Wang and colleagues in their Quantum Random Number Generator—wasting bits directly translates to slower system performance.

Reaching the Shannon Limit with Dyadic Trees

The theoretical minimum number of fair coin flips needed to generate a sample from a distribution $P$ is given by its Shannon entropy, $H(P)$. Historically, algorithms that reached this limit required "Knuth-Yao" interval trees, which could grow exponentially large, making them useless for distributions with many outcomes.

The breakthrough in this field has been the development of "near-optimal" samplers that maintain a small memory footprint. The FLDR algorithm achieves this by using dyadic rationals to approximate distributions. By representing weights as binary expansions, the sampler only "consumes" bits of entropy as needed to traverse a tree. If the first bit of a coin flip already determines the outcome, the algorithm stops, saving the remaining entropy for the next sample.

This "lazy" consumption is further refined in the Amplified Loaded Dice Roller (ALDR) by Feras Saad and T. Draper. They demonstrate that by setting a precision parameter to double the required bit depth, one can guarantee that the average entropy cost stays within 2 bits of the Shannon limit while keeping memory scaling linearithmic.

Randomness Recycling and Online Sampling

The next evolution of this idea is randomness recycling. In many algorithms, a coin flip isn't just "used up"; it often contains leftover information. For example, if you flip a coin to decide between three options, you haven't used the full "power" of that bit.

T. Draper explores this in Efficient Online Random Sampling via Randomness Recycling. By integrating entropy recycling into structures like alias tables, it becomes possible to "carry over" the unused fractional bits to the next sampling task. This is particularly effective for complex tasks like the Fisher-Yates shuffle or generating discrete Gaussians, where the required bits per sample can be reduced by up to a factor of ten.

The Theoretical Flip Side: Extraction from Weak Sources

While one side of the research focuses on using bits efficiently, the other focuses on producing them from "weak" or "dirty" sources. This is the domain of randomness extractors.

Traditional extractors often struggle when the source entropy is very low—what Boaz Barak, Ronen Shaltiel, and Avi Wigderson describe as the "square root barrier" in their landmark 2-source disperser paper. Their work, along with that of David Zuckerman on leakage-resilient sharing, seeks to build "cleaning" functions that can extract pure randomness even from highly biased or correlated physical sources.

The common thread is the entropy-rate. As Ahmad Beirami and Hamid Nejati argue, the entropy-rate is the true fundamental limit of any random process. Whether you are building a chaotic-map generator or a discrete sampler, the goal is the same: to operate as close to that rate as possible without incurring an exponential cost in space or time.

Summary of the Intuition

The research direction can be viewed as a three-way optimization problem:

  1. Entropy Efficiency: Use as few bits as possible (approaching Shannon's limit).
  2. Memory Efficiency: Avoid exponential state-space growth (staying linear or logarithmic).
  3. Exactness: Maintain perfect statistical distributions without floating-point errors.

By moving away from "block-based" sampling (where we take 64 bits at a time) toward "bit-level" or "arithmetic" sampling, researchers like Saad and Draper have shown that we can have all three. We can now simulate complex systems using only the information strictly necessary to describe them, effectively "recycling" the randomness that was previously thrown away.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_entropy_optimal_discrete_sampling_and_ra_892eb42e,
  title = {Entropy Optimal Discrete Sampling and Randomness Extraction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/entropy-optimal-discrete-sampling-and-randomness-extraction/rdr_892eb42e69794be1a3ec313cd384d542},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_entropy_optimal_discrete_sampling_and_ra_892eb42e_v1,
  title = {Entropy Optimal Discrete Sampling and Randomness Extraction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/entropy-optimal-discrete-sampling-and-randomness-extraction/rdr_892eb42e69794be1a3ec313cd384d542/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}