{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T13:03:58Z","timestamp":1769519038985,"version":"3.49.0"},"reference-count":42,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2016,1,22]],"date-time":"2016-01-22T00:00:00Z","timestamp":1453420800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2016,5]]},"abstract":"<jats:p>We propose a new method, probabilistic divide-and-conquer, for improving the success probability in rejection sampling. For the example of integer partitions, there is an ideal recursive scheme which improves the rejection cost from asymptotically order<jats:italic>n<\/jats:italic><jats:sup>3\/4<\/jats:sup>to a constant. We show other examples for which a non-recursive, one-time application of probabilistic divide-and-conquer removes a substantial fraction of the rejection sampling cost.<\/jats:p><jats:p>We also present a variation of probabilistic divide-and-conquer for generating i.i.d. samples that exploits features of the coupon collector's problem, in order to obtain a cost that is sublinear in the number of samples.<\/jats:p>","DOI":"10.1017\/s0963548315000358","type":"journal-article","created":{"date-parts":[[2016,1,22]],"date-time":"2016-01-22T10:31:05Z","timestamp":1453458665000},"page":"324-351","source":"Crossref","is-referenced-by-count":19,"title":["Probabilistic Divide-and-Conquer: A New Exact Simulation Method, With Integer Partitions as an Example"],"prefix":"10.1017","volume":"25","author":[{"given":"RICHARD","family":"ARRATIA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"STEPHEN","family":"DeSALVO","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,1,22]]},"reference":[{"key":"S0963548315000358_ref28","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1939-0000410-9"},{"key":"S0963548315000358_ref22","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-17.1.75"},{"key":"S0963548315000358_ref19","unstructured":"Engel B. (2014) Log-concavity of the overpartition function. arXiv: 1412.4603"},{"key":"S0963548315000358_ref42","first-page":"36","article-title":"Various techniques used in connection with random digits","volume":"3","author":"von Neumann","year":"1951","journal-title":"Journal of Research of the National Bureau of Standards, Appl. Math. Series"},{"key":"S0963548315000358_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(75)90013-8"},{"key":"S0963548315000358_ref25","first-page":"357","volume-title":"Algorithms and complexity: Proc. Sympos., Carnegie-Mellon University, Pittsburgh, PA","author":"Knuth","year":"1976"},{"key":"S0963548315000358_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s11139-014-9599-y"},{"key":"S0963548315000358_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/0150020"},{"key":"S0963548315000358_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/0471200611"},{"key":"S0963548315000358_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990332"},{"key":"S0963548315000358_ref35","volume-title":"Combinatorial Algorithms: For Computers and Calculators","author":"Nijenhuis","year":"1978"},{"key":"S0963548315000358_ref14","unstructured":"DeSalvo S. (2014) Probabilistic divide-and-conquer: deterministic second half. arXiv:1411.6698"},{"key":"S0963548315000358_ref5","first-page":"29","volume-title":"Contemporary Combinatorics","author":"Arratia","year":"2002"},{"key":"S0963548315000358_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00323-5"},{"key":"S0963548315000358_ref6","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176347615"},{"key":"S0963548315000358_ref23","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157012001088"},{"key":"S0963548315000358_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(91)90079-Q"},{"key":"S0963548315000358_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(91)90080-U"},{"key":"S0963548315000358_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8643-8"},{"key":"S0963548315000358_ref30","volume-title":"Version 7.12.0.635 (R2011a)","year":"2011"},{"key":"S0963548315000358_ref8","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176992808"},{"key":"S0963548315000358_ref20","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1215\/S0012-7094-41-00826-8","article-title":"The distribution of the number of summands in the partitions of a positive integer","volume":"8","author":"Erd\u0151s","year":"1941","journal-title":"Duke Math. J."},{"key":"S0963548315000358_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006315"},{"key":"S0963548315000358_ref29","volume-title":"Mathematica Edition: Version 8.0","year":"2010"},{"key":"S0963548315000358_ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s11139-009-9184-y"},{"key":"S0963548315000358_ref39","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.23.2.78"},{"key":"S0963548315000358_ref13","unstructured":"DeSalvo S. (2012) Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example and lower bound expansions for random Bernoulli matrices via novel integer partitions. PhD thesis, University of Southern California."},{"key":"S0963548315000358_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/C-M.1977.217750"},{"key":"S0963548315000358_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548315000358_ref26","article-title":"Affine insertion and Pieri rules for the affine Grassmannian","volume":"208","author":"Lam","year":"2010","journal-title":"Mem. Amer. Math. Soc."},{"key":"S0963548315000358_ref7","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1994.1022"},{"key":"S0963548315000358_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90029-E"},{"key":"S0963548315000358_ref38","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2791"},{"key":"S0963548315000358_ref33","doi-asserted-by":"publisher","DOI":"10.5802\/aif.714"},{"key":"S0963548315000358_ref37","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1996.0523"},{"key":"S0963548315000358_ref27","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1938-1501943-5"},{"key":"S0963548315000358_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s11139-011-9365-3"},{"key":"S0963548315000358_ref21","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1993-1094553-1"},{"key":"S0963548315000358_ref40","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(82)90040-1"},{"key":"S0963548315000358_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/s11139-006-9576-1"},{"key":"S0963548315000358_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00086-7"},{"key":"S0963548315000358_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511608650"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548315000358","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,2]],"date-time":"2022-06-02T05:12:49Z","timestamp":1654146769000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548315000358\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,22]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["S0963548315000358"],"URL":"https:\/\/doi.org\/10.1017\/s0963548315000358","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,22]]}}}