Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method

[1] D. J. Aldous, Exchangeability and related topics, in: École d'été de probabilités de Saint-Flour, XIII-1983, Lecture Notes in Math., 1117 (1985) 1-198.10.1007/BFb0099421Search in Google Scholar

[2] L. Alonso, Uniform generation of a Motzkin word, Theoret. Comput. Sci., 134 (1994) 529-536.10.1016/0304-3975(94)00086-7Search in Google Scholar

[3] R. Arratia and S. DeSalvo, Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example, Combin. Probab. Comput., 25 (2016) 324-351.10.1017/S0963548315000358Search in Google Scholar

[4] R. Arratia and S. Tavare, Independent process approximations for random combinatorial structures, Adv. Math., 104 (1994) 90-154.10.1006/aima.1994.1022Search in Google Scholar

[5] E. A. Bender and J. R. Goldman, Enumerative uses of generating functions, Indiana Univ. Math. J., 20 (1970/1971) 753-765.10.1512/iumj.1971.20.20060Search in Google Scholar

[6] I. Bezáková, A. Sinclair, D. Štefankovič and E. Vigoda, Negative examples for sequential importance sampling of binary contingency tables, in: Algorithms-ESA 2006, Springer, 2006, pp. 136-147.10.1007/11841036_15Search in Google Scholar

[7] L. V. Bogachev, Unified derivation of the limit shape for multiplicative ensembles of random integer partitions with equiweighted parts, Random Structures Algorithms, 47 (2015) 227-266.10.1002/rsa.20540Search in Google Scholar

[8] N. G. De Bruijn, Asymptotic methods in analysis, volume 4, Courier Dover Publications, 1970.Search in Google Scholar

[9] A. Dembo, A. Vershik and O. Zeitouni, Large deviations for integer partitions, Institut des Hautes Etudes Scientifiques [IHES], 1998.Search in Google Scholar

[10] A. Denise and P. Zimmermann, Uniform random generation of decomposable structures using floating-point arithmetic, Theoret. Comput. Sci., 218 (1999) 233-248.10.1016/S0304-3975(98)00323-5Search in Google Scholar

[11] S. DeSalvo, Probabilistic divide-and-conquer: deterministic second half, Adv. in Appl. Math., to appear.Search in Google Scholar

[12] L. Devroye, Nonuniform random variate generation, Handbooks Oper. Res. Management Sci., 13 (2006) 83-121.10.1016/S0927-0507(06)13004-2Search in Google Scholar

[13] P. Duchon, P. Flajolet, G. Louchard and G. Schaeffer, Boltzmann samplers for the random generation of combinatorial structures, Combin. Probab. Comput., 13 (2004) 577-625.10.1017/S0963548304006315Search in Google Scholar

[14] P. Erdōs, On an elementary proof of some asymptotic formulas in the theory of partitions, Ann. of Math. (2), 43 (1942) 437-450.10.2307/1968802Search in Google Scholar

[15] P. Erdōs and J. Lehner, The distribution of the number of summands in the partitions of a positive integer, Duke Math. J, 8 (1941) 335-345.10.1215/S0012-7094-41-00826-8Search in Google Scholar

[16] R. A. Fisher and F. Yates, Statistical Tables for Biological, Agricultural and Medical Research, 2nd ed., Oliver and Boyd Ltd., London, 1943. .Search in Google Scholar

[17] B. Fristedt, The structure of random partitions of large integers, Trans. Amer. Math. Soc., 337 (1993) 703-735.10.1090/S0002-9947-1993-1094553-1Search in Google Scholar

[18] G. H. Hardy and S. Ramanujan, Asymptotic formulaæ in combinatory analysis, Proc. Lond. Math. Soc. (3), 2 (1918) 75-115.10.1112/plms/s2-17.1.75Search in Google Scholar

[19] M. L. Huber, Perfect Simulation, Chapman & Hall/CRC Monographs on Statistics & Applied Probability, Taylor & Francis, 2015.Search in Google Scholar

[20] S. V. Kerov and A. M. Vershik, The characters of the infinite symmetric group and probability properties of the Robinson-Schensted-Knuth algorithm, SIAM J. Algebraic Discrete Methods, 7 (1986) 116-124.10.1137/0607014Search in Google Scholar

[21] D. H. Lehmer, On the remainders and convergence of the series for the partition function, Trans. Amer. Math. Soc., 46 (1939) 362-373.10.1090/S0002-9947-1939-0000410-9Search in Google Scholar

[22] D. A. Levin, Y. Peres and E. L. Wilmer, Markov chains and mixing times, American Mathematical Soc., 2009.10.1090/mbk/058Search in Google Scholar

[23] L. Moser and M. Wyman, An asymptotic formula for the Bell numbers, Trans. Roy. Soc. Canada. Sect. III. (3), 49 (1955) 49-54.Search in Google Scholar

[24] E. Mossel and E. Vigoda, Limitations of Markov chain Monte Carlo algorithms for Bayesian inference of phylogeny, Ann. Appl. Probab., 16 (2006) 2215-2234.10.1214/105051600000000538Search in Google Scholar

[25] A. Nijenhuis and H. S. Wilf, A method and two algorithms on the theory of partitions, J. Combin. Theory Ser. A, 18 (1975) 219-222.10.1016/0097-3165(75)90013-8Search in Google Scholar

[26] A. Nijenhuis and H. S. Wilf, Combinatorial algorithms, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, second edition, 1978. For computers and calculators, Computer Science and Applied Mathematics.Search in Google Scholar

[27] B. Pittel, On a likely shape of the random Ferrers diagram, Adv. in Appl. Math., 18 (1997) 432-488.10.1006/aama.1996.0523Search in Google Scholar

[28] B. Pittel, Random set partitions: asymptotics of subset counts, J. Combin. Theory Ser. A, 79 (1997) 326-359.10.1006/jcta.1997.2791Search in Google Scholar

[29] J. G. Propp and D. B. Wilson, Exact sampling with coupled markov chains and applications to statistical mechanics, Random Structures Algorithms, 9 (1996) 223-252.10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO;2-OSearch in Google Scholar

[30] H. Rademacher, On the partition function p(n), Proc. Lond. Math. Soc., 2 (1938) 241-254.10.1112/plms/s2-43.4.241Search in Google Scholar

[31] G. Szekeres, An asymptotic formula in the theory of partitions, Q. J. Math., 2 (1951) 85-108.10.1093/qmath/2.1.85Search in Google Scholar

[32] G. Szekeres, Some asymptotic formulae in the theory of partitions. II, Q. J. Math., 4 (1953) 96-111.10.1093/qmath/4.1.96Search in Google Scholar

[33] H. N. V. Temperley, Statistical mechanics and the partition of numbers II. The form of crystal surfaces, Math. Proc. Cambridge Philos. Soc., 48 (1952) 683-697.10.1017/S0305004100076453Search in Google Scholar

[34] J. Von Neumann, Various techniques used in connection with random digits, J. Res. Nat. Bur. Stand., 12 (1951) 36-38.Search in Google Scholar

[35] Y. Yakubovich, Ergodicity of multiplicative statistics, J. Combin. Theory Ser. A, 119 (2012) 1250-1279.10.1016/j.jcta.2012.03.002Search in Google Scholar