{"id":"1ae7f806-0d51-4090-8677-b738f7a16dc8","arxiv_id":"2507.00915","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"MichelangeRoll recycles leftover randomness with asymmetric numeral systems to sample any rational distribution exactly at H(D)+ε entropy per sample.","lead":"This paper presents a new algorithm, MichelangeRoll, that samples any rational discrete distribution exactly using H(D)+ε fair coin tosses per sample on average, improving on the previous H(D)+2 bound. It shows that the '+2' overhead is not fundamental and gives explicit space and time costs, so exact sampling can be nearly as efficient as approximate methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's verdict ACCEPT is well supported. The weakest assumption identified by the reader, Lemma 6, is indeed the most delicate step in the entropy accounting, but the proof given in the paper is complete and correct. I checked the induction in Lemma 6, including the even case (requiring N ≥ 4), the odd base cases (N = 2, 3, 5, 7), and the reduction of the odd case to Lemma 7 via the mean value theorem; the algebra checks out. The subsequent entropy accounting in Section 4.3 correctly identifies the two loss sources (rejection entropy and ANS reset loss) and shows both are O(ε). The independence of the recycled tosses from the output samples and the N's follows from Lemma 4 (uniformity of the ANS state) and Lemma 5 (the extraction procedure produces fair bits independent of the modulus), and the renewal structure justifies the amortization of the 3-bit loss over blocks of length at least 1/ε. The space and time bounds are also consistent with the algorithm's state sizes and operations. The only externally confirmed claim, Conjecture 8, is not used in the proof of Theorem 1, so the private-communication reliance does not affect the main result. No circular reasoning, missing proof, or internal inconsistency was found. Therefore the original ACCEPT verdict remains unchanged.","tokens_in":10872,"tokens_out":47985,"duration_ms":501978,"concrete_test":"Independently verify Lemma 6 by computing T(N) from recurrences (5)-(6) for all N up to 10^6 and confirming T(N) > log2(N) - 3; optionally, simulate MichelangeRoll for a small rational distribution (e.g., Bernoulli(1/3)) over 10^6 samples with ε = 0.01 and compare the measured average fresh tosses per sample against H(D) + ε.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After reviewing the full argument, I find no load-bearing flaw. The central claim hinges on Lemma 6, whose induction proof is correct: the even and odd recurrence steps, together with Lemma 7's mean-value-theorem bound, establish T(N) > log2(N) - 3 for all N. The entropy accounting in Section 4.3 is sound: the recycled bits are independent of the I's and N's by Lemmas 4 and 5, the rejection loss is O(ε^2 log(1/ε)), and the per-reset loss of at most 3 bits in expectation amortizes to O(ε) because the ANS block length is at least 1/ε. The space and time bounds follow from the stated integer sizes. The sharper Conjecture 8, supported only by a private communication, is not needed for Theorem 1. Thus no significant objection is identified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10991,"tokens_out":21452,"duration_ms":230913,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 4.3"},{"comment":"The phrase 'per samples' should be 'per sample' in both the abstract and the theorem statement.","section":"Abstract and Theorem 1"},{"comment":"The expression 'O(log(m/ε)2/ε)' is ambiguous and should be typeset as O(log^2(m/ε)/ε) to avoid confusion with multiplication by 2.","section":"Section 4.5 and Table 1"},{"comment":"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":"Appendix A"},{"comment":"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":"Section 3.3, proof of Lemma 6"},{"comment":"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":"Section 4.4, footnote"},{"comment":"There is a typo: 'deviates away form Shannon's prediction' should be 'deviates away from Shannon's prediction'.","section":"Section 2.1"}],"recommendation":"minor_revision","confidential_remarks":"The main theorem is sound; I recommend publication after minor revisions. The appendix's use of a private communication from Draper to confirm Conjecture 8 is not ideal for a public record, but since the conjecture is explicitly not needed for Theorem 1, it does not affect the paper's contribution. I would encourage the authors to either provide a fully self-contained derivation of Conjecture 8 or mark it more clearly as an optional, non-verified strengthening. The overlap with concurrent work [DS25a] is acknowledged and contextualized in Table 1; the contributions are distinct enough (different time-space trade-offs) for this venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nSoft 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.\n\nThis 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.","headline":"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.","tokens_in":11518,"tokens_out":1537,"would_cite":true,"duration_ms":17179,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q87","94A17","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"MichelangeRoll samples any rational distribution exactly with H(D)+ε fair coin tosses per sample and polynomial memory.","keywords":["exact random number generation","entropy-optimal sampling","asymmetric numeral systems","rational distributions","Knuth-Yao decision trees","randomness recycling","discrete distribution simulation","Shannon entropy"],"falsifier":"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.","tokens_in":10676,"feed_emoji":"🎲","tokens_out":9092,"duration_ms":97163,"temperature":0.7,"pith_summary":"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.","feed_headline":"Sampling any distribution now needs only entropy plus ε","feed_subtitle":"A recycling scheme recovers wasted coin tosses, beating the old '+2' overhead without blowing up memory.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the optimal decision-tree construction and the H(D)+2 baseline that MichelangeRoll improves, and Appendix A uses its Theorem 2.2 for the bit-extraction bound.","marker":"[KY76]"},{"why":"Gives the previous state of the art with H(D)+2 tosses and O(n log n log m) memory that this paper surpasses on entropy.","marker":"[DS25b]"},{"why":"Introduces the asymmetric numeral system that MichelangeRoll adapts to recycle residual uniform integers.","marker":"[Dud14]"},{"why":"Provides the dyadized-distribution rejection construction and subinterval lookup scheme the algorithm builds on.","marker":"[SFRM20]"},{"why":"Used in the paper's own remark and appendix to justify the expected-bit bound that the entropy accounting relies on.","marker":"[Eli72]"}],"fun_headline_variants":["Recycled coin tosses beat sampling's +2 overhead","Entropy recycling: sample any distribution at H+ε cost","MichelangeRoll: exact sampling with entropy plus epsilon","Sampling distributions: only ε over entropy, not +2","Waste-free sampling: from H+2 to H+ε entropy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Recycled coin tosses beat sampling's +2 overhead","Entropy recycling: sample any distribution at H+ε cost","MichelangeRoll: exact sampling with entropy plus epsilon","Sampling distributions: only ε over entropy, not +2","Waste-free sampling: from H+2 to H+ε entropy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000638,"raw_usage":{"total_tokens":2957,"prompt_tokens":981,"completion_tokens":1976,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":597,"completion_tokens_details":{"reasoning_tokens":1890}},"tokens_in":597,"tokens_out":1976,"duration_ms":14883,"temperature":1.0,"reasoning_tokens":1890,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:05:00.536699+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}