{"id":"ab45bd58-5f1a-400a-b4ec-6613bf4c06ed","arxiv_id":"2506.12061","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A theorem bounds the total variation distance between the ideal Binomial distribution and the distribution produced by standard library samplers, and the bound is integrated into a DNF counter.","lead":"This paper proposes using statistical distance to measure how far standard Binomial random number samplers drift from the ideal distribution, and derives explicit error bounds for the Python-style transformed rejection sampler. It then shows how to fold those bounds into a DNF model counting algorithm so users know the worst-case error introduced by the sampler.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's proof relies on a false conditional uniformity assumption, so the constants in Theorem 1 are unsupported.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: Lemma 3's conditional uniformity claim is false in general, and the proof's integrals depend on it. My independent reading confirms this. The paper's Theorem 1 is the central claim; Lemma 3 supplies the epsilon_H terms in the bound, and Lemma 4 supplies the epsilon and zeta terms. While Lemma 4's proof also has points worth scrutiny (e.g., the treatment of log(h^{-1}(u)) and the ex bounds), the false conditional density in Lemma 3 is the clearest fatal flaw. The theorem may be salvageable with a corrected analysis, but as written the constants are unsupported. Since my conclusion matches the reader's REJECT verdict, no verdict adjustment is needed. I did not find grounds for additional objections beyond the reader's; the case study is a demonstration, not the core claim, and the paper does provide an artifact and the framework may be useful. Thus the verdict should remain REJECT (unchanged).","tokens_in":21098,"tokens_out":2023,"duration_ms":20529,"concrete_test":"Recompute the two integrals in the proof of Lemma 3 (Appendix A) using the correct conditional density h(v)/(H(t+1)-H(t)) instead of the uniform density 1. Specifically, evaluate Pr(k' = t+1 | floor(H^{-1}(U)) = t) = integral from (t+1)/(1+eps_H) to t+1 of (1/2) * h(v)/(H(t+1)-H(t)) dv, and similarly for the lower bound. If these corrected integrals yield bounds exceeding eps_H(t+1)/3 or below 1 - eps_H(3k+1) for a concrete hat distribution (e.g., Hörmann's), then Lemma 3 fails and Theorem 1's constants are invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 1's bound on dTV(bn,p, b^BinSamp_n,p), and that bound inherits its constants from Lemma 3. The proof of Lemma 3 (Appendix A) contains two unjustified steps. First, it assumes the error in computing H^{-1}(u) is uniformly distributed over [-epsilon_H, epsilon_H]; this is a statistical model for floating-point error, not a consequence of the arithmetic error bounds in Section 2.2, and a worst-case bound would require taking a supremum over error distributions, not positing a convenient one. Second, and more seriously, the proof assumes that, conditional on floor(H^{-1}(U)) = t, the value H^{-1}(U) is uniform on [t, t+1). For inverse-transform sampling with U uniform on [0,1], X = H^{-1}(U) has density h, so the conditional density is h(v)/(H(t+1)-H(t)), not 1. The integrals computing Pr(k' = t+1 | floor = t) and the analogous lower-bound integral replace this density with 1, so the derived bounds (eps_H(t+1)/3 and 1 - eps_H(3k+1)) do not follow. Because Lemma 3 directly feeds the epsilon_H terms of Theorem 1, the theorem's stated constants are not established. The paper's own Limitations section acknowledges the uniformity assumption, but the false conditional uniformity is not a stated limitation; it is an error in the proof. Since Theorem 1 is the central deliverable, the main claim is currently unproven.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes statistical distance (total variation distance) as a quality metric for Binomial samplers and derives a bound on the distance between the ideal Binomial distribution bn,p and the distribution b^BinSamp_n,p produced by a standard transformed-rejection-sampling implementation (Algorithm 1). Theorem 1 states dTV(bn,p, b^BinSamp_n,p) ≤ (1110β + 3cp + c + αc)nε + 15ζ + o(ε), where ε is the unit roundoff, ζ is the Lanczos approximation error, α is the rejection rate, and c is a constant depending on the hat distribution. The proof splits the error into inverse-transform error E1 (Lemma 3) and rejection-ratio error E2 (Lemmas 4–6). The framework is then applied to APSEst, a DNF model counter, by adding a statistical-distance error budget and an explicit δ_in/δ_out interface, with experiments showing accurate counts on standard benchmarks.","tokens_in":21470,"tokens_out":8195,"duration_ms":80627,"significance":"If Theorem 1 were correct, the paper would deliver a practically useful and theoretically clean way to make sampler quality auditable: Lemma 2 shows that any downstream randomized algorithm's error can be bounded by the sampler's TV distance, and the APSEst2 case study demonstrates a low-overhead integration. The paper does not fit constants to its conclusions; it composes error bounds from the numerical-analysis literature, and the constants c, ζ, α are defined by the hat distribution and the algorithm rather than tuned to the target theorem. The proposed interface extension and the empirical accuracy study are valuable regardless of the theorem. However, the central theoretical deliverable is not established: the proof of Lemma 3 relies on a false conditional-uniformity assumption, and the uniform-error modeling assumption is not derived from the floating-point error bounds. Because the main theorem is the basis for the claimed rigorous guarantees, the contribution in its current form is not sound.","major_comments":[{"comment":"The proof assumes that, conditional on ⌊H^{-1}(u)⌋ = t, the value H^{-1}(u) is uniformly distributed on [t, t+1), and it sets the conditional density f(H^{-1}(u)=v | floor=t) to 1 in the integrals. This is not true for inverse-transform sampling: X = H^{-1}(U) has density h(x), so the conditional density given floor(X)=t is h(v)/(H(t+1)-H(t)), not 1. Consequently the bounds Pr(k'=t+1 | floor=t) ≤ εH(t+1)/3 and Pr(k'=k | floor=k) ≥ 1 - εH(3k+1) do not follow from the stated calculations. Since Lemma 3 directly supplies the εH terms in Theorem 1, the constants (1110β + 3cp + c + αc)nε are not established. This is not one of the admitted limitations in §7; it is an incorrect step in the proof.","section":"Appendix A, proof of Lemma 3"},{"comment":"The proof of Lemma 3 introduces a statistical model by stating, \"we assume it to be uniformly distributed over the range [-εH, εH]\" for the error in computing H^{-1}(u). This is not a consequence of the deterministic floating-point error bounds in §2.2, which only give an interval guarantee for the computed value. A rigorous worst-case TV bound requires either a supremum over all error distributions consistent with that interval, or a fully deterministic accounting of the error. The Limitations section acknowledges \"uniformity in the error distribution\" as a simplifying assumption, but then the abstract and Theorem 1 overclaim by calling the result a rigorous bound; at best the theorem is conditional on an unverified stochastic model of floating-point error.","section":"§5.3, \"Error in Inverse Transform Sampling\" (p. 15)"},{"comment":"The statement |erk/rk - 1| ≤ (1110n + 2540)βε + 14ε log(h(k)) + 15ζ + o(ε) is problematic because h(k) ≤ 1 and hence log(h(k)) ≤ 0; the right-hand side can be negative while the left-hand side is nonnegative. The proof itself derives upper and lower one-sided bounds involving 14ε log(h^{-1}(u)) = -14ε log h(k), and the combined absolute error should contain |log h(k)| (or an equivalent positive term). This is not cosmetic: the proof of Theorem 1 later uses these signed terms to simplify sums, so the missing absolute value can artificially shrink the bound.","section":"Lemma 4 (p. 12) and its proof in Appendix A"},{"comment":"The final algebra in the proof of Theorem 1 appears to drop a term of order ε. From (3np+1)εH + αεH(n+2), with εH = cε, one obtains 3cp nε + cε + αc nε + 2αc ε, but the displayed final expression (1110β + 3cp + c + αc)nε + 15ζ + o(ε) omits the 2αc ε term, which is O(ε) and cannot be absorbed into o(ε) without comment. In addition, the lower-bound expression \"14αε + log(h^{-1}(u))\" appears to be missing a factor and a summation. These issues, together with the sign issue in Lemma 4, mean the constants in the theorem need to be rechecked carefully.","section":"§5.3, proof of Theorem 1"}],"minor_comments":[{"comment":"Several references have corrupted author names or formatting, for example [36] lists \"Meel rG\" and [38] lists \"ormann, W., erflinger, G.\" instead of Hörman and Derflinger.","section":"References"},{"comment":"The notation δ′ ← δ′ + δi|sol(φi)|,p is unclear; it should presumably be δ_i^{n_i,p_i} with the sampler parameters made explicit, as used in the surrounding text.","section":"Algorithm 2, line 11"},{"comment":"The constant c in Theorem 1 is only described as \"a constant determined by the inverse function pair (H,h)\"; the paper gives no explicit method to compute it, and the remark \"c ≤ 100\" is informal. Without an explicit bound, the numerical usefulness of the theorem in the case study is limited.","section":"Theorem 1 and §5.3"},{"comment":"The condition in the theorem is β ≥ max(2⌈log2 n⌉, ⌈−log2 p⌉), while the proof text says β > 2 log2⌈n⌉; the relationship between these conditions, especially for n that is not a power of two, should be clarified.","section":"§5.1 / Theorem 1"}],"recommendation":"reject","confidential_remarks":"The paper is not circular: the derivation composes independent numerical-analysis bounds and does not fit constants to the target conclusion. The problem is a genuine proof error in the central theorem, not a question of calibration. The APSEst2 modification and the experimental study are well described and useful. However, since Theorem 1 is the core contribution and its proof contains a false conditional-uniformity assumption plus a non-rigorous uniform-error model, the main claim is currently unproven; I do not see how a routine revision can fix this without substantially reworking the analysis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi [name],\n\nQuick take: the paper has a good idea and a nice integration story, but its main theorem isn't proven as written. The flaw is in Lemma 3, and it's load-bearing.\n\nWhat's genuinely new: framing sampler quality as a TV-distance budget that downstream algorithms can consume is clean and practical. The composition of existing floating-point and AGM log error bounds into a single bound for standard Binomial samplers is a real contribution; I don't know of another place that does that. The APSEst2 case study is also a good proof of concept—it shows how to plug the bound into a DNF counter and keep the error accounting explicit, with experiments that reproduce the accuracy of the original algorithm.\n\nWhat's wrong: Lemma 3's proof in Appendix A assumes that, conditional on floor(H^{-1}(u)) = t, the value H^{-1}(u) is uniform on [t, t+1). Under inverse-transform sampling, the conditional density is h(v)/(H(t+1)-H(t)), not 1. The integrals that lead to the ε_H bounds (for example ε_H(t+1)/3) replace that density with 1, so those bounds don't follow. This is not a cosmetic issue: Lemma 3 supplies the ε_H terms in Theorem 1, so the theorem's constants are unsupported. The paper does state in its Limitations that it assumes uniformity of the error distribution, which is honest as far as it goes, but the conditional uniformity step is a separate, incorrect claim and isn't flagged as a limitation.\n\nEverything else—the E1/E2 decomposition, the arithmetic error chaining, the empirical section—looks fine to me. The problem is concentrated in one proof step, but that step is essential.\n\nWho this is for: people building or using randomized algorithms that rely on Binomial samplers, and anyone interested in practical guarantees for library sampling routines. A reader who cares about the framework and the integration recipe will get value; a reader who needs a rigorous bound will not, yet.\n\nRecommendation: send it to review, but expect the referee to catch this. The paper deserves a serious referee and a major revision; the framework and case study are worth preserving, and the proof may be repairable with a worst-case error argument rather than the uniform assumption.\n\nBest","headline":"Useful framework, unproven main theorem: Lemma 3's false conditional uniformity assumption invalidates the constants in Theorem 1.","tokens_in":21922,"tokens_out":2348,"would_cite":false,"duration_ms":22363,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C10","65G50"],"pacs":[],"model":"deepseek-v4-flash","headline":"Standard Binomial samplers now have a proven statistical-distance bound that makes their quality auditable in randomized algorithms.","keywords":["Binomial sampler","statistical distance","total variation distance","transformed rejection sampling","rounding error","randomized algorithms","DNF counting","Lanczos approximation"],"falsifier":"Compare the conditional distribution of $H^{-1}(U)$ given $\\lfloor H^{-1}(U) \\rfloor = t$ against uniformity for Hörmann's hat with concrete $n, p$ and small $\\varepsilon$; any measurable deviation shows Lemma 3's premise fails, so Theorem 1's constant is not justified for that sampler. Alternatively, empirically estimate $d_{\\mathrm{TV}}$ between Python's BinSamp output and $b_{n,p}$ for $n=100$ and $n=1000$ with $p=0.5$ by exhaustive enumeration and check whether it respects the bound.","tokens_in":20930,"feed_emoji":"🎲","tokens_out":4595,"duration_ms":40152,"temperature":0.7,"pith_summary":"This paper argues that the quality of a Binomial sampler should be reported as its statistical distance from the ideal Binomial distribution, and it proves the first explicit bound on that distance for standard library implementations based on transformed rejection sampling. The bound is concrete: for precision $\\beta$ and Lanczos error $\\zeta$, $d_{\\mathrm{TV}}(b_{n,p}, \\hat{b}^{\\mathrm{BinSamp}}_{n,p}) \\le (1110\\beta + 3cp + c + \\alpha c)n\\varepsilon + 15\\zeta + o(\\varepsilon)$. Because statistical distance controls the worst-case change in probability of any event in any downstream randomized algorithm, the bound converts an opaque implementation detail into an auditable error budget. The paper demonstrates the workflow on a DNF model counter, APSEst, and proposes an interface extension so users can set and monitor the allowed distance.","feed_headline":"A proven error bound for standard binomial samplers","feed_subtitle":"Statistical distance turns sampler quality into a number that downstream algorithms can budget for.","key_machinery":"The central device is the statistical distance (total variation distance) between the ideal distribution $b_{n,p}$ and the sampler's output distribution $\\hat{b}^{\\mathrm{BinSamp}}_{n,p}$, together with the bounding lemmas that feed Theorem 1: Lemma 3 bounds the distortion of the hat distribution caused by rounding in $H^{-1}(u)$, and Lemma 4 bounds the relative error of the computed rejection ratio from Lanczos factorial approximation, arithmetic-geometric-mean logarithm, and floating-point operations. Lemma 2, the indistinguishability property, is what turns a distance bound into a transferable error guarantee for any downstream randomized algorithm.","core_discovery":"On its own terms, the paper establishes that standard Binomial samplers, such as the Hörmann transformed-rejection algorithm used in Python and NumPy, sample from a distribution whose deviation from the true Binomial distribution is bounded by Theorem 1. The proof decomposes the deviation into two sources: errors in the inverse-transform step that corrupt the hat distribution, and errors in the computed rejection ratio due to factorial approximation, logarithm approximation, and floating-point rounding. Combined with the folklore lemma that replacing one randomness source by another changes any event probability by at most the statistical distance between the sources, this gives a rigorous recipe for randomized algorithms to absorb sampler error: add the sampler's distance to the failure budget, or abort when the budget is exceeded. The paper demonstrates the recipe by modifying APSEst into a version with explicit error guarantees, and it reports empirical errors around $10^{-6}$ on DNF benchmarks.","pith_inferences":["The proof of Lemma 3 rests on the assumption that $H^{-1}(U)$ is uniform on $[t, t+1)$ given its floor is $t$; for Hörmann's hat distribution the conditional density is proportional to the hat density, so the bound in Theorem 1 may not hold as stated for the very sampler the paper analyzes.","Because the bound grows linearly with $n$, the guarantee weakens for large Binomial parameters; a testable extension would measure empirical TV distance for large $n$ with $p$ near $1/2$ and compare it to the bound.","The $\\delta_{\\mathrm{in}}/\\delta_{\\mathrm{out}}$ interface could be standardized across sampling libraries, letting algorithm designers treat sampler error like any other resource with a budget."],"forward_implications":["Every downstream randomized algorithm can have its failure probability increased by at most the sampler's statistical distance, so bounds like Theorem 1 give an end-to-end error budget.","Users can request a target quality $\\delta_{\\mathrm{in}}$ and receive a reported $\\delta_{\\mathrm{out}}$, making sampling accuracy a controllable parameter rather than a hidden implementation detail.","The APSEst case study shows the bounds are tight enough in practice to keep DNF counts within tolerance while reporting sampler errors around $10^{-6}$.","The same decomposition, inverse-transform error plus rejection-ratio error, applies to other transformed-rejection samplers such as Poisson, Normal, and Beta, opening a route to similar guarantees.","Exact sampling algorithms remain the benchmark; the framework does not replace them but makes approximate samplers auditable."],"supporting_citations":[{"why":"Defines the Hörmann transformed-rejection algorithm that the paper analyzes as the standard Binomial sampler.","marker":"[22]"},{"why":"Provides the Lanczos factorial approximation used in the sampler's probability mass computation.","marker":"[32]"},{"why":"Supplies the uniform error bound for the Lanczos approximation that enters the rejection-ratio bound as $\\zeta$.","marker":"[41]"},{"why":"Gives the arithmetic-geometric-mean logarithm algorithm and its error bound, used for $\\log$ and $\\log(1-p)$.","marker":"[9]"},{"why":"Provides the floating-point operation and summation error bounds that quantify the basic arithmetic error term $\\varepsilon$.","marker":"[26]"},{"why":"Defines correct rounding for basic operations, justifying the relative error bounds for $+,-,\\times,/,\\sqrt{}$.","marker":"[17]"},{"why":"Describes the multiple-precision arithmetic and ulp definitions underlying the precision parameter $\\beta$ and the unit round-off $\\varepsilon$.","marker":"[48]"},{"why":"Supplies the APSEst DNF counting algorithm that the paper modifies to demonstrate the practical utility of the bounds.","marker":"[36]"}],"fun_headline_variants":["Statistical distance bounds binomial sampler error","Binomial sampler quality, made measurable","Error bounds for standard binomial samplers","Quantifying sampler deviations: a statistical distance approach"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of Lemma 3 assumes the rounding error in computing $H^{-1}(u)$ is uniformly distributed and that, conditional on the floor of $H^{-1}(U)$ being $t$, the value is uniform on $[t, t+1)$; the second assumption is false for the hat distributions used in practice, and the first is an unverified model of floating-point error.","fun_headline_variants_meta":{"raw":{"variants":["Statistical distance bounds binomial sampler error","Binomial sampler quality, made measurable","Error bounds for standard binomial samplers","Quantifying sampler deviations: a statistical distance approach"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000293,"raw_usage":{"total_tokens":1699,"prompt_tokens":929,"completion_tokens":770,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":545,"completion_tokens_details":{"reasoning_tokens":718}},"tokens_in":545,"tokens_out":770,"duration_ms":7807,"temperature":1.0,"reasoning_tokens":718,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:01:02.805449+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compare the conditional distribution of $H^{-1}(U)$ given $\\lfloor H^{-1}(U) \\rfloor = t$ against uniformity for Hörmann's hat with concrete $n, p$ and small $\\varepsilon$; any measurable deviation shows Lemma 3's premise fails, so Theorem 1's constant is not justified for that sampler. Alternatively, empirically estimate $d_{\\mathrm{TV}}$ between Python's BinSamp output and $b_{n,p}$ for $n=100$ and $n=1000$ with $p=0.5$ by exhaustive enumeration and check whether it respects the bound.","supporting_citations":[{"cited_title":"Journal of statistical computation and simulation 46(1-2), 101–110 (1993)","cited_arxiv_id":null,"evidence_quote":"Defines the Hörmann transformed-rejection algorithm that the paper analyzes as the standard Binomial sampler."},{"cited_title":"Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis1(1), 86–96 (1964)","cited_arxiv_id":null,"evidence_quote":"Provides the Lanczos factorial approximation used in the sampler's probability mass computation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the uniform error bound for the Lanczos approximation that enters the rejection-ratio bound as $\\zeta$."},{"cited_title":"SIAM review 26(3), 351–366 (1984)","cited_arxiv_id":null,"evidence_quote":"Gives the arithmetic-geometric-mean logarithm algorithm and its error bound, used for $\\log$ and $\\log(1-p)$."},{"cited_title":"Mathematics of computation 87(310), 803–819 (2018)","cited_arxiv_id":null,"evidence_quote":"Provides the floating-point operation and summation error bounds that quantify the basic arithmetic error term $\\varepsilon$."},{"cited_title":"ACM Trans- actions on Mathematical Software (TOMS) 33(2), 13–es (2007)","cited_arxiv_id":null,"evidence_quote":"Defines correct rounding for basic operations, justifying the relative error bounds for $+,-,\\times,/,\\sqrt{}$."},{"cited_title":"org/algorithms.pdf/","cited_arxiv_id":null,"evidence_quote":"Describes the multiple-precision arithmetic and ulp definitions underlying the precision parameter $\\beta$ and the unit round-off $\\varepsilon$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the APSEst DNF counting algorithm that the paper modifies to demonstrate the practical utility of the bounds."}],"review_version":1}