Pith. sign in

REVIEW 4 major objections 4 minor 50 references

Assessing the Quality of Binomial Samplers: A Statistical Distance Framework

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

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

Pith's one-line read Standard Binomial samplers now have a proven statistical-distance bound that makes their quality auditable in randomized algorithms.

desk verdict Useful framework, unproven main theorem: Lemma 3's false conditional uniformity assumption invalidates the constants in Theorem 1. read the letter →

arxiv 2506.12061 v1 pith:WMVHFEER submitted 2025-05-31 stat.CO cs.LO

Uddalok Sarkar , Sourav Chakraborty , Kuldeep S. Meel This is my paper
classification stat.COcs.LO MSC 65C1065G50
keywords BinomialsamplerstatisticaldistancetotalvariationtransformedrejectionsamplingroundingerrorrandomizedalgorithmsDNFcountingLanczosapproximation
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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

4 major / 4 minor

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.

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 (4)
  1. [Appendix A, proof of Lemma 3] 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.
  2. [§5.3, "Error in Inverse Transform Sampling" (p. 15)] 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.
  3. [Lemma 4 (p. 12) and its proof in Appendix A] 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.
  4. [§5.3, proof of Theorem 1] 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.
minor comments (4)
  1. [References] 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.
  2. [Algorithm 2, line 11] 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.
  3. [Theorem 1 and §5.3] 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.
  4. [§5.1 / Theorem 1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's statistical-distance bounds are not derived by fitting the target or by load-bearing self-citation.

full rationale

The derivation chain is not circular. Theorem 1 combines two independent error analyses: Lemma 3 bounds the deviation of the hat distribution from arithmetic error in H^{-1}(u), and Lemmas 4-6 bound the rejection-ratio error using standard floating-point, logarithm, and Lanczos approximation bounds cited from the numerical-analysis literature. No parameter is fitted to the target TV distance, and Lemma 2 is a standard folklore composition lemma proved from the definition of statistical distance. The uniformity assumption in Lemma 3 is an explicit modeling assumption, acknowledged in the Limitations section ('The current analysis relies on several simplifying assumptions—for instance, uniformity in the error distribution'), so it is a correctness/validity concern, not a circular reduction. The definition of er_k in Lemma 4 as b^BinSamp_{n,p}(k)/(αh(k)) is notationally suspicious, and the proof of Lemma 5 in Appendix A actually bounds the algorithm's computed ratio e^{elrk} rather than that defined quantity; this is a proof gap or inconsistency, not a case where the theorem's conclusion is assumed as its premise. Self-citations appear in the related work on sampler testing and in the APSEst case study, but none is load-bearing for the main statistical-distance theorem: the theorem stands on the cited error bounds for arithmetic, AGM logarithm, and Lanczos approximation, which are external numerical-analysis results. For these reasons, no circular step can be exhibited.

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

The central bound rests on three external numerical error bounds (correctly rounded arithmetic, Lanczos, AGM) plus two ad hoc statistical assumptions about the error in the inverse transform. Constants c, zeta, and alpha are not instantiated. No new physical entities are introduced.

free parameters (3)
  • c
    Appears in Theorem 1 and Lemma 3 as the constant bounding error in evaluating H^{-1}(u); the paper says typically c <= 100, but no concrete value is fixed for Python's Hormann implementation, so the numeric bound is not instantiated.
  • zeta
    Uniform Lanczos factorial error bound from Pugh; depends on t and g used by the implementation, which are not specified for Python's sampler, leaving the bound's final value uncomputed.
  • alpha
    Rejection rate of the hat distribution; algorithm-specific and not numerically specified in the theorem, though it is part of the stated bound.
assumptions (7)
  • standard math Basic floating-point operations in F are correctly rounded with relative error epsilon = 2^{-beta} (eq. 2)
    Used in Lemma 5 to bound arithmetic error in the rejection ratio.
  • standard math Lanczos approximation satisfies relative error bound zeta from Pugh (eq. 1)
    Used in Lemma 6 and Lemma 7 to bound factorial approximation error.
  • standard math AGM log approximation has additive error tau = 178*beta/2^beta (eq. 4)
    Used in the Lemma 5 proof to bound log errors.
  • domain assumption The output k' of inverse transform is limited to {k-1, k, k+1} under the stated beta condition
    Used in Lemma 3; relies on epsilon_H * H^{-1}(u) <= 1, which needs the beta threshold.
  • ad hoc to paper Numerical error in H^{-1}(u) is uniformly distributed over [-epsilon_H, epsilon_H]
    Section 5.3 and Lemma 3; not derived from floating-point arithmetic, and the theorem statement does not condition on it.
  • ad hoc to paper Conditional distribution of H^{-1}(U) given floor value t is uniform on [t, t+1)
    Appendix proof of Lemma 3; false in general because the conditional density is proportional to the hat density h(y).
  • domain assumption Symmetry or parameter range ensures |log p| < beta and |log(1-p)| < beta
    Used in the Appendix Lemma 5 proof; the stated beta condition does not bound |log(1-p)| for p near 1 unless an unstated symmetry is used.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Assessing the Quality of Binomial Samplers: A Statistical Distance Framework." pith.science (2026). https://pith.science/paper/WMVHFEER

@misc{pith2026250612061,
  author       = {Pith},
  title        = {Pith review of: Assessing the Quality of Binomial Samplers: A Statistical Distance Framework},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WMVHFEER}},
  note         = {Machine review of arXiv:2506.12061}
}
read the original abstract

Randomized algorithms depend on accurate sampling from probability distributions, as their correctness and performance hinge on the quality of the generated samples. However, even for common distributions like Binomial, exact sampling is computationally challenging, leading standard library implementations to rely on heuristics. These heuristics, while efficient, suffer from approximation and system representation errors, causing deviations from the ideal distribution. Although seemingly minor, such deviations can accumulate in downstream applications requiring large-scale sampling, potentially undermining algorithmic guarantees. In this work, we propose statistical distance as a robust metric for analyzing the quality of Binomial samplers, quantifying deviations from the ideal distribution. We derive rigorous bounds on the statistical distance for standard implementations and demonstrate the practical utility of our framework by enhancing APSEst, a DNF model counter, with improved reliability and error guarantees. To support practical adoption, we propose an interface extension that allows users to control and monitor statistical distance via explicit input/output parameters. Our findings emphasize the critical need for thorough and systematic error analysis in sampler design. As the first work to focus exclusively on Binomial samplers, our approach lays the groundwork for extending rigorous analysis to other common distributions, opening avenues for more robust and reliable randomized algorithms.

Figures

Figures reproduced from arXiv: 2506.12061 by the authors.

Figure 1
Figure 1. Early (left) and new (right) sampler interfaces. The new version includes [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Accuracy experiment results for APSEst2. The red line represents the tolerance factor (ε = 0.8). which are commonly used in both model counting competitions and practical applications. Finally, we set κ to 0.5. Summary of Results Our observations reveal that APSEst2 delivers counts that are nearly as precise as the exact counts obtained from Ganak, as demonstrated in fig. 2. The y-axis of fig. 2 represents the relat… view at source ↗
Figure 3
Figure 3. Left: Reported errors (δ ′ ) by APSEst2 for individual instances. Right: Average error grouped by the number of clauses in the DNF formula, showing a clear upward trend as formula size increases. usage of statistical distance as the quality metric owing to its ability to allow end users to obtain sound bounds on the bad events. We also presented a case study demonstrating the minimal effort required by system design… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

50 extracted references · 50 canonical work pages

  1. [1]

    Cambridge University Press (2009)

    Arora, S., Barak, B.: Computational complexity: a modern approach. Cambridge University Press (2009)

    work page 2009

  2. [2]

    In: AISTATS (2023)

    Banerjee, A., Chakraborty, S., Chakraborty, S., Meel, K.S., Sarkar, U., Sen, S.: Testing of horn samplers. In: AISTATS (2023)

    work page 2023

  3. [3]

    In: AAAI (2024)

    Bhattacharyya, R., Chakraborty, S., Pote, Y., Sarkar, U., Sen, S.: Testing self- reducible samplers. In: AAAI (2024)

    work page 2024

  4. [4]

    Binder, K., Heermann, D.W., Binder, K.: Monte Carlo simulation in statistical physics, vol. 8. Springer (1992)

    work page 1992

  5. [5]

    IMA Journal of Numerical Analysis 41(4), 2311–2330 (2021)

    Blanchard, P., Higham, D.J., Higham, N.J.: Accurately computing the log-sum- exp and softmax functions. IMA Journal of Numerical Analysis 41(4), 2311–2330 (2021)

    work page 2021

  6. [6]

    Commu- nications of the ACM 13(7), 422–426 (1970)

    Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commu- nications of the ACM 13(7), 422–426 (1970)

    work page 1970

  7. [7]

    Bonnot, P., Boyer, B., Faissole, F., March´ e, C., Rieu-Helft, R.: Formally veri- fied bounds on rounding errors in concrete implementations of logarithm-sum- exponential functions. Tech. rep. (2023)

    work page 2023

  8. [8]

    In: FMCAD

    Bonnot, P., Boyer, B., Faissole, F., March´ e, C., Rieu-Helft, R.: Formally verified rounding errors of the logarithm sum exponential function. In: FMCAD. pp. 251–

    work page

Show all 50 references
  1. [9]

    SIAM review 26(3), 351–366 (1984)

    Borwein, J.M., Borwein, P.B.: The arithmetic-geometric mean and fast computa- tion of elementary functions. SIAM review 26(3), 351–366 (1984)

    1984

  2. [10]

    Mathematics of Computation 76(259), 1469–1481 (2007)

    Brent, R., Percival, C., Zimmermann, P.: Error bounds on complex floating-point multiplication. Mathematics of Computation 76(259), 1469–1481 (2007)

    2007

  3. [11]

    In: STOC (1977)

    Carter, J.L., Wegman, M.N.: Universal classes of hash functions. In: STOC (1977)

    1977

  4. [12]

    In: AAAI (2019)

    Chakraborty, S., Meel, K.S.: On testing of uniform samplers. In: AAAI (2019)

    2019

  5. [13]

    In: IJCAI

    Chakraborty, S., Meel, K.S., Vardi, M.Y.: Algorithmic improvements in approxi- mate counting for probabilistic inference: From linear to logarithmic sat calls. In: IJCAI. pp. 3569–3576 (2016)

    2016

  6. [14]

    Computers & Mathematics with Applications 6(3), 305–315 (1980)

    Devroye, L.: Generating the maximum of independent identically distributed ran- dom variables. Computers & Mathematics with Applications 6(3), 305–315 (1980)

    1980

  7. [15]

    Handbooks in operations re- search and management science 13, 83–121 (2006)

    Devroye, L.: Nonuniform random sample generation. Handbooks in operations re- search and management science 13, 83–121 (2006)

    2006

  8. [16]

    Algorithmica 73, 637–651 (2015)

    Farach-Colton, M., Tsai, M.T.: Exact sublinear binomial sampling. Algorithmica 73, 637–651 (2015)

    2015

  9. [17]

    ACM Trans- actions on Mathematical Software (TOMS) 33(2), 13–es (2007)

    Fousse, L., Hanrot, G., Lef` evre, V., P´ elissier, P., Zimmermann, P.: Mpfr: A multiple-precision binary floating-point library with correct rounding. ACM Trans- actions on Mathematical Software (TOMS) 33(2), 13–es (2007)

    2007

  10. [18]

    Network Theory Limited Godalming (2002)

    Galassi, M., Davies, J., Theiler, J., Gough, B., Jungman, G., Alken, P., Booth, M., Rossi, F., Ulerich, R.: GNU scientific library. Network Theory Limited Godalming (2002)

    2002

  11. [19]

    Nature 585, 357–362 (2020)

    Harris, C.R., Millman, K.J., van der Walt, S.J., Gommers, R., Virtanen, P., Cour- napeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N.J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M.H., Brett, M., Haldane, A., del R ´ ıo, J.F., Wiebe, M., Peterson, P., G´ erard-Marchant...

    2020

  12. [20]

    Communications of the ACM 4(7), 321 (1961) 21

    Hoare, C.A.R.: Algorithm 64: quicksort. Communications of the ACM 4(7), 321 (1961) 21

    1961

  13. [21]

    Acm Sigact News 32(1), 60–65 (2001)

    Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to automata theory, lan- guages, and computation. Acm Sigact News 32(1), 60–65 (2001)

    2001

  14. [22]

    Journal of statistical computation and simulation 46(1-2), 101–110 (1993)

    H¨ ormann, W.: The generation of binomial random samples. Journal of statistical computation and simulation 46(1-2), 101–110 (1993)

    1993

  15. [23]

    Automatic Nonuniform Random Variate Generation pp

    H¨ ormann, W., Leydold, J., Derflinger, G., H¨ ormann, W., Leydold, J., Derflinger, G.: Transformed density rejection (tdr). Automatic Nonuniform Random Variate Generation pp. 55–111 (2004)

    2004

  16. [24]

    Mathematics of Computation 86(304), 881–898 (2017)

    Jeannerod, C.P., Kornerup, P., Louvet, N., Muller, J.M.: Error bounds on complex floating-point multiplication with an fma. Mathematics of Computation 86(304), 881–898 (2017)

    2017

  17. [25]

    SIAM Journal on Matrix Analysis and Applications 34(2), 338– 344 (2013)

    Jeannerod, C.P., Rump, S.M.: Improved error bounds for inner products in floating- point arithmetic. SIAM Journal on Matrix Analysis and Applications 34(2), 338– 344 (2013)

    2013

  18. [26]

    Mathematics of computation 87(310), 803–819 (2018)

    Jeannerod, C.P., Rump, S.M.: On relative errors of floating-point operations: op- timal bounds and applications. Mathematics of computation 87(310), 803–819 (2018)

    2018

  19. [27]

    Communications of the ACM 31(2), 216–222 (1988)

    Kachitvichyanukul, V., Schmeiser, B.W.: Binomial random sample generation. Communications of the ACM 31(2), 216–222 (1988)

    1988

  20. [28]

    ACM Transactions on Mathematical Software (TOMS) 42(1), 1–14 (2016)

    Karney, C.F.: Sampling exactly from the normal distribution. ACM Transactions on Mathematical Software (TOMS) 42(1), 1–14 (2016)

    2016

  21. [29]

    In: FOCS (1983)

    Karp, R.M., Luby, M.: Monte-carlo algorithms for enumeration and reliability prob- lems. In: FOCS (1983)

    1983

  22. [30]

    Journal of algorithms 10(3), 429–448 (1989)

    Karp, R.M., Luby, M., Madras, N.: Monte-carlo approximation algorithms for enu- meration problems. Journal of algorithms 10(3), 429–448 (1989)

    1989

  23. [31]

    Kumar, G., Meel, K.S., Pote, Y.: Tolerant testing of high-dimensional samplers with subcube conditioning (2023)

    2023

  24. [32]

    Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis1(1), 86–96 (1964)

    Lanczos, C.: A precision approximation of the gamma function. Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis1(1), 86–96 (1964)

    1964

  25. [33]

    Automata and Languages: Theory and Applications pp

    Meduna, A., Meduna, A.: Turing transducers. Automata and Languages: Theory and Applications pp. 833–887 (2000)

    2000

  26. [34]

    NeurIPS (2020)

    Meel, K.S., Pote, Y.P., Chakraborty, S.: On testing of samplers. NeurIPS (2020)

    2020

  27. [35]

    Constraints 24, 211–233 (2019)

    Meel, K.S., Shrotri, A.A., Vardi, M.Y.: Not all fprass are equal: demystifying fprass for dnf-counting. Constraints 24, 211–233 (2019)

    2019

  28. [36]

    Meel rG, K.S., Vinodchandran rG, N., Chakraborty, S.: Estimating size of the union of sets in streaming model (2021)

    2021

  29. [37]

    Springer (2006)

    Muller, J.M., Muller, J.M.: Elementary functions. Springer (2006)

    2006

  30. [38]

    Communications in Statistics-Simulation and Computation 23(3), 847–860 (1994)

    ormann, W., erflinger, G.: The transformed rejection method for generating ran- dom variables, an alternative to the ratio of uniforms method. Communications in Statistics-Simulation and Computation 23(3), 847–860 (1994)

    1994

  31. [39]

    NeurIPS (2022)

    Pote, Y., Meel, K.S.: On scalable testing of samplers. NeurIPS (2022)

    2022

  32. [40]

    NeurIPS (2021)

    Pote, Y.P., Meel, K.S.: Testing probabilistic circuits. NeurIPS (2021)

    2021

  33. [41]

    Pugh, G.R.: An analysis of the Lanczos gamma approximation. Ph.D. thesis, Uni- versity of British Columbia (2004)

    2004

  34. [42]

    Citeseer (1990)

    Pugh, W.: Concurrent maintenance of skip lists. Citeseer (1990)

    1990

  35. [43]

    SIAM Journal on Scientific Computing 31(1), 189–224 (2008)

    Rump, S.M., Ogita, T., Oishi, S.: Accurate floating-point summation part i: Faith- ful rounding. SIAM Journal on Scientific Computing 31(1), 189–224 (2008)

    2008

  36. [44]

    Research memorandum pp

    Schmeiser, B., Kachitvichyanukul, V.: Poisson random sample generation. Research memorandum pp. 81–4 (1981)

    1981

  37. [45]

    In: IJCAI

    Sharma, S., Roy, S., Soos, M., Meel, K.S.: Ganak: A scalable probabilistic exact model counter. In: IJCAI. vol. 19, pp. 1169–1176 (2019) 22

    2019

  38. [46]

    In: IJCAI

    Soos, M., Aggarwal, D., Chakraborty, S., Meel, K.S., Obremski, M.: Engineering an efficient approximate dnf-counter. In: IJCAI. pp. 2031–2038 (2023)

    2023

  39. [47]

    In: Proceedings of the AAAI Conference on Artificial Intelligence

    Soos, M., Meel, K.S.: Bird: engineering an efficient cnf-xor sat solver and its appli- cations to approximate model counting. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 33, pp. 1592–1599 (2019)

    2019

  40. [48]

    org/algorithms.pdf/

    The MPFR Team: The mpfr library: Algorithms and proofs, https://www.mpfr. org/algorithms.pdf/

  41. [49]

    Springer Science & Business Media (2012) 23 Appendix A Extended Proofs Proof of Lemma 5 To prove Lemma 5, we begin by analyzing how log n! is approximated

    Thomopoulos, N.T.: Essentials of Monte Carlo simulation: Statistical methods for building simulation models. Springer Science & Business Media (2012) 23 Appendix A Extended Proofs Proof of Lemma 5 To prove Lemma 5, we begin by analyzing how log n! is approximated. In this cont...

    2012

  42. [260]

    TU Wien Academic Press (2024)

    2024

Pith tools

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