1. bookVolume 26 (2017): Issue 1 (June 2017)
Journal Details
License
Format
Journal
First Published
30 Mar 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

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

Published Online: 14 Jul 2017
Page range: 22 - 45
Received: 30 Sep 2016
Journal Details
License
Format
Journal
First Published
30 Mar 2015
Publication timeframe
4 times per year
Languages
English

We demonstrate an approach for exact sampling of certain discrete combinatorial distributions, which is a hybrid of exact Boltzmann sampling and the recursive method, using probabilistic divide-and-conquer (PDC). The approach specializes to exact Boltzmann sampling in the trivial setting, and specializes to PDC deterministic second half in the first non-trivial application. A large class of examples is given for which this method broadly applies, and several examples are worked out explicitly.

Keywords

[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.Search in Google Scholar

[2] L. Alonso, Uniform generation of a Motzkin word, Theoret. Comput. Sci., 134 (1994) 529-536.Search 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.Search in Google Scholar

[4] R. Arratia and S. Tavare, Independent process approximations for random combinatorial structures, Adv. Math., 104 (1994) 90-154.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search 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.Search in Google Scholar

[18] G. H. Hardy and S. Ramanujan, Asymptotic formulaæ in combinatory analysis, Proc. Lond. Math. Soc. (3), 2 (1918) 75-115.Search 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.Search 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.Search in Google Scholar

[22] D. A. Levin, Y. Peres and E. L. Wilmer, Markov chains and mixing times, American Mathematical Soc., 2009.Search 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.Search 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.Search 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.Search in Google Scholar

[28] B. Pittel, Random set partitions: asymptotics of subset counts, J. Combin. Theory Ser. A, 79 (1997) 326-359.Search 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.Search in Google Scholar

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

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

[32] G. Szekeres, Some asymptotic formulae in the theory of partitions. II, Q. J. Math., 4 (1953) 96-111.Search 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.Search 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.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo