{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T14:49:15Z","timestamp":1776955755178,"version":"3.51.4"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T00:00:00Z","timestamp":1576800000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>\n            This paper addresses a fundamental problem in random variate generation: given access to a random source that emits a stream of independent fair bits, what is the most accurate and entropy-efficient algorithm for sampling from a discrete probability distribution (\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026,\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            ), where the probabilities of the output distribution (\n            <jats:italic>p\u0302<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026,\n            <jats:italic>p\u0302<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            ) of the sampling algorithm must be specified using at most\n            <jats:italic>k<\/jats:italic>\n            bits of precision? We present a theoretical framework for formulating this problem and provide new techniques for finding sampling algorithms that are optimal both statistically (in the sense of sampling accuracy) and information-theoretically (in the sense of entropy consumption). We leverage these results to build a system that, for a broad family of measures of statistical accuracy, delivers a sampling algorithm whose expected entropy usage is minimal among those that induce the same distribution (i.e., is \u201centropy-optimal\u201d) and whose output distribution (\n            <jats:italic>p\u0302<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026,\n            <jats:italic>p\u0302<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            ) is a closest approximation to the target distribution (\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026,\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            ) among all entropy-optimal sampling algorithms that operate within the specified\n            <jats:italic>k<\/jats:italic>\n            -bit precision. This optimal approximate sampler is also a closer approximation than any (possibly entropy-suboptimal) sampler that consumes a bounded amount of entropy with the specified precision, a class which includes floating-point implementations of inversion sampling and related methods found in many software libraries. We evaluate the accuracy, entropy consumption, precision requirements, and wall-clock runtime of our optimal approximate sampling algorithms on a broad set of distributions, demonstrating the ways that they are superior to existing approximate samplers and establishing that they often consume significantly fewer resources than are needed by exact samplers.\n          <\/jats:p>","DOI":"10.1145\/3371104","type":"journal-article","created":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T19:45:25Z","timestamp":1576871125000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimal approximate sampling from discrete probability distributions"],"prefix":"10.1145","volume":"4","author":[{"given":"Feras A.","family":"Saad","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cameron E.","family":"Freer","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin C.","family":"Rinard","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vikash K.","family":"Mansinghka","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,12,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.532895"},{"key":"e_1_2_2_2_1","first-page":"1","article-title":"A General Class of Coefficients of Divergence of One Distribution from Another","volume":"28","author":"Ali S. M.","year":"1966","unstructured":"S. M. Ali and S. D. Silvey . 1966 . A General Class of Coefficients of Divergence of One Distribution from Another . J. R. Stat. Soc. B. 28 , 1 (Jan. 1966), 131\u2013142. S. M. Ali and S. D. Silvey. 1966. A General Class of Coefficients of Divergence of One Distribution from Another. J. R. Stat. Soc. B. 28, 1 (Jan. 1966), 131\u2013142.","journal-title":"J. R. Stat. Soc. B."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_2_4_1","volume-title":"Topics in Current Physics","volume":"7","author":"Ed Kurt Binder","year":"1986","unstructured":"Kurt Binder ( Ed .). 1986 . Monte Carlo Methods in Statistical Physics (2 ed.) . Topics in Current Physics , Vol. 7 . Springer-Verlag, Berlin. Kurt Binder (Ed.). 1986. Monte Carlo Methods in Statistical Physics (2 ed.). Topics in Current Physics, Vol. 7. Springer-Verlag, Berlin."},{"key":"e_1_2_2_5_1","volume-title":"Efficient Generation \u03f5-close to G(n, p) and Generalizations. (April","author":"Blanca Antonio","year":"2012","unstructured":"Antonio Blanca and Milena Mihail . 2012. Efficient Generation \u03f5-close to G(n, p) and Generalizations. (April 2012 ). arXiv: 1204.5834 Antonio Blanca and Milena Mihail. 2012. Efficient Generation \u03f5-close to G(n, p) and Generalizations. (April 2012). arXiv: 1204.5834"},{"key":"e_1_2_2_6_1","volume-title":"Complexity and Real Computation","author":"Blum Lenore","unstructured":"Lenore Blum , Felipe Cucker , Michael Shub , and Steve Smale . 1998. Complexity and Real Computation . Springer-Verlag , New York . Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. 1998. Complexity and Real Computation. Springer-Verlag, New York."},{"key":"e_1_2_2_7_1","first-page":"2","article-title":"Independent Unbiased Coin Flips from a Correlated Biased Source","volume":"6","author":"Blum Manuel","year":"1986","unstructured":"Manuel Blum . 1986 . Independent Unbiased Coin Flips from a Correlated Biased Source : A Finite State Markov Chain. Combinatorica 6 , 2 (June 1986), 97\u2013108. Manuel Blum. 1986. Independent Unbiased Coin Flips from a Correlated Biased Source: A Finite State Markov Chain. Combinatorica 6, 2 (June 1986), 97\u2013108.","journal-title":"A Finite State Markov Chain. Combinatorica"},{"key":"e_1_2_2_8_1","series-title":"Lecture Notes in Computer Science","volume-title":"ICALP 2013: Proceedings of the 40th International Colloquium on Automata, Languages and Programming (Riga, Latvia)","author":"Bringmann Karl","unstructured":"Karl Bringmann and Tobias Friedrich . 2013. Exact and Efficient Generation of Geometric Random Variates and Random Graphs . In ICALP 2013: Proceedings of the 40th International Colloquium on Automata, Languages and Programming (Riga, Latvia) . Lecture Notes in Computer Science , Vol. 7965 . Springer , Heidelberg , 267\u2013278. Karl Bringmann and Tobias Friedrich. 2013. Exact and Efficient Generation of Geometric Random Variates and Random Graphs. In ICALP 2013: Proceedings of the 40th International Colloquium on Automata, Languages and Programming (Riga, Latvia). Lecture Notes in Computer Science, Vol. 7965. Springer, Heidelberg, 267\u2013278."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0205-0"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.878151"},{"key":"e_1_2_2_11_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"2006","unstructured":"Thomas M. Cover and Joy A . Thomas . 2006 . Elements of Information Theory (2 ed.). John Wiley & amp; Sons, Inc., Hoboken. Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory (2 ed.). John Wiley &amp; Sons, Inc., Hoboken."},{"key":"e_1_2_2_12_1","volume-title":"Gen: A General-purpose Probabilistic Programming System with Programmable Inference. In PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Cusumano-Towner Marco F.","unstructured":"Marco F. Cusumano-Towner , Feras A. Saad , Alexander K. Lew , and Vikash K. Mansinghka . 2019 . Gen: A General-purpose Probabilistic Programming System with Programmable Inference. In PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation ( Phoenix, AZ, USA). ACM, New York, 221\u2013236. Marco F. Cusumano-Towner, Feras A. Saad, Alexander K. Lew, and Vikash K. Mansinghka. 2019. Gen: A General-purpose Probabilistic Programming System with Programmable Inference. In PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (Phoenix, AZ, USA). ACM, New York, 221\u2013236."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1155\/2012\/675130"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/00949658208810536"},{"key":"e_1_2_2_15_1","volume-title":"Non-Uniform Random Variate Generation","author":"Devroye Luc","unstructured":"Luc Devroye . 1986. Non-Uniform Random Variate Generation . Springer-Verlag , New York . Luc Devroye. 1986. Non-Uniform Random Variate Generation. Springer-Verlag, New York."},{"key":"e_1_2_2_16_1","volume-title":"Sampling with Arbitrary Precision. (Feb","author":"Devroye Luc","year":"2015","unstructured":"Luc Devroye and Claude Gravel . 2015. Sampling with Arbitrary Precision. (Feb . 2015 ). arXiv: 1502.02539 Luc Devroye and Claude Gravel. 2015. Sampling with Arbitrary Precision. (Feb. 2015). arXiv: 1502.02539"},{"key":"e_1_2_2_17_1","volume-title":"A Divisive Information-Theoretic Feature Clustering Algorithm for Text Classification. J. Mach. Learn. Res. 3 (March","author":"Dhillon Inderjit S.","year":"2003","unstructured":"Inderjit S. Dhillon , Subramanyam Mallela , and Rahul Kumar . 2003. A Divisive Information-Theoretic Feature Clustering Algorithm for Text Classification. J. Mach. Learn. Res. 3 (March 2003 ), 1265\u20131287. Inderjit S. Dhillon, Subramanyam Mallela, and Rahul Kumar. 2003. A Divisive Information-Theoretic Feature Clustering Algorithm for Text Classification. J. Mach. Learn. Res. 3 (March 2003), 1265\u20131287."},{"key":"e_1_2_2_18_1","volume-title":"Retrieved","author":"Djuric Dragan","year":"2019","unstructured":"Dragan Djuric . 2019 . Billions of Random Numbers in a Blink of an Eye . Retrieved June 15, 2019 from https:\/\/dragan.rocks\/ articles\/19\/Billion- random- numbers- blink- eye- Clojure Dragan Djuric. 2019. Billions of Random Numbers in a Blink of an Eye. Retrieved June 15, 2019 from https:\/\/dragan.rocks\/ articles\/19\/Billion- random- numbers- blink- eye- Clojure"},{"key":"e_1_2_2_19_1","volume-title":"Towards Efficient Discrete Gaussian Sampling For Lattice-Based Cryptography. In FPL 2015: Proceedings of the 25th International Conference on Field Programmable Logic and Applications","author":"Du Chaohui","year":"2015","unstructured":"Chaohui Du and Guoqiang Bai . 2015 . Towards Efficient Discrete Gaussian Sampling For Lattice-Based Cryptography. In FPL 2015: Proceedings of the 25th International Conference on Field Programmable Logic and Applications ( London, UK). IEEE Press, Piscataway, 1\u20136. Chaohui Du and Guoqiang Bai. 2015. Towards Efficient Discrete Gaussian Sampling For Lattice-Based Cryptography. In FPL 2015: Proceedings of the 25th International Conference on Field Programmable Logic and Applications (London, UK). IEEE Press, Piscataway, 1\u20136."},{"key":"e_1_2_2_20_1","first-page":"3","article-title":"Sampling from Discrete Gaussians for Lattice-Based Cryptography On a Constrained","volume":"25","author":"Dwarakanath Nagarjun C.","year":"2014","unstructured":"Nagarjun C. Dwarakanath and Steven D. Galbraith . 2014 . Sampling from Discrete Gaussians for Lattice-Based Cryptography On a Constrained Device. Appl. Algebr. Eng. Comm. 25 , 3 (June 2014), 159\u2013180. Nagarjun C. Dwarakanath and Steven D. Galbraith. 2014. Sampling from Discrete Gaussians for Lattice-Based Cryptography On a Constrained Device. Appl. Algebr. Eng. Comm. 25, 3 (June 2014), 159\u2013180.","journal-title":"Device. Appl. Algebr. Eng. Comm."},{"key":"e_1_2_2_21_1","first-page":"3","article-title":"The Efficient Construction of an Unbiased Random","volume":"43","author":"Elias Peter","year":"1972","unstructured":"Peter Elias . 1972 . The Efficient Construction of an Unbiased Random Sequence. Ann. Math. Stat. 43 , 3 (June 1972), 865\u2013870. Peter Elias. 1972. The Efficient Construction of an Unbiased Random Sequence. Ann. Math. Stat. 43, 3 (June 1972), 865\u2013870.","journal-title":"Sequence. Ann. Math. Stat."},{"key":"e_1_2_2_22_1","first-page":"1","article-title":"Gaussian Sampling in Lattice Based Cryptography","volume":"60","author":"Foll\u00e1th J\u00e1nos","year":"2014","unstructured":"J\u00e1nos Foll\u00e1th . 2014 . Gaussian Sampling in Lattice Based Cryptography . Tatra Mount. Math. Pub. 60 , 1 (Sept. 2014), 1\u201323. J\u00e1nos Foll\u00e1th. 2014. Gaussian Sampling in Lattice Based Cryptography. Tatra Mount. Math. Pub. 60, 1 (Sept. 2014), 1\u201323.","journal-title":"Tatra Mount. Math. Pub."},{"key":"e_1_2_2_23_1","volume-title":"GNU Scientific Library","author":"Galassi Mark","unstructured":"Mark Galassi , Jim Davies , James Theiler , Brian Gough , Gerard Jungman , Patrick Alken , Michael Booth , Fabrice Rossi , and Rhys Ulerich . 2019. GNU Scientific Library . Free Software Foundation . Mark Galassi, Jim Davies, James Theiler, Brian Gough, Gerard Jungman, Patrick Alken, Michael Booth, Fabrice Rossi, and Rhys Ulerich. 2019. GNU Scientific Library. Free Software Foundation."},{"key":"e_1_2_2_24_1","volume-title":"Monte Carlo Methods in Financial Engineering. Stochastic Modeling and Applied Probability","author":"Glasserman Paul","unstructured":"Paul Glasserman . 2003. Monte Carlo Methods in Financial Engineering. Stochastic Modeling and Applied Probability , Vol. 53 . Springer Science +Business Media, New York. Paul Glasserman. 2003. Monte Carlo Methods in Financial Engineering. Stochastic Modeling and Applied Probability, Vol. 53. Springer Science+Business Media, New York."},{"key":"e_1_2_2_25_1","volume-title":"Probabilistic Programming. In FOSE 2014: Proceedings of the on Future of Software Engineering","author":"Gordon Andrew D.","unstructured":"Andrew D. Gordon , Thomas A. Henzinger , Aditya V. Nori , and Sriram K. Rajamani . 2014 . Probabilistic Programming. In FOSE 2014: Proceedings of the on Future of Software Engineering ( Hyderabad, India). ACM, New York, 167\u2013181. Andrew D. Gordon, Thomas A. Henzinger, Aditya V. Nori, and Sriram K. Rajamani. 2014. Probabilistic Programming. In FOSE 2014: Proceedings of the on Future of Software Engineering (Hyderabad, India). ACM, New York, 167\u2013181."},{"key":"e_1_2_2_26_1","first-page":"2","article-title":"Interval Algorithm for Random Number Generation","volume":"43","author":"Han Te Sun","year":"1997","unstructured":"Te Sun Han and Mamoru Hoshi . 1997 . Interval Algorithm for Random Number Generation . IEEE Trans. Inf. Theory 43 , 2 (March 1997), 599\u2013611. Te Sun Han and Mamoru Hoshi. 1997. Interval Algorithm for Random Number Generation. IEEE Trans. Inf. Theory 43, 2 (March 1997), 599\u2013611.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.256486"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.3.307"},{"key":"e_1_2_2_30_1","volume-title":"Yao","author":"Knuth Donald E.","year":"1976","unstructured":"Donald E. Knuth and Andrew C . Yao . 1976 . The Complexity of Nonuniform Random Number Generation. In Algorithms and Complexity: New Directions and Recent Results, Joseph F. Traub (Ed.). Academic Press , Inc., Orlando, FL, 357\u2013428. Donald E. Knuth and Andrew C. Yao. 1976. The Complexity of Nonuniform Random Number Generation. In Algorithms and Complexity: New Directions and Recent Results, Joseph F. Traub (Ed.). Academic Press, Inc., Orlando, FL, 357\u2013428."},{"key":"e_1_2_2_31_1","series-title":"Lecture Notes in Computer Science","volume-title":"Horizons of the Mind. A Tribute to Prakash Panangaden: Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday","author":"Kozen Dexter","unstructured":"Dexter Kozen . 2014. Optimal Coin Flipping . In Horizons of the Mind. A Tribute to Prakash Panangaden: Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday . Lecture Notes in Computer Science , Vol. 8464 . Springer , Cham , 407\u2013426. Dexter Kozen. 2014. Optimal Coin Flipping. In Horizons of the Mind. A Tribute to Prakash Panangaden: Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, Vol. 8464. Springer, Cham, 407\u2013426."},{"key":"e_1_2_2_32_1","series-title":"Lecture Notes in Computer Science","volume-title":"RAMiCS 2018: Proceedings of the 17th International Conference on Relational and Algebraic Methods in Computer Science (Groningen, The Netherlands)","author":"Kozen Dexter","unstructured":"Dexter Kozen and Matvey Soloviev . 2018. Coalgebraic Tools for Randomness-Conserving Protocols . In RAMiCS 2018: Proceedings of the 17th International Conference on Relational and Algebraic Methods in Computer Science (Groningen, The Netherlands) . Lecture Notes in Computer Science , Vol. 11194 . Springer , Cham , 298\u2013313. Dexter Kozen and Matvey Soloviev. 2018. Coalgebraic Tools for Randomness-Conserving Protocols. In RAMiCS 2018: Proceedings of the 17th International Conference on Relational and Algebraic Methods in Computer Science (Groningen, The Netherlands). Lecture Notes in Computer Science, Vol. 11194. Springer, Cham, 298\u2013313."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729694"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2009.06.019"},{"key":"e_1_2_2_35_1","volume-title":"User\u2019s Guide to the GNU C++ Library","author":"Lea Dopug","unstructured":"Dopug Lea . 1992. User\u2019s Guide to the GNU C++ Library . Free Software Foundation, Inc. Dopug Lea. 1992. User\u2019s Guide to the GNU C++ Library. Free Software Foundation, Inc."},{"key":"e_1_2_2_36_1","unstructured":"Josef Leydold and Sougata Chaudhuri. 2014. rvgtest: Tools for Analyzing Non-Uniform Pseudo-Random Variate Generators. https:\/\/CRAN.R- project.org\/package=rvgtest R package version 0.7.4.  Josef Leydold and Sougata Chaudhuri. 2014. rvgtest: Tools for Analyzing Non-Uniform Pseudo-Random Variate Generators. https:\/\/CRAN.R- project.org\/package=rvgtest R package version 0.7.4."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.881731"},{"key":"e_1_2_2_38_1","volume-title":"Monte Carlo Strategies in Scientific Computing","author":"Liu Jun S.","unstructured":"Jun S. Liu . 2001. Monte Carlo Strategies in Scientific Computing . Springer , New York . Jun S. Liu. 2001. Monte Carlo Strategies in Scientific Computing. Springer, New York."},{"key":"e_1_2_2_39_1","volume-title":"Optimal Discrete Uniform Generation from Coin Flips, and Applications. (April","author":"Lumbroso J\u00e9rmie","year":"2013","unstructured":"J\u00e9rmie Lumbroso . 2013. Optimal Discrete Uniform Generation from Coin Flips, and Applications. (April 2013 ). arXiv: 1304.1916 J\u00e9rmie Lumbroso. 2013. Optimal Discrete Uniform Generation from Coin Flips, and Applications. (April 2013). arXiv: 1304.1916"},{"key":"e_1_2_2_40_1","volume-title":"Building Fast Bayesian Computing Machines Out of Intentionally Stochastic Digital Parts. (Feb","author":"Mansinghka Vikash","year":"2014","unstructured":"Vikash Mansinghka and Eric Jonas . 2014. Building Fast Bayesian Computing Machines Out of Intentionally Stochastic Digital Parts. (Feb . 2014 ). arXiv: 1402.4914 Vikash Mansinghka and Eric Jonas. 2014. Building Fast Bayesian Computing Machines Out of Intentionally Stochastic Digital Parts. (Feb. 2014). arXiv: 1402.4914"},{"key":"e_1_2_2_41_1","volume-title":"Statistics Toolbox User\u2019s Guide. The MathWorks","author":"MathWorks The","unstructured":"The MathWorks . 1993. Statistics Toolbox User\u2019s Guide. The MathWorks , Inc . The MathWorks. 1993. Statistics Toolbox User\u2019s Guide. The MathWorks, Inc."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1985-0804945-X"},{"key":"e_1_2_2_43_1","volume-title":"Efficient Synthesis of Probabilistic Programs. In PLDI 2015: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Nori Aditya V.","year":"2015","unstructured":"Aditya V. Nori , Sherjil Ozair , Sriram K. Rajamani , and Deepak Vijaykeerthy . 2015 . Efficient Synthesis of Probabilistic Programs. In PLDI 2015: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation ( Portland, OR, USA). ACM, New York, 208\u2013217. Aditya V. Nori, Sherjil Ozair, Sriram K. Rajamani, and Deepak Vijaykeerthy. 2015. Efficient Synthesis of Probabilistic Programs. In PLDI 2015: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (Portland, OR, USA). ACM, New York, 208\u2013217."},{"key":"e_1_2_2_44_1","first-page":"11","article-title":"Randomizing Functions: Simulation of a Discrete Probability Distribution Using a Source of Unknown Distribution","volume":"52","author":"Loui Pae","year":"2006","unstructured":"Sung-il Pae and Michael C Loui . 2006 . Randomizing Functions: Simulation of a Discrete Probability Distribution Using a Source of Unknown Distribution . IEEE Trans. Inf. Theory 52 , 11 (Nov. 2006), 4965\u20134976. Sung-il Pae and Michael C Loui. 2006. Randomizing Functions: Simulation of a Discrete Probability Distribution Using a Source of Unknown Distribution. IEEE Trans. Inf. Theory 52, 11 (Nov. 2006), 4965\u20134976.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786440009463897"},{"key":"e_1_2_2_46_1","first-page":"1","article-title":"Iterating von Neumann\u2019s Procedure for Extracting Random","volume":"20","author":"Peres Yuval","year":"1992","unstructured":"Yuval Peres . 1992 . Iterating von Neumann\u2019s Procedure for Extracting Random Bits. Ann. Stat. 20 , 1 (March 1992), 590\u2013597. Yuval Peres. 1992. Iterating von Neumann\u2019s Procedure for Extracting Random Bits. Ann. Stat. 20, 1 (March 1992), 590\u2013597.","journal-title":"Bits. Ann. Stat."},{"key":"e_1_2_2_47_1","volume-title":"R: A Language and Environment for Statistical Computing","author":"Team R Core","year":"2014","unstructured":"R Core Team . 2014 . R: A Language and Environment for Statistical Computing . R Foundation for Statistical Computing , Vienna, Austria . http:\/\/www.R- project.org\/ R Core Team. 2014. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. http:\/\/www.R- project.org\/"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.1991.695225"},{"key":"e_1_2_2_49_1","volume-title":"High Precision Discrete Gaussian Sampling on FPGAs. In SAC 2013: Proceedings of the 20th International Conference on Selected Areas in Cryptography","volume":"8282","author":"Roy Sinha S.","year":"2013","unstructured":"Sinha S. Roy , Frederik Vercauteren , and Ingrid Verbauwhede . 2013 . High Precision Discrete Gaussian Sampling on FPGAs. In SAC 2013: Proceedings of the 20th International Conference on Selected Areas in Cryptography ( Burnaby, Canada). Lecture Notes in Computer Science , Vol. 8282 . Springer, Berlin, 383\u2013401. Sinha S. Roy, Frederik Vercauteren, and Ingrid Verbauwhede. 2013. High Precision Discrete Gaussian Sampling on FPGAs. In SAC 2013: Proceedings of the 20th International Conference on Selected Areas in Cryptography (Burnaby, Canada). Lecture Notes in Computer Science, Vol. 8282. Springer, Berlin, 383\u2013401."},{"key":"e_1_2_2_50_1","volume-title":"Probabilistic Data Analysis with Probabilistic Programming. (Aug","author":"Saad Feras","year":"2016","unstructured":"Feras Saad and Vikash Mansinghka . 2016. Probabilistic Data Analysis with Probabilistic Programming. (Aug . 2016 ). arXiv: 1608.05347 Feras Saad and Vikash Mansinghka. 2016. Probabilistic Data Analysis with Probabilistic Programming. (Aug. 2016). arXiv: 1608.05347"},{"key":"e_1_2_2_51_1","volume-title":"Proc. ACM Program. Lang. 3, POPL, Article 37 (Jan.","author":"Saad Feras A.","year":"2019","unstructured":"Feras A. Saad , Marco F. Cusumano-Towner , Ulrich Schaechtle , Martin C. Rinard , and Vikash K. Mansinghka . 2019. Bayesian Synthesis of Probabilistic Programs for Automatic Data Modeling . Proc. ACM Program. Lang. 3, POPL, Article 37 (Jan. 2019 ), 32 pages. Feras A. Saad, Marco F. Cusumano-Towner, Ulrich Schaechtle, Martin C. Rinard, and Vikash K. Mansinghka. 2019. Bayesian Synthesis of Probabilistic Programs for Automatic Data Modeling. Proc. ACM Program. Lang. 3, POPL, Article 37 (Jan. 2019), 32 pages."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935313"},{"key":"e_1_2_2_56_1","first-page":"1","article-title":"Tree Algorithms for Unbiased Coin Tossing with a Biased","volume":"12","author":"Stout Quentin F.","year":"1984","unstructured":"Quentin F. Stout and Bette Warren . 1984 . Tree Algorithms for Unbiased Coin Tossing with a Biased Coin. Ann. Probab. 12 , 1 (Feb. 1984), 212\u2013222. Quentin F. Stout and Bette Warren. 1984. Tree Algorithms for Unbiased Coin Tossing with a Biased Coin. Ann. Probab. 12, 1 (Feb. 1984), 212\u2013222.","journal-title":"Coin. Ann. Probab."},{"key":"e_1_2_2_57_1","first-page":"10","article-title":"Two Algorithms for Random Number Generation Implemented by Using Arithmetic of Limited Precision","volume":"86","author":"Uyematsu Tomohiko","year":"2003","unstructured":"Tomohiko Uyematsu and Yuan Li . 2003 . Two Algorithms for Random Number Generation Implemented by Using Arithmetic of Limited Precision . IEICE Trans. Fund. Elec. Comm. Comp. Sci 86 , 10 (Oct. 2003), 2542\u20132551. Tomohiko Uyematsu and Yuan Li. 2003. Two Algorithms for Random Number Generation Implemented by Using Arithmetic of Limited Precision. IEICE Trans. Fund. Elec. Comm. Comp. Sci 86, 10 (Oct. 2003), 2542\u20132551.","journal-title":"IEICE Trans. Fund. Elec. Comm. Comp. Sci"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.412679"},{"key":"e_1_2_2_59_1","series-title":"National Bureau of Standards Applied Mathematics Series","volume-title":"Various Techniques Used in Connection with Random Digits","author":"von Neumann John","unstructured":"John von Neumann . 1951. Various Techniques Used in Connection with Random Digits . In Monte Carlo Method, A. S. Householder, G. E. Forsythe, and H. H. Germond (Eds.). National Bureau of Standards Applied Mathematics Series , Vol. 12 . U.S. Government Printing Office, Washington, DC , Chapter 13, 36\u201338. John von Neumann. 1951. Various Techniques Used in Connection with Random Digits. In Monte Carlo Method, A. S. Householder, G. E. Forsythe, and H. H. Germond (Eds.). National Bureau of Standards Applied Mathematics Series, Vol. 12. U.S. Government Printing Office, Washington, DC, Chapter 13, 36\u201338."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1049\/el:19740097"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355749"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371104","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:43Z","timestamp":1750273543000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,20]]},"references-count":59,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1145\/3371104"],"URL":"https:\/\/doi.org\/10.1145\/3371104","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,20]]},"assertion":[{"value":"2019-12-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}