MichelangeRoll: Sculpting Rational Distributions Exactly and Efficiently

Hsin-Po Wang; Jui-Hsiang Shao

MichelangeRoll: Sculpting Rational Distributions Exactly and Efficiently

T0 review · 0 major / 7 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read MichelangeRoll samples any rational distribution exactly with H(D)+ε fair coin tosses per sample and polynomial memory.

desk verdict A clean, honest algorithm paper that breaks the '+2' barrier by recycling leftover entropy with ANS; the proof holds, and the result is real though incremental over concurrent work. read the letter →

arxiv 2507.00915 v2 pith:E6RMSDUW submitted 2025-07-01 cs.IT math.IT

Jui-Hsiang Shao , Hsin-Po Wang This is my paper · ORCID

classification cs.ITmath.IT MSC 68Q8794A1760C05

keywords exactrandomnumbergenerationentropy-optimalsamplingasymmetricnumeralsystemsrationaldistributionsKnuth-YaodecisiontreesrandomnessrecyclingdiscretedistributionsimulationShannonentropy

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 claims that exact simulation of an arbitrary rational distribution from fair coin tosses can be made essentially as cheap as Shannon's entropy bound: $H(D)+\varepsilon$ tosses per sample for any small $\varepsilon>0$, with memory and time polynomial in the description of the distribution. Previously, exact simulation paid a fixed overhead of about two tosses per sample, and the paper argues that this overhead is not a fundamental price of exactness but an artifact of discarding leftover randomness. MichelangeRoll recycles that leftover randomness with an asymmetric numeral system, and the proof shows the remaining losses are $O(\varepsilon)$ per sample. If the theorem is right, exact samplers become competitive with approximate samplers on entropy and resources, especially for low-entropy distributions where the old fixed overhead dominated.

What carries the argument

The load-bearing object is the asymmetric numeral system (ANS), an entropy-coding scheme that compresses a stream of symbols into a single integer by alternating multiplication and addition. Here it takes a residual pair $(N_t,S_t)$ and updates one state $A_t$; Lemma 4 shows the aggregated state is uniform in $\{0,1,\ldots,N_1\cdots N_t-1\}$, so no randomness is lost inside the accumulator. The companion bit-extraction loop—output the parity of $A_t$, halve both $A_t$ and $N_t$, and stop when $N_t$ is odd and $A_t=N_t-1$—turns that integer back into fair, independent coin tosses, and Lemma 6's expected-toss bound $>\log_2(N)-3$ makes the recycling loss small. The subinterval construction with $M=\lfloor 2^{j+k}/m\rfloor m$ keeps the rejection rate and the reset frequency low enough that the combined loss is $O(\varepsilon)$ per sample.

What would settle it

Evaluate the recurrence $T(N)=1+T(N/2)$ for even $N$ and $T(N)=((N-1)/N)(1+T((N-1)/2))$ for odd $N$ up to large $N$ (or find a closed form) and check whether $T(N)\ge \log_2(N)-3$ ever fails for a positive integer $N$. A counterexample would invalidate the entropy accounting; a proof of the stronger $T(N)\ge \log_2(N)-2$ would tighten the algorithm's constant.

Watch

Extended reading notes

Core claim

At the center of the paper is the observation that a non-dyadic uniform draw still carries randomness that can be saved instead of thrown away. MichelangeRoll draws a uniform integer from $[0,2^{j+k})$, locates it in one of $n$ subintervals of lengths $Mp_i$ plus a rejection interval, and emits the interval index whenever it is a genuine $D$-outcome. The pair $(N_t,S_t)$—the interval length and the offset inside it—is pushed into the asymmetric numeral system through $A_t := A_{t-1}N_t + S_t$, so residual uniform numbers aggregate into one large uniform integer; at resets, a halving procedure converts $A_t$ into fair coin tosses, with Lemma 6 bounding the loss by fewer than three bits per reset. Since the rejection rate is below $\varepsilon^2$ and the ANS is reset every $O(1/\varepsilon)$ samples, the total loss is $O(\varepsilon)$ per sample, which proves Theorem 1's $H(D)+\varepsilon$ entropy guarantee under the stated memory and time bounds.

Load-bearing premise

The paper's entropy guarantee rests on the claim that the bit-extraction procedure recovers at least $\log_2(N)-3$ tosses in expectation from a uniform integer in $\{0,\ldots,N-1\}$; if the true loss per reset were larger than three bits, the per-sample entropy bound would not follow.

Editorial extensions

If this is right

For every rational distribution $D$, an ongoing sample stream can be generated with $H(D)+\varepsilon$ fair coin tosses per sample, so the old '+2' overhead disappears without batching exponentially many samples.
The memory bound $O((n+1/\varepsilon)\log(m/\varepsilon))$ avoids the $n^{1/\varepsilon}$ and $m^{1/\varepsilon}$ blow-up that batch-amortization would require.
Distributions with small entropy, such as Bernoulli(1/100), benefit most because the former fixed overhead was large relative to $H(D)$.
The algorithm can be run indefinitely with a bounded buffer, since the coin-toss buffer is emptied before each reset rather than merely with high probability.

Reading between the lines

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

Beyond the paper: the same recycle-the-residual pattern should extend to other entropy sources, such as non-dyadic dice or biased coins; the paper lists this as future work, and nothing in the aggregation lemma depends on the source being fair.
Beyond the paper: a public proof of the sharper two-bit extraction bound would improve the additive constant in the entropy guarantee; the paper currently relies on a private communication for that sharper estimate.
Beyond the paper: an implementation for small $m$ could reveal whether the theoretical entropy saving survives practice, since the quoted $O(\log(m/\varepsilon)^2/\varepsilon)$ operation count is dominated by schoolbook integer multiplication.

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, and a circularity audit.

Desk Editor's Note

read the letter

Read the paper. The headline result is genuine: MichelangeRoll generates an ongoing sequence of D-samples using H(D)+epsilon fair tosses per sample, with polynomial space and time in the description size. The mechanism, using an asymmetric numeral system to recycle leftover uniformity from accepted subintervals, is new, and the entropy accounting is careful. Lemmas 4 and 5 establish independence and uniformity of recycled bits; Lemma 6's induction is sound, and the weaker log2(N)-3 bound is all Theorem 1 needs. I agree with the stress test: no load-bearing flaw.

What's actually new is the specific construction, the space/time tradeoff, and the observation that ANS lets you aggregate non-dyadic uniform leftovers without paying the 'forgetting the level' cost twice. The paper is also honest about concurrent work [DS25a], which reaches the same H(D)+epsilon target with a different, arguably more dexterous method. That does reduce the novelty from 'first to break +2' to 'another way to break +2 with a distinct complexity profile,' and the authors say so themselves.

Soft spots, all minor. The constants in the O(epsilon) entropy loss are not explicit; the '3 bits' per reset is an upper bound, and the amortization argument is sketched rather than formalized. The appendix proof of Conjecture 8 leans on a private communication and a reference to Knuth-Yao; the main theorem doesn't need it, but a self-contained proof of the sharper claim would be cleaner. The time bound O(log(m/epsilon)^2/epsilon) is higher than previous work, but that is the price for breaking +2 and is still quasi-linear in the gap. None of this threatens the central claim.

This paper is for people working in exact random generation, entropy extraction, and randomness recycling. It deserves a serious referee. The writing is clear, the citations are appropriate, and the result is a clean step forward. I would send it to review.

Referee Report

0 major / 7 minor

Summary. This paper presents MichelangeRoll, an algorithm for generating an ongoing sequence of exact samples from a rational discrete distribution D=(p_1,...,p_n) with common denominator m, using fair coin tosses. The main result (Theorem 1) states that for any small constant ε>0, the expected number of fresh coin tosses per D-sample is H(D)+ε, with O((n+1/ε) log(m/ε)) memory and O(log(m/ε)^2/ε) operations per sample. The construction generates a uniform integer U_t in [0,2^{j+k}) and partitions the range into n outcome intervals and one rejection interval. When U_t falls into the i-th interval, the algorithm outputs i; the offset S_t inside the interval is fed into an asymmetric numeral system (ANS) that aggregates these uniform remainders into a large integer A_t. At reset, A_t is converted back into fair coin tosses, which are reused as randomness for future samples. The proof bounds two sources of entropy loss: the rejection indicator, contributing O(ε^2 log(1/ε)) per sample, and the ANS reset, contributing at most 3 bits per reset, which amortizes to O(ε). The exactness and independence of the recycled bits are established in Lemmas 4-5, and Lemma 6 proves that the expected number of tosses extracted from a uniform integer in [0,N) exceeds log2(N)-3.

Significance. If correct, the theorem is a significant advance in exact random variate generation: it breaks the Knuth-Yao '+2' barrier for exact sampling without the exponential space blow-up of batching, matching Shannon entropy up to an arbitrarily small additive ε. The proof is self-contained for the main theorem; importantly, the sharper Conjecture 8 is not used, so the H(D)+ε claim rests only on Lemmas 4-7, whose induction and mean-value-theorem estimates are explicit and verifiable. The paper also gives a clear comparison with prior work (Knuth-Yao, Han-Hoshi, rejection sampling, Draper-Saad), and the acknowledgment of concurrent work is honest. The cost is higher time complexity, but the paper is upfront about this trade-off.

minor comments (7)

[Section 4.3] The text says 'we lost 3 bits every time the ANS is reset' and 'it resets once every 1/ε samples'; the first should be 'at most 3 bits' (since Lemma 6 is an upper bound) and the second should be 'at most once every 1/ε samples', because the proof only shows the product N_1...N_t grows by a factor less than 2^{j+k} per iteration, so resets cannot occur more frequently than once per 1/ε samples.
[Abstract and Theorem 1] The phrase 'per samples' should be 'per sample' in both the abstract and the theorem statement.
[Section 4.5 and Table 1] The expression 'O(log(m/ε)2/ε)' is ambiguous and should be typeset as O(log^2(m/ε)/ε) to avoid confusion with multiplication by 2.
[Appendix A] The symbol ν is not defined, and the proof sketch relies on [Eli72, (14)] and [KY76, (2.19)] without the necessary context; since Conjecture 8 is not required for Theorem 1, this is a presentation issue, but the appendix as written is not self-checkable.
[Section 3.3, proof of Lemma 6] In the odd case of the induction, the intermediate line '= N + 3/N log2(N − 1) − 3K + 1/N' appears garbled; it should be '= ((N+3)/N) log2(N−1) − 3 − 1/N' with the erroneous 'K' removed.
[Section 4.4, footnote] The footnote says the buffer bound is 'an almost always bound'; this should be 'a deterministic (worst-case) bound', since the argument is not probabilistic.
[Section 2.1] There is a typo: 'deviates away form Shannon's prediction' should be 'deviates away from Shannon's prediction'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified.

full rationale

The derivation of Theorem 1 is self-contained and does not reduce to its inputs by construction. The central entropy-saving claim rests on Lemma 6, whose proof is an induction with a mean-value-theorem bound supplied by Lemma 7, not on a fitted parameter or an assumed conclusion. The entropy accounting in Section 4.3 separately bounds rejection loss and per-reset loss, then amortizes the constant per-reset loss over an ANS block of length about 1/epsilon; none of these steps presuppose the H(D)+epsilon result. The recycled-bit independence and fairness are established by Lemmas 4 and 5. External results cited, including Knuth-Yao, are classical and used for context or for the non-load-bearing Appendix A confirmation of Conjecture 8; that conjecture is explicitly not needed for Theorem 1. There are no self-citations by the authors, no fitted input renamed as a prediction, and no uniqueness theorem imported from prior work by the same authors. The paper compares against external benchmarks such as Knuth-Yao's H(D)+2 and Draper-Saad's recent work, and the claimed improvement is proved rather than assumed.

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

The central claim rests on the paper's own lemmas (proved in Sections 3 and 4) and on standard information-theoretic facts. No free parameters are fitted to data. No new entities are introduced.

assumptions (3)

domain assumption D is a rational distribution with a known common denominator m.
The construction uses m to define the dyadic grid and the denominator of the interval lengths.
standard math Uniform random integers can be converted into fair independent bits by the parity-extraction procedure.
Proved as Lemmas 4 and 5; relies on standard properties of uniform integers.
standard math Knuth-Yao's bound on the function ν(N), cited as [KY76, Theorem 2.2], used in Appendix A to prove the sharper entropy extraction bound.
External citation; only needed for Conjecture 8, not for the main theorem.

how reviews work

0 comments

Cite this review

Pith. "Pith review of MichelangeRoll: Sculpting Rational Distributions Exactly and Efficiently." pith.science (2026). https://pith.science/paper/E6RMSDUW

@misc{pith2026250700915,
  author       = {Pith},
  title        = {Pith review of: MichelangeRoll: Sculpting Rational Distributions Exactly and Efficiently},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E6RMSDUW}},
  note         = {Machine review of arXiv:2507.00915}
}

abstract

Simulating an arbitrary discrete distribution $D \in [0, 1]^n$ using fair coin tosses incurs trade-offs between entropy complexity and space and time complexity. Shannon's theory suggests that $H(D)$ tosses are necessary and sufficient, but does not guarantee exact distribution. Knuth and Yao showed that a decision tree consumes fewer than $H(D) + 2$ tosses for one exact sample. Draper and Saad's recent work addresses the space and time aspect, showing that $H(D) + 2$ tosses, $O(n \log(n) \log(m))$ memory, and $O(H(D))$ operations are all it costs, where $m$ is the common denominator of the probability masses in $D$ and $n$ is the number of possible outcomes. In this paper, MichelangeRoll recycles leftover entropy to break the "$+2$" barrier. With $O((n + 1/\varepsilon) \log(m/\varepsilon))$ memory, the entropy cost of generating a ongoing sequence of $D$ is reduced to $H(D) + \varepsilon$ per sample.

Figures

Figures reproduced from arXiv: 2507.00915 by the authors.

**Figure 2.** Left: A tree repeats itself. Right: The repeating part is simplified by a “goto” arrow. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Han and Hoshi’s construction with D := (1/3, 1/3, 1/3) as a running example. The unit interval [0, 1] is partitioned into 3 subintervals of length 1/3, represented by the three colored strips. The process of revealing the fuzzy random number is represented by rectangles with progressively halving heights. A rectangle is accepted if it is monochromatic. Accepted rectangles will not be divided further. 2.4 Acceptance–… view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: The goal is to generate D := (3/5, 2/5). Left: Follow Knuth–Yao’s recipe and wait patiently for repetition. Right: Generate D¨ := (3/8, 2/8, 3/8) and reject the third outcome. are slightly smaller than 2k+3 and 2k+4, respectively. If we use 15m or 31m as the denominato…

**Figure 5.** Figure 5: A visualization of ANS: Two uniform distributions are combined into one before being [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]

**Figure 6.** Figure 6: An overview of the MichelangeRoll. Proof. Multiply both sides by N and cancel 3N to reduce the goal to (N + 3) log2 (N − 1) ? ⩾ (N + 2) log2 (N) + 1. Apply mean value theorem to log2 over [N − 1, N] to reduce the goal to (N + 3) log2 (N) − log2 (e) N − 1 ? ⩾ (N + 2)…

**Figure 7.** Figure 7: Our classification of earlier works based on the type of entropy source and the type of [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Space-Entropy Lower Bounds for Random Sampling
cs.CC 2026-07 conditional novelty 8.0 of 10

Exact entropy-efficient random sampling with per-sample entropy loss ε requires Ω(log(1/ε)) bits of persistent space, with sharp constants for Bernoulli(1/3) and almost all k-outcome distributions.
Online Random Sampling with Real Probabilities
cs.DS 2026-07 conditional novelty 7.0 of 10

An online sampler converts fair coin flips into exact samples from arbitrary computable distributions with entropy loss O(log n) and O(log n) persistent space, matching lower bounds up to constants.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · cited by 2 Pith papers

[1]

Abrahams

J. Abrahams. Generation of discrete distributions from biased coins. IEEE Transactions on Information Theory , 42(5):1541--1546, September 1996

work page 1996
[2]

M. Blum. Independent unbiased coin flips from a correlated biased source: A finite state markov chain. In 25th Annual Symposium onFoundations of Computer Science, 1984. , pages 425--433, October 1984

work page 1984
[3]

Draper and Feras A

Thomas L. Draper and Feras A. Saad. Efficient Online Random Sampling via Randomness Recycling , July 2025

work page 2025
[4]

Draper and Feras A

Thomas L. Draper and Feras A. Saad. Efficient Rejection Sampling in the Entropy-Optimal Range , April 2025

work page 2025
[5]

Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, January 2014

Jarek Duda. Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, January 2014

work page 2014
[6]

The efficient construction of an unbiased random sequence

Peter Elias. The efficient construction of an unbiased random sequence. The Annals of Mathematical Statistics , 43(3):865--870, 1972

work page 1972
[7]

On the order of a (mod p)

P \'a l Erd \"o s and M Ram Murty. On the order of a (mod p). In CRM Proceedings and Lecture Notes , volume 19, pages 87--97, 1999

work page 1999
[8]

T. S. Han and M. Hoshi. Interval algorithm for random number generation. IEEE Transactions on Information Theory , 43(2):599--611, March 1997

work page 1997

Show all 17 references

[9]

Optimal rolling of fair dice using fair coins, December 2024

Mark Huber and Danny Vargas. Optimal rolling of fair dice using fair coins, December 2024

2024
[10]

Optimal Coin Flipping

Dexter Kozen. Optimal Coin Flipping . In Franck Van Breugel, Elham Kashefi, Catuscia Palamidessi, and Jan Rutten, editors, Horizons of the Mind . A Tribute to Prakash Panangaden , volume 8464, pages 407--426. Springer International Publishing, Cham, 2014

2014
[11]

Knuth and A

D. Knuth and A. Yao. Algorithms and Complexity: New Directions and Recent Results , chapter The complexity of nonuniform random number generation. Academic Press, 1976

1976
[12]

Optimal Discrete Uniform Generation from Coin Flips , and Applications , April 2013

J \'e r \'e mie Lumbroso. Optimal Discrete Uniform Generation from Coin Flips , and Applications , April 2013

2013
[13]

Iterating Von Neumann 's Procedure for Extracting Random Bits

Yuval Peres. Iterating Von Neumann 's Procedure for Extracting Random Bits . The Annals of Statistics , 20(1), March 1992

1992
[14]

Sung-il Pae and Michael C. Loui. Optimal random number generation from a biased coin. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms , Soda '05, pages 1079--1088, Vancouver, British Columbia and USA, 2005. Society for Industrial and Applied Ma...

2005
[15]

J.R. Roche. Efficient Generation Of Random Variables From Biased Coins . In Proceedings. 1991 IEEE International Symposium on Information Theory , pages 169--169, Budapest, Hungary, 1991. IEEE

1991
[16]

Saad, Cameron E

Feras A. Saad, Cameron E. Freer, Martin C. Rinard, and Vikash K. Mansinghka. The Fast Loaded Dice Roller : A Near-Optimal Exact Sampler for Discrete Probability Distributions , June 2020

2020
[17]

Various techniques used in connection with random digits

John Von Neumann et al. Various techniques used in connection with random digits. John von Neumann, Collected Works , 5:768--770, 1963

1963

Pith tools

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

[1] [1]

Abrahams

J. Abrahams. Generation of discrete distributions from biased coins. IEEE Transactions on Information Theory , 42(5):1541--1546, September 1996

work page 1996

[2] [2]

M. Blum. Independent unbiased coin flips from a correlated biased source: A finite state markov chain. In 25th Annual Symposium onFoundations of Computer Science, 1984. , pages 425--433, October 1984

work page 1984

[3] [3]

Draper and Feras A

Thomas L. Draper and Feras A. Saad. Efficient Online Random Sampling via Randomness Recycling , July 2025

work page 2025

[4] [4]

Draper and Feras A

Thomas L. Draper and Feras A. Saad. Efficient Rejection Sampling in the Entropy-Optimal Range , April 2025

work page 2025

[5] [5]

Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, January 2014

Jarek Duda. Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, January 2014

work page 2014

[6] [6]

The efficient construction of an unbiased random sequence

Peter Elias. The efficient construction of an unbiased random sequence. The Annals of Mathematical Statistics , 43(3):865--870, 1972

work page 1972

[7] [7]

On the order of a (mod p)

P \'a l Erd \"o s and M Ram Murty. On the order of a (mod p). In CRM Proceedings and Lecture Notes , volume 19, pages 87--97, 1999

work page 1999

[8] [8]

T. S. Han and M. Hoshi. Interval algorithm for random number generation. IEEE Transactions on Information Theory , 43(2):599--611, March 1997

work page 1997