{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:34:06Z","timestamp":1757619246091,"version":"3.44.0"},"publisher-location":"Cham","reference-count":49,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031986789"},{"type":"electronic","value":"9783031986796"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T00:00:00Z","timestamp":1753142400000},"content-version":"vor","delay-in-days":202,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>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.<\/jats:p>","DOI":"10.1007\/978-3-031-98679-6_11","type":"book-chapter","created":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T09:20:52Z","timestamp":1753089652000},"page":"231-253","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Assessing the Quality of Binomial Samplers: A Statistical Distance Framework"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-4997-1084","authenticated-orcid":false,"given":"Uddalok","family":"Sarkar","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9518-6204","authenticated-orcid":false,"given":"Sourav","family":"Chakraborty","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9423-5270","authenticated-orcid":false,"given":"Kuldeep S.","family":"Meel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,22]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"11_CR2","unstructured":"Banerjee, A., Chakraborty, S., Chakraborty, S., Meel, K.S., Sarkar, U., Sen, S.: Testing of horn samplers. In: AISTATS (2023)"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, R., Chakraborty, S., Pote, Y., Sarkar, U., Sen, S.: Testing self-reducible samplers. In: AAAI (2024)","DOI":"10.1609\/aaai.v38i8.28632"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Binder, K., Heermann, D.W., Binder, K.: Monte Carlo Simulation in Statistical Physics, vol.\u00a08. Springer, Heidelberg (1992)","DOI":"10.1007\/978-3-662-30273-6"},{"issue":"4","key":"11_CR5","doi-asserted-by":"publisher","first-page":"2311","DOI":"10.1093\/imanum\/draa038","volume":"41","author":"P Blanchard","year":"2021","unstructured":"Blanchard, P., Higham, D.J., Higham, N.J.: Accurately computing the log-sum-exp and softmax functions. IMA J. Numer. Anal. 41(4), 2311\u20132330 (2021)","journal-title":"IMA J. Numer. Anal."},{"issue":"7","key":"11_CR6","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422\u2013426 (1970)","journal-title":"Commun. ACM"},{"key":"11_CR7","unstructured":"Bonnot, P., Boyer, B., Faissole, F., March\u00e9, C., Rieu-Helft, R.: Formally verified bounds on rounding errors in concrete implementations of logarithm-sum-exponential functions. Technical report, Inria (2023)"},{"key":"11_CR8","unstructured":"Bonnot, P., Boyer, B., Faissole, F., March\u00e9, C., Rieu-Helft, R.: Formally verified rounding errors of the logarithm sum exponential function. In: FMCAD, pp. 251\u2013260. TU Wien Academic Press (2024)"},{"issue":"3","key":"11_CR9","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1137\/1026073","volume":"26","author":"JM Borwein","year":"1984","unstructured":"Borwein, J.M., Borwein, P.B.: The arithmetic-geometric mean and fast computation of elementary functions. SIAM Rev. 26(3), 351\u2013366 (1984)","journal-title":"SIAM Rev."},{"issue":"259","key":"11_CR10","doi-asserted-by":"publisher","first-page":"1469","DOI":"10.1090\/S0025-5718-07-01931-X","volume":"76","author":"R Brent","year":"2007","unstructured":"Brent, R., Percival, C., Zimmermann, P.: Error bounds on complex floating-point multiplication. Math. Comput. 76(259), 1469\u20131481 (2007)","journal-title":"Math. Comput."},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Carter, J.L., Wegman, M.N.: Universal classes of hash functions. In: STOC (1977)","DOI":"10.1145\/800105.803400"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Meel, K.S.: On testing of uniform samplers. In: AAAI (2019)","DOI":"10.1609\/aaai.v33i01.33017777"},{"key":"11_CR13","unstructured":"Chakraborty, S., Meel, K.S., Vardi, M.Y.: Algorithmic improvements in approximate counting for probabilistic inference: from linear to logarithmic sat calls. In: IJCAI, pp. 3569\u20133576 (2016)"},{"issue":"3","key":"11_CR14","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0898-1221(80)90039-5","volume":"6","author":"L Devroye","year":"1980","unstructured":"Devroye, L.: Generating the maximum of independent identically distributed random variables. Comput. Math. Appl. 6(3), 305\u2013315 (1980)","journal-title":"Comput. Math. Appl."},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0927-0507(06)13004-2","volume":"13","author":"L Devroye","year":"2006","unstructured":"Devroye, L.: Nonuniform random sample generation. Handbooks Oper. Res. Manag. Sci. 13, 83\u2013121 (2006)","journal-title":"Handbooks Oper. Res. Manag. Sci."},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/s00453-015-0077-8","volume":"73","author":"M Farach-Colton","year":"2015","unstructured":"Farach-Colton, M., Tsai, M.T.: Exact sublinear binomial sampling. Algorithmica 73, 637\u2013651 (2015)","journal-title":"Algorithmica"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Fousse, L., Hanrot, G., Lef\u00e8vre, V., P\u00e9lissier, P., Zimmermann, P.: Mpfr: A multiple-precision binary floating-point library with correct rounding. ACM Trans. Math. Softw. (TOMS) 33(2), 13\u2013es (2007)","DOI":"10.1145\/1236463.1236468"},{"key":"11_CR18","unstructured":"Galassi, M., et al.: GNU scientific library. Network Theory Limited Godalming (2002)"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/s41586-020-2649-2","volume":"585","author":"CR Harris","year":"2020","unstructured":"Harris, C.R., et al.: Array programming with NumPy. Nature 585, 357\u2013362 (2020)","journal-title":"Nature"},{"issue":"7","key":"11_CR20","first-page":"321","volume":"4","author":"C Hoare","year":"1961","unstructured":"Hoare, C.: Algorithm 64: quicksort. Commun. ACM 4(7), 321 (1961)","journal-title":"Commun. ACM"},{"issue":"1","key":"11_CR21","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/568438.568455","volume":"32","author":"JE Hopcroft","year":"2001","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to automata theory, languages, and computation. ACM SIGACT News 32(1), 60\u201365 (2001)","journal-title":"ACM SIGACT News"},{"issue":"1\u20132","key":"11_CR22","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1080\/00949659308811496","volume":"46","author":"W H\u00f6rmann","year":"1993","unstructured":"H\u00f6rmann, W.: The generation of binomial random samples. J. Stat. Comput. Simul. 46(1\u20132), 101\u2013110 (1993)","journal-title":"J. Stat. Comput. Simul."},{"issue":"3","key":"11_CR23","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1080\/03610919408813203","volume":"23","author":"W H\u00f6rmann","year":"1994","unstructured":"H\u00f6rmann, W., Derflinger, G.: The transformed rejection method for generating random variables, an alternative to the ratio of uniforms method. Commun. Stat.-Simul. Comput. 23(3), 847\u2013860 (1994)","journal-title":"Commun. Stat.-Simul. Comput."},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"H\u00f6rmann, W., Leydold, J., Derflinger, G., H\u00f6rmann, W., Leydold, J., Derflinger, G.: Transformed density rejection (tdr). In: Automatic Nonuniform Random Variate Generation, pp. 55\u2013111 (2004)","DOI":"10.1007\/978-3-662-05946-3_4"},{"issue":"304","key":"11_CR25","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1090\/mcom\/3123","volume":"86","author":"CP Jeannerod","year":"2017","unstructured":"Jeannerod, C.P., Kornerup, P., Louvet, N., Muller, J.M.: Error bounds on complex floating-point multiplication with an fma. Math. Comput. 86(304), 881\u2013898 (2017)","journal-title":"Math. Comput."},{"issue":"2","key":"11_CR26","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/120894488","volume":"34","author":"CP Jeannerod","year":"2013","unstructured":"Jeannerod, C.P., Rump, S.M.: Improved error bounds for inner products in floating-point arithmetic. SIAM J. Matrix Anal. Appl. 34(2), 338\u2013344 (2013)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"310","key":"11_CR27","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1090\/mcom\/3234","volume":"87","author":"CP Jeannerod","year":"2018","unstructured":"Jeannerod, C.P., Rump, S.M.: On relative errors of floating-point operations: optimal bounds and applications. Math. Comput. 87(310), 803\u2013819 (2018)","journal-title":"Math. Comput."},{"issue":"2","key":"11_CR28","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1145\/42372.42381","volume":"31","author":"V Kachitvichyanukul","year":"1988","unstructured":"Kachitvichyanukul, V., Schmeiser, B.W.: Binomial random sample generation. Commun. ACM 31(2), 216\u2013222 (1988)","journal-title":"Commun. ACM"},{"issue":"1","key":"11_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2710016","volume":"42","author":"CF Karney","year":"2016","unstructured":"Karney, C.F.: Sampling exactly from the normal distribution. ACM Trans. Math. Softw. (TOMS) 42(1), 1\u201314 (2016)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Luby, M.: Monte-carlo algorithms for enumeration and reliability problems. In: FOCS (1983)","DOI":"10.1109\/SFCS.1983.35"},{"issue":"3","key":"11_CR31","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"RM Karp","year":"1989","unstructured":"Karp, R.M., Luby, M., Madras, N.: Monte-carlo approximation algorithms for enumeration problems. J. Algor. 10(3), 429\u2013448 (1989)","journal-title":"J. Algor."},{"key":"11_CR32","unstructured":"Kumar, G., Meel, K.S., Pote, Y.: Tolerant testing of high-dimensional samplers with subcube conditioning. In: AISTATS (2025)"},{"issue":"1","key":"11_CR33","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/0701008","volume":"1","author":"C Lanczos","year":"1964","unstructured":"Lanczos, C.: A precision approximation of the gamma function. J. Soc. Ind. Appl. Math. Series B: Numer. Anal. 1(1), 86\u201396 (1964)","journal-title":"J. Soc. Ind. Appl. Math. Series B: Numer. Anal."},{"key":"11_CR34","doi-asserted-by":"crossref","unstructured":"Meduna, A., Meduna, A.: Turing transducers. In: Automata and Languages: Theory and Applications, pp. 833\u2013887 (2000)","DOI":"10.1007\/978-1-4471-0501-5_11"},{"key":"11_CR35","unstructured":"Meel, K.S., Pote, Y.P., Chakraborty, S.: On testing of samplers. In: NeurIPS (2020)"},{"key":"11_CR36","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s10601-018-9301-x","volume":"24","author":"KS Meel","year":"2019","unstructured":"Meel, K.S., Shrotri, A.A., Vardi, M.Y.: Not all fprass are equal: demystifying fprass for dnf-counting. Constraints 24, 211\u2013233 (2019)","journal-title":"Constraints"},{"key":"11_CR37","doi-asserted-by":"crossref","unstructured":"Meel, K.S., Vinodchandran, N., Chakraborty, S.: Estimating the size of union of sets in streaming models. In: PODS, pp. 126\u2013137 (2021)","DOI":"10.1145\/3452021.3458333"},{"key":"11_CR38","unstructured":"Muller, J.M., Muller, J.M.: Elementary Functions. Springer, Heidelberg (2006)"},{"key":"11_CR39","unstructured":"Pote, Y., Meel, K.S.: On scalable testing of samplers. In: NeurIPS (2022)"},{"key":"11_CR40","unstructured":"Pote, Y.P., Meel, K.S.: Testing probabilistic circuits. In: NeurIPS (2021)"},{"key":"11_CR41","unstructured":"Pugh, G.R.: An analysis of the Lanczos gamma approximation. Ph.D. thesis, University of British Columbia (2004)"},{"key":"11_CR42","unstructured":"Pugh, W.: Concurrent maintenance of skip lists. Citeseer (1990)"},{"issue":"1","key":"11_CR43","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1137\/050645671","volume":"31","author":"SM Rump","year":"2008","unstructured":"Rump, S.M., Ogita, T., Oishi, S.: Accurate floating-point summation part i: faithful rounding. SIAM J. Sci. Comput. 31(1), 189\u2013224 (2008)","journal-title":"SIAM J. Sci. Comput."},{"key":"11_CR44","unstructured":"Schmeiser, B., Kachitvichyanukul, V.: Poisson random sample generation. In: Research Memorandum, pp. 81\u20134 (1981)"},{"key":"11_CR45","doi-asserted-by":"crossref","unstructured":"Sharma, S., Roy, S., Soos, M., Meel, K.S.: Ganak: a scalable probabilistic exact model counter. In: IJCAI, vol.\u00a019, pp. 1169\u20131176 (2019)","DOI":"10.24963\/ijcai.2019\/163"},{"key":"11_CR46","doi-asserted-by":"crossref","unstructured":"Soos, M., Aggarwal, D., Chakraborty, S., Meel, K.S., Obremski, M.: Engineering an efficient approximate dnf-counter. In: IJCAI, pp. 2031\u20132038 (2023)","DOI":"10.24963\/ijcai.2023\/226"},{"key":"11_CR47","doi-asserted-by":"crossref","unstructured":"Soos, M., Meel, K.S.: Bird: engineering an efficient cnf-xor sat solver and its applications to approximate model counting. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol.\u00a033, pp. 1592\u20131599 (2019)","DOI":"10.1609\/aaai.v33i01.33011592"},{"key":"11_CR48","unstructured":"The MPFR Team: The mpfr library: Algorithms and proofs. https:\/\/www.mpfr.org\/algorithms.pdf\/"},{"key":"11_CR49","doi-asserted-by":"crossref","unstructured":"Thomopoulos, N.T.: Essentials of Monte Carlo simulation: Statistical Methods for Building Simulation Models. Springer, Heidelberg (2012)","DOI":"10.1007\/978-1-4614-6022-0"}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-98679-6_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,7]],"date-time":"2025-09-07T16:18:00Z","timestamp":1757261880000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-98679-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031986789","9783031986796"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-98679-6_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 July 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"CAV","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computer Aided Verification","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Zagreb","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Croatia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 July 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cav2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conferences.i-cav.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}