Pith. sign in

REVIEW 3 major objections 4 minor 69 references

Space-Entropy Lower Bounds for Random Sampling

T0 review · 3 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read Exact random sampling that stays within ε bits per sample of the optimal-entropy lower bound must use at least a logarithmic amount of persistent memory.

desk verdict Genuinely new lower bound: clean proof of Ω(log 1/ε) persistent space for exact entropy-efficient sampling; the advertised 1/5.116201 constant rides on an imported Diophantine bound and there's a fixable typo in (1.2), but the central result stands. read the letter →

arxiv 2607.14503 v1 pith:JMKJNAYC submitted 2026-07-16 cs.CC cs.DScs.ITmath.ITmath.PR

Thomas L. Draper , Feras A. Saad This is my paper
classification cs.CCcs.DScs.ITmath.ITmath.PR MSC 68Q1794A1711J82
keywords randomsamplingentropylossspacecomplexityonlinealgorithmsBernoullidistributionDiophantineapproximationstateinformationcontent
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

This paper establishes the first space lower bounds for entropy-efficient random sampling. Its main theorem states that any online sampler which exactly generates arbitrary discrete distributions and consumes at most H + εn + o(n) input bits in expectation — within ε bits per sample of the Shannon entropy lower bound — must use Ω(log(1/ε)) bits of persistent state. The bound is quantitative: a single Bernoulli(1/3) source (a biased coin with probability 1/3) already forces a state space of size at least (1/ε)^(1/5.116201), and handling infinitely many Bernoulli distributions tightens the requirement to at least 1/ε states. A second theorem extends a (1/(k+1)-o(1)) log(1/ε) lower bound to almost every i.i.d. k-outcome distribution. The proof reduces the problem to Diophantine approximation: the required memory is determined by how close integer combinations of log-probabilities can come to integers.

What carries the argument

The load-bearing construction is the state information content h, a nonnegative real value assigned to each state that bounds how much reusable randomness the sampler can carry across rounds; it must satisfy h(s') + log(1/p(x)) ≤ h(s) + |c| for every transition, mirroring a data-processing inequality. The paper proves such a function always exists by showing the associated difference-constraint graph has no negative cycles. A pigeonhole argument over the state space then shows that after M samples, some state repeats, so the information lost around the resulting cycle is at least the fractional part of an integer combination of log-probabilities; this yields the master bound |S| ≥ Γ_p(|S|)/ε

What would settle it

Run a brute-force search for an exact Bernoulli(1/3) sampler with fewer than 3 persistent states that achieves entropy loss below ε = 0.01 per sample; the theorem predicts log|S| ≥ 1.29 bits, i.e., at least 3 states, so such a sampler would refute the bound. A more direct check of the number-theoretic input: compute min_{1≤a≤10^6} ⟨−a log_2 3⟩ and verify it stays above (10^6)^{-4.116201}.

Watch

Extended reading notes

Core claim

In the paper's own terms, the central discovery is that persistent memory and entropy efficiency are provably at odds. Theorem 1 proves that an online random sampler that is exact for arbitrary discrete distributions and achieves entropy loss at most ε per sample must have log|S| ≥ Ω(log(1/ε)); specifically, if it can sample Bernoulli(1/3), then log|S| ≥ (1/5.116201 − o(1)) log(1/ε), and if it can sample Bernoulli(1/(2m+1)) for infinitely many m, then |S| ≥ 1/ε. Theorem 2 proves that for almost every distribution on k outcomes, any sampler generating i.i.d. samples with entropy loss ε per sample requires at least (1/(k+1)−o(1)) log(1/ε) bits of persistent state. The route is Theorem 14, whic

Load-bearing premise

The proof's load-bearing premise is the exactness condition — that the weighted sum over all input strings producing an output string equals the target product probability exactly — together with the imported number-theory bound on how close multiples of log 3 can come to integers.

Editorial extensions

If this is right

  • No sampler with constant persistent memory can provide arbitrarily small entropy loss for a non-dyadic distribution; saving ε entropy per sample forces saving log(1/ε) memory.
  • Even a fixed, single Bernoulli(1/3) source induces the logarithmic lower bound, with the constant 1/5.116201 pinned to how well log 3 resists rational approximation.
  • Supporting infinitely many Bernoulli(1/(2m+1)) distributions strengthens the bound to |S| ≥ 1/ε, so at least log(1/ε) bits of memory are needed.
  • For almost every k-outcome distribution, even the static i.i.d. sampling setting (no adaptivity across distributions) requires at least (1/(k+1)−o(1)) log(1/ε) bits of space.
  • For rational distributions with a bounded denominator d, the existing randomness-recycling sampler achieves O(log(d/ε)) bits of space, so the lower bound is tight up to constant factors in this regime.

Reading between the lines

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

  • The reduction to Diophantine approximation suggests a finer taxonomy: distributions whose log-probabilities are rationally dependent might be samplable with less than logarithmic memory; the dyadic case, where zero entropy loss and zero state are possible, is the extreme example.
  • Almost-everywhere hardness implies the typical k-outcome distribution is as hard as the hardest; constructing a sampler that exploits Diophantine structure (e.g., good rational approximations) is the natural converse direction.
  • The same cycle/information-content argument may transfer to arithmetic coding, where a precision/redundancy trade-off of the same form is known; unifying these two settings would be a natural next step.
  • A testable extension: try to realize the (1/ε) bound for Bernoulli(1/(2m+1)) with a concrete sampler family; if the true constant in the infinite-family case can be approached, it would confirm that the Diophantine bound is not only necessary but also achievable.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper proves space lower bounds for exact online random sampling. For any sampler that produces exact samples from arbitrary discrete distributions using i.i.d. uniform bits and has expected entropy loss at most ε per sample, the persistent state space S must satisfy log|S| ≥ Ω(log(1/ε)). The two concrete instantiations are: (1.1) if Bernoulli(1/3) is supported, log|S| ≥ (1/5.116201 − o(1)) log(1/ε); (1.2) if infinitely many Bernoulli distributions of the form Bernoulli(1/(2^m+1)) are supported, then |S| ≥ 1/ε. A second theorem gives (1/(k+1) − o(1)) log(1/ε) for almost every k-outcome i.i.d. distribution. The proof introduces a state information content function h, shows via difference constraints and exactness that a nonnegative h exists, then uses a pigeonhole/cycle argument to lower-bound the per-sample entropy loss by a Diophantine quantity Γ_p(|S|). The final bounds come from lower bounds on fractional parts of integer multiples of log-probabilities.

Significance. The central Ω(log(1/ε)) bound is a genuine and notable result: it resolves a conjecture from the authors' earlier work and appears to be the first space lower bound for entropy-efficient random sampling. The structural reduction is clean: exactness rules out negative cycles, the state information content potential is well defined, and the cycle argument is self-contained. A particular strength is that the proof isolates the Diophantine input, so the main logarithmic bound is robust even if the numerical constant from the external number-theory result were to change. The paper also connects the lower bound to existing upper bounds, showing that the space usage of randomness recycling is optimal up to constants. If the numerical issues described below are resolved, this is a strong contribution to the random-variate-generation literature.

major comments (3)
  1. [§6.1, Eq. (39)] The advertised constant 1/5.116201 in Theorem 1(1.1) rests entirely on the imported bound ν(1,ln2,ln3) ≤ 4.116201 attributed to [BLS18, Theorem 1], and the derivation of (39) is only sketched in one sentence. The authors need to (a) quote the exact statement from [BLS18], (b) show explicitly how a linear-independence measure over (1,ln2,ln3) yields the base-2 fractional-part bound min_{1≤a≤M} ⟨−a log 3⟩ ≥ M^{−4.116201−o(1)}, and (c) reconcile the text's assertion that the current best irrationality exponent of log 3 is 5.116201 with the claimed stronger ν ≤ 4.116201. If the constant cannot be confirmed, the theorem should be restated with an unspecified constant from Baker's theorem, which is sufficient for the central Ω(log(1/ε)) claim.
  2. [Theorem 1(1.2) and §6, Eq. (42)] The theorem statement says Bernoulli(1/(2m+1)), but the proof uses p_m = Bernoulli(1/(2^m+1)) with α_m = log(1+2^{-m}). For p = 1/(2m+1) the fractional parts of log(1/p(0)) and log(1/p(1)) are not equal, and the proof's reduction to ⟨−a α_m⟩ fails. The statement (and abstract) should be corrected to Bernoulli(1/(2^m+1)). In addition, the displayed implication in Eq. (42), |S| ≥ sup_m (1−|S|α_m)/ε, is not algebraically valid because the right-hand side depends on |S|. The correct step is to rearrange to |S| ≥ 1/(ε+α_m) for each m and then take the supremum as α_m → 0, yielding |S| ≥ 1/ε. The conclusion is right, but the written derivation needs repair.
  3. [Lemma 10, §4] The proof of Lemma 10 assumes each edge weight A_{i,j} is finite when it writes A_{i,j}+ε, yet the lemma also claims to verify that every A_{i,j} > −∞. As written, the argument is incomplete for the case A_{i,j} = −∞. A rigorous proof should first establish a finite lower bound for every A_{i,j} using reachability and the exactness of a prefix path, or handle −∞ edges separately. The statement is true, but the proof needs an additional paragraph.
minor comments (4)
  1. [§6, Eq. (41)–(42)] The symbol M is used both as an integer in (41) and as the infinite set of m in the proof of (1.2). Please use different notation to avoid confusion.
  2. [§6, proof of Theorem 1] Typo: 'reuslt' should be 'result'.
  3. [Definitions 15–16] The irrationality exponent and linear independence measure are defined as the 'minimum' real number satisfying the stated property, but such a minimum may not be attained; the standard formulation uses an infimum or the smallest exponent up to ε. Please make the definitions precise.
  4. [§6.1] The conversion between natural and base-2 logarithms in Eq. (39) should be stated explicitly. Since [BLS18] concerns ln 2 and ln 3, the bound for ⟨−a log 3⟩ should be derived with the factor ln 2 made explicit; otherwise the reader cannot verify the exponent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bounds are derived from the exactness condition plus external Diophantine-approximation results.

full rationale

The paper's central lower bound is not circular. Theorem 14 reduces the space lower bound to an intrinsic Diophantine quantity Γ_p(M) defined purely from the target distribution p, and the proof uses only the exactness condition (Definition 4, Eq. 9) to rule out negative cycles (Theorem 9), a pigeonhole/cycle argument (Lemma 13), and the state-information potential whose existence follows from those constraints. The explicit constant in Theorem 1(1.1) is imported from the external number-theory result [BLS18, Theorem 1] via Eq. (39), which lower-bounds the fractional parts Γ_p(M); this is a cited external bound, not a parameter fitted to the paper's own claims. Theorem 2 likewise relies on the external Kleinbock–Margulis theorem [KM98] and Groshev's theorem [Gro38]. The conjecture from [DS26a] is the paper's own earlier conjecture, but it is not used as a proof premise; rather, the paper proves it. Self-citations to [DS26a], [DS26b], and [DHS26] appear only in background and as upper-bound comparisons, not as load-bearing evidence for the lower-bound theorems. No step equates a defined quantity with the target outcome by construction, and no fitted value is relabeled as a prediction. The only concerns flagged—the reliability of the imported [BLS18] constant and the apparent typo in Theorem 1(1.2) (Bernoulli(1/(2m+1)) versus Bernoulli(1/(2^m+1)))—are correctness issues, not circularity.

Assumptions & free parameters 3 free parameters · 6 assumptions · 2 invented entities

The paper's core contribution is its own structural theorem (Theorem 14), which is self-contained. The only numerical inputs are external Diophantine constants from Baker/BLS18 and Kleinbock–Margulis. No ad-hoc parameters are fitted to data; the 'constants' are imported from published number theory. The invented entities are proof devices, not physical postulates. Hence the ledger is relatively light, with the main risk being the accuracy of the imported constants.

free parameters (3)
  • Diophantine constant C = ν(1, ln 2, ln 3) ≤ 4.116201 = 4.116201 (from [BLS18, Theorem 1])
    This external constant from number theory is imported in Eq. (39) and directly determines the advertised constant 1/5.116201 in Theorem 1(1.1). The paper does not derive or verify it; if it were larger, the stated bound would weaken.
  • Irrationality/linear-independence measures ν(1, log p_i) ≤ k for almost all distributions = k (from [KM98, Theorem A])
    Used in Theorem 2 to get the exponent 1/(k+1). This is a cited theorem with an external constant k; the paper verifies that the manifold hypothesis (span of derivatives) holds, but the numerical value k is imported.
  • Theorem 18 auxiliary integer q and coefficients β_i, λ_i,j = arbitrary but fixed
    These are bookkeeping parameters in the decomposition log p(x_i) = β_i/q + Σ λ_i,j α_j; they do not affect the asymptotic exponent but the q factor and Σ λ bounds are hidden in the o(1) term. Not fitted to data, but chosen adversarially for the proof.
assumptions (6)
  • standard math Standard model of an online random sampler (Definition 4): prefix-free, exhaustive, exact with respect to i.i.d. uniform bits, and states reachable.
    The lower bound applies to this formal model. It excludes samplers that, e.g., have access to non-i.i.d. entropy sources, can peek at future distributions, or may emit samples without a deterministic transition function. The paper states this model explicitly in §3.
  • standard math State information content h is nonnegative and satisfies the difference constraints h(s') + log(1/p(x)) ≤ h(s) + |c| (Definition 7).
    Feasibility is proved in §4 (Corollary 11) via Bellman-Ford and no-negative-cycle argument (Theorem 9). This is a self-contained derivation, not an external assumption, but the proof that no negative cycles exist relies on the exactness of the sampler (Definition 4, Eq. 9).
  • domain assumption Exactness in Definition 4 is strong enough to rule out negative cycles (Theorem 9) and to imply h ≥ 0 (Lemma 10).
    The proof of Theorem 9 uses that no output sequence can be generated with probability greater than the target product p_1(x_1)...p_n(x_n). This is required to rule out weight-reducing cycles in the state graph. If one only required statistical closeness rather than exactness, the no-negative-cycle lemma would fail and the whole bound would need to be re-examined.
  • domain assumption Baker's theorem / known irrationality measures of log 3: min_{1≤a≤M} ⟨−a log 3⟩ ≥ M^{-4.116201−o(1)}.
    Imported in Eq. (39), §6.1. The statement is attributed to [Bak75] and [BLS18]. The paper does not prove it and takes it as a black box; this constant is the load-bearing 'hardness of approximation' input.
  • domain assumption Khintchine-Groshev theorem / Kleinbock-Margulis Diophantine approximation on manifolds (Theorem 19 = [KM98, Theorem A]): for almost all u in an open set with span of derivatives = R^k, ν(1, f_1(u),...,f_k(u)) ≤ k.
    Used in the proof of Theorem 2 to bound ν(1, log p_1, ..., log p_k). The paper verifies the span condition with first and second derivatives for the log-probability manifold, but the measure-theoretic conclusion is an external theorem.
  • domain assumption Lebesgue-almost-every distribution on the (k−1)-simplex is Q-linearly independent in its log-probability coordinates and satisfies the linear independence measure bound.
    This is the 'almost all' statement in Theorem 2; it follows from [KM98] but is an external measure-theoretic input. Note the set of distributions with rational log-probabilities (e.g., dyadic) has measure zero, so the theorem deliberately excludes easy cases.
invented entities (2)
  • State information content function h: S → R_≥0
    purpose: Assigns an information value to each state, allowing the proof to bound information loss via difference constraints and cycles.
    h is a proof artifact introduced in Definition 7, not a physical or algorithmic entity. Its existence is proved (Corollary 11), so it is a mathematical construction rather than a postulated force/particle. It has no falsifiable handle outside the paper, but it also is not an unexplained assumption: it is derived from the sampler's transition function.
  • Γ_p(M) = inf over fractional parts of integer combinations of log-probabilities
    purpose: Central quantity connecting state count M to per-sample information loss.
    Another proof artifact (Eq. 35), defined in terms of the target distribution p. No independent evidence is needed because it is constructed and bounded within the proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Space-Entropy Lower Bounds for Random Sampling." pith.science (2026). https://pith.science/paper/JMKJNAYC

@misc{pith2026260714503,
  author       = {Pith},
  title        = {Pith review of: Space-Entropy Lower Bounds for Random Sampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JMKJNAYC}},
  note         = {Machine review of arXiv:2607.14503}
}
abstract

We prove fundamental space lower bounds for exact random sampling using an entropy source of i.i.d. uniform bits. A classic result from information theory shows that generating $n$ discrete random variables $X_1, \dots, X_n$ requires at least $H(X_1, \dots, X_n)$ input random bits on average, where $H$ is the Shannon entropy function. How much space must a random sampling algorithm use in order to approach this information-theoretically optimal entropy bound? We prove that any random sampling algorithm that is exact for arbitrary discrete target distributions and consumes at most $H(X_1,\ldots,X_n)+\varepsilon n+o(n)$ input bits in expectation for every output process must use $\Omega(\log(1/\varepsilon))$ bits of space. In fact, i.i.d. sampling from the single distribution $\mathrm{Bernoulli}(1/3)$ already forces at least $(1/{5.116201}-o(1))\log(1/\varepsilon)$ bits of space. If the sampler handles a family of infinitely many Bernoulli distributions, we show a sharper bound of at least $\log(1/\varepsilon)$ bits of space. We also prove lower bounds for general i.i.d. sampling: for almost every distribution on $k$ outcomes, the space is at least $(1/(k+1)-o(1))\log(1/\varepsilon)$ bits. The proof technique is based on a graph-theoretic analysis of the amount of information that any algorithm can store in its state. Finite state spaces force short cycles around the state-transition graph, and the loss around such cycles reduces to Diophantine lower bounds on fractional parts of integer combinations of log-probabilities. To the best of our knowledge, these results comprise the first known space lower bounds for entropy-efficient random sampling.

Figures

Figures reproduced from arXiv: 2607.14503 by the authors.

Figure 1
Figure 1. Two iterations of the interval algorithm [ [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Examples of random state extraction when using randomness recycling and DDG tree [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Visualization of the information lost during a state transition of a sampler. [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

69 extracted references · 3 linked inside Pith

  1. [1]

    Probabilistic

    Gill, John Thomas , school =. Probabilistic. 1972 , chapter =

    1972

  2. [2]

    Journal für die reine und angewandte Mathematik (Crelles Journal) , doi =

    Theorie der einfachen Ungleichungen , author =. Journal für die reine und angewandte Mathematik (Crelles Journal) , doi =

  3. [3]

    Information and Computation , volume =

    The Functions Erf and Erfc Computed with Arbitrary Precision and Explicit Error Bounds , author =. Information and Computation , volume =. 2012 , publisher =

    2012

  4. [4]

    Computing the Incomplete Gamma Function to Arbitrary Precision , author =. Proc. International Conference on Computational Science and Its Applications (ICCSA) , pages =. 2003 , doi =

    2003

  5. [5]

    , title =

    Shannon, Claude E. , title =. The Bell System Technical Journal , volume =. 1948 , publisher =

    1948

  6. [6]

    1953 , publisher =

    Statistical Tables for Biological, Agricultural And Medical Research , author =. 1953 , publisher =

    1953

  7. [7]

    Communications of the ACM , volume =

    Durstenfeld, Richard , title =. Communications of the ACM , volume =. 1964 , publisher =

    1964

  8. [8]

    Annals of Mathematical Statistics , volume =

    The Efficient Construction of an Unbiased Random Sequence , author =. Annals of Mathematical Statistics , volume =. 1972 , publisher =. doi:10.1214/aoms/1177692552 , address =

    arXiv 1972

Show all 69 references
  1. [9]

    Algorithms and Complexity: New Directions and Recent Results , pages =

    The Complexity of Nonuniform Random Number Generation , author =. Algorithms and Complexity: New Directions and Recent Results , pages =. 1976 , publisher =

    1976

  2. [10]

    , title =

    Walker, Alastair J. , title =. ACM Transactions on Mathematical Software , volume =. 1977 , publisher =

    1977

  3. [11]

    1986 , address =

    Non-Uniform Random Variate Generation , author =. 1986 , address =

    1986

  4. [12]

    and Zuckerman, D

    Impagliazzo, R. and Zuckerman, D. , title =. Proc. 30th Annual Symposium on Foundations of Computer Science (FOCS) , year =

  5. [13]

    IEEE Transactions on Software Engineering , volume =

    A Linear Algorithm for Generating Random Numbers with a Given Distribution , author =. IEEE Transactions on Software Engineering , volume =. 1991 , publisher =

    1991

  6. [14]

    IEEE Transactions on Information Theory , volume =

    Interval Algorithm for Random Number Generation , author =. IEEE Transactions on Information Theory , volume =. 1997 , publisher =

    1997

  7. [15]

    Journal of Complexity , volume =

    Tomoyuki Yamakami , title =. Journal of Complexity , volume =. 1999 , doi =

    1999

  8. [16]

    and Huber, Mark , booktitle =

    Fill, James A. and Huber, Mark , booktitle =. The Randomness Recycler: A New Technique For Perfect Sampling , year =

  9. [17]

    and Jakobsson, M

    Juels, A. and Jakobsson, M. and Shriver, E. and Hillyer, B.K. , journal =. How To Turn Loaded Dice Into Fair Coins , year =

  10. [18]

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , volume =

    Two Algorithms for Random Number Generation Implemented by Using Arithmetic of Limited Precision , author =. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , volume =. 2003 , month = oct, publisher =

    2003

  11. [19]

    David J. C. MacKay , title =

  12. [20]

    2004 , month = feb, howpublished =

    Willekens, Jacques , title =. 2004 , month = feb, howpublished =

    2004

  13. [21]

    arXiv , volume =

    Bit Recycling For Scaling Random Number Generators , author =. arXiv , volume =. 2010 , doi =

    2010

  14. [22]

    An Irregular Mind: Szemer

    Trevisan, Luca , title =. An Irregular Mind: Szemer. 2010 , pages =

    2010

  15. [23]

    arXiv , volume =

    Optimal Discrete Uniform Generation from Coin Flips, and Applications , author =. arXiv , volume =. 2013 , doi =

    2013

  16. [24]

    Algorithmica , volume =

    Bringmann, Karl and Panagiotou, Konstantinos , title =. Algorithmica , volume =. 2017 , publisher =

    2017

  17. [25]

    and Vercauteren, Frederik and Verbauwhede, Ingrid , booktitle =

    Roy, Sinha S. and Vercauteren, Frederik and Verbauwhede, Ingrid , booktitle =. High Precision Discrete. 2013 , doi =

    2013

  18. [26]

    ACM Transactions on Modeling and Computer Simulation , volume =

    Lemire, Daniel , title =. ACM Transactions on Modeling and Computer Simulation , volume =. 2019 , publisher =

    2019

  19. [27]

    1502.02539v6 , month = nov, year =

    Random Variate Generation Using Only Finitely Many Unbiased, Independently and Identically Distributed Random Bits , author =. 1502.02539v6 , month = nov, year =

    arXiv

  20. [28]

    Proceedings of the ACM on Programming Languages , volume =

    Optimal Approximate Sampling from Discrete Probability Distributions , author =. Proceedings of the ACM on Programming Languages , volume =. 2020 , publisher =. doi:10.1145/3371104 , address =

    2020 doi

  21. [29]

    The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete Probability Distributions , author =. Proc. 23rd International Conference on Artificial Intelligence and Statistics , volume =

  22. [30]

    Journal of Logical and Algebraic Methods in Programming , volume =

    Coalgebraic Tools for Randomness-Conserving Protocols , author =. Journal of Logical and Algebraic Methods in Programming , volume =. 2022 , doi =

    2022

  23. [31]

    Optimal Rolling of Fair Dice Using Fair Coins , author =

  24. [32]

    Software: Practice and Experience , volume =

    Brackett-Rozinsky, Nevin and Lemire, Daniel , title =. Software: Practice and Experience , volume =. 2025 , doi =

    2025

  25. [33]

    and Lee, Wonyeol , title =

    Saad, Feras A. and Lee, Wonyeol , title =. Proceedings of the ACM on Programming Languages , volume =. 2025 , publisher =

    2025

  26. [34]

    and Saad, Feras A

    Draper, Thomas L. and Saad, Feras A. , title =. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2026 , doi =

    2026

  27. [35]

    2507.00915 , month = jul, year =

    MichelangeRoll: Sculpting Rational Distributions Exactly and Efficiently , author =. 2507.00915 , month = jul, year =

    arXiv

  28. [36]

    2020 , publisher =

    Foundations of Probabilistic Programming , editor =. 2020 , publisher =

    2020

  29. [37]

    The Discrete

    Canonne, Cl\'. The Discrete. Proc. 34th International Conference on Neural Information Processing Systems (NeurIPS) , series =. 2020 , eprint =

    2020

  30. [38]

    Entropy , volume =

    Chattopadhyay, Eshan , title =. Entropy , volume =. 2022 , doi =

    2022

  31. [39]

    The Intel® Random Number Generator , author =

  32. [40]

    Quantum Random Number Generators , author =. Rev. Mod. Phys. , volume =. 2017 , publisher =

    2017

  33. [41]

    and Koch, Julian and Antkowiak, Philipp L

    Meiser, Linda C. and Koch, Julian and Antkowiak, Philipp L. and Stark, Wendelin J. and Heckel, Reinhard and Grass, Robert N. , title =. Nature Communications , volume = 11, eid = 5869, month = nov, year =

  34. [42]

    Monte Carlo Method , editor =

    Various Techniques Used in Connection with Random Digits , author =. Monte Carlo Method , editor =. 1951 , publisher =

    1951

  35. [43]

    Iterating von

    Peres, Yuval , journal =. Iterating von. 1992 , publisher =

    1992

  36. [44]

    Entropy , volume =

    Prasitsupparote, Amonrat and Konno, Norio and Shikata, Junji , title =. Entropy , volume =. 2018 , doi =

    2018

  37. [45]

    A Generalization of

    Pae, Sung-Il , journal =. A Generalization of. 2015 , doi =

    2015

  38. [46]

    Randomizing Functions: Simulation of a Discrete Probability Distribution Using a Source of Unknown Distribution , journal =

    Pae,. Randomizing Functions: Simulation of a Discrete Probability Distribution Using a Source of Unknown Distribution , journal =. 2006 , volume =

    2006

  39. [47]

    IEEE Transactions on Information Theory , volume =

    Pae, Sung-Il , title =. IEEE Transactions on Information Theory , volume =. 2020 , pages =. doi:10.1109/TIT.2019.2962480 , address =

    2020

  40. [48]

    Combinatorica , volume =

    Blum, Manuel , title =. Combinatorica , volume =. 1986 , doi =

    1986

  41. [49]

    ACM Transactions on Mathematical Software , volume =

    Sampling Exactly from the Normal Distribution , author =. ACM Transactions on Mathematical Software , volume =. 2016 , month = jan, publisher =

    2016

  42. [50]

    Exact and Efficient Generation of Geometric Random Variates and Random Graphs , author =. Proc. 40th International Colloquium on Automata, Languages, and Programming (ICALP) , pages =. 2013 , publisher =

    2013

  43. [51]

    and Luk, Wayne , booktitle =

    Thomas, David B. and Luk, Wayne , booktitle =. Sampling from the Exponential Distribution Using Independent Bernoulli Variates , year =

  44. [52]

    Scientific Reports , volume =

    True Randomness from Big Data , author =. Scientific Reports , volume =. 2016 , publisher =

    2016

  45. [53]

    Annals of Mathematics , volume =

    Integer Multiplication In Time O(n n) , author =. Annals of Mathematics , volume =. 2021 , fpublisher =

    2021

  46. [54]

    2005 , doi =

    Randomness Requirements for Security , author =. 2005 , doi =

    2005

  47. [55]

    Granlund, Torbj. GNU

  48. [56]

    IEEE Transactions on Information Theory , volume =

    Efficient Rejection Sampling in the Entropy-Optimal Range , author =. IEEE Transactions on Information Theory , volume =. 2026 , doi =

    2026

  49. [57]

    Generating Random Floating-Point Numbers by Dividing Integers: A Case Study , booktitle =

    Goualard, Fr. Generating Random Floating-Point Numbers by Dividing Integers: A Case Study , booktitle =. 2020 , doi =

    2020

  50. [58]

    Communications in Statistics - Simulation and Computation , volume =

    Mendo, Luis , title =. Communications in Statistics - Simulation and Computation , volume =. 2025 , publisher =

    2025

  51. [59]

    Information and Computation , volume =

    Feldman, David and Impagliazzo, Russell and Naor, Moni and Nisan, Noam and Rudich, Steven and Shamir, Adi , title =. Information and Computation , volume =. 1993 , doi =

    1993

  52. [60]

    and Leiserson, Charles E

    Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford , title =. 2022 , edition =

    2022

  53. [61]

    On Precision - Redundancy Relation in the Design of Source Coding Algorithms , author =

  54. [62]

    IEEE Transactions on Information Theory , volume =

    Shayevitz, Ofer and Meron, Eado and Feder, Meir and Zamir, Ram , title =. IEEE Transactions on Information Theory , volume =. 2014 , doi =

    2014

  55. [63]

    1975 , doi =

    Baker, Alan , title =. 1975 , doi =

    1975

  56. [64]

    Journal of Number Theory , volume =

    On the Irrationality Measure of 3 , author =. Journal of Number Theory , volume =. 2014 , doi =

    2014

  57. [65]

    Bondareva, I. V. and Luchin, M. Yu. and Salikhov, V. Kh. , title =. Chebyshevskii Sbornik , volume =. 2018 , furl =

    2018

  58. [66]

    Groshev, A. V. , title =. Doklady Akademii Nauk SSSR , volume =. 1938 , furl =

    1938

  59. [67]

    SIAM Journal on Discrete Mathematics , volume =

    Kindler, Guy and Romik, Dan , title =. SIAM Journal on Discrete Mathematics , volume =. 2004 , doi =

    2004

  60. [68]

    D. Y. Kleinbock and G. A. Margulis , title =. Annals of Mathematics , volume =. 1998 , doi =

    1998

  61. [69]

    2607.13828 , month = jul, year =

    Online Random Sampling with Real Probabilities , author =. 2607.13828 , month = jul, year =

    arXiv

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.