Hostname: page-component-74656f9884-rngvg Total loading time: 0 Render date: 2026-11-04T11:33:42.393Z Has data issue: false hasContentIssue false
  • English
  • Français

Probabilistic Divide-and-Conquer: A New Exact Simulation Method, With Integer Partitions as an Example

Part of: Combinatorial probability Combinatorics

Published online by Cambridge University Press:  22 January 2016

RICHARD ARRATIA  and
STEPHEN DeSALVO
RICHARD ARRATIA
Affiliation:
Department of Mathematics, University of Southern California, Los Angeles, CA 90089, USA (e-mail: rarratia@math.usc.edu)
STEPHEN DeSALVO
Affiliation:
Department of Mathematics, University of California Los Angeles, Los Angeles, CA 90024, USA (e-mail: stephendesalvo@math.ucla.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 n 3/4 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.

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.

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05A17: Partitions of integers

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 3 , May 2016 , pp. 324 - 351
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Almkvist, G. (1991) Exact asymptotic formulas for the coefficients of nonmodular functions. J. Number Theory 38 145–160.CrossRefGoogle Scholar
[2] Almkvist, G. and Andrews, G. E. (1991) A Hardy–Ramanujan formula for restricted partitions. J. Number Theory 38 135–144.CrossRefGoogle Scholar
[3] Alonso, L. (1994) Uniform generation of a Motzkin word. Theoret. Comput. Sci. 134 529–536.CrossRefGoogle Scholar
[4] Andrews, G. E. (1984) The Theory of Partitions, Cambridge Mathematical Library.CrossRefGoogle Scholar
[5] Arratia, R. (2002) On the amount of dependence in the prime factorization of a uniform random integer. In Contemporary Combinatorics, Vol. 10 of Bolyai Society Mathematical Studies, János Bolyai Mathematical Society, pp. 29–91.Google Scholar
[6] Arratia, R., Gordon, L. and Waterman, M. S. (1990) The Erdős–Rényi law in distribution, for coin tossing and sequence matching. Ann. Statist. 18 529–570.CrossRefGoogle Scholar
[7] Arratia, R. and Tavaré, S. (1994) Independent process approximations for random combinatorial structures. Adv. Math. 104 90–154.CrossRefGoogle Scholar
[8] Arratia, R. and Waterman, M. S. (1985) Critical phenomena in sequence matching. Ann. Probab. 13 1236–1249.CrossRefGoogle Scholar
[9] Bodini, O., Fusy, E. and Pivoteau, C. (2010) Random sampling of plane partitions. Combin. Probab. Comput. 19 201–226.CrossRefGoogle Scholar
[10] Bollobás, B. (2001) Random Graphs, second edition, Vol. 73 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.CrossRefGoogle Scholar
[11] Cover, T. M. and Thomas, J. A. (1991) Elements of Information Theory, Wiley Series in Telecommunications, Wiley.Google Scholar
[12] Denise, A. and Zimmermann, P. (1999) Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci. 218 233–248.CrossRefGoogle Scholar
[13] 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.Google Scholar
[14] DeSalvo, S. (2014) Probabilistic divide-and-conquer: deterministic second half. arXiv:1411.6698 Google Scholar
[15] DeSalvo, S. and Pak, I. (2015) Log-concavity of the partition function. Ramanujan J. 38 61–73.CrossRefGoogle Scholar
[16] Devroye, L. (1986) Non-Uniform Random Variate Generation, Springer.CrossRefGoogle Scholar
[17] Diffie, W. and Hellman, M. E. (1977) Special feature exhaustive cryptanalysis of the NBS data encryption standard. Computer 10 74–84.CrossRefGoogle Scholar
[18] Duchon, P., Flajolet, P., Louchard, G. and Schaeffer, G. (2004) Boltzmann samplers for the random generation of combinatorial structures. Combin. Probab. Comput. 13 577–625.CrossRefGoogle Scholar
[19] Engel, B. (2014) Log-concavity of the overpartition function. arXiv: 1412.4603Google Scholar
[20] Erdős, P. and Lehner, J. (1941) The distribution of the number of summands in the partitions of a positive integer. Duke Math. J. 8 335–345.CrossRefGoogle Scholar
[21] Fristedt, B. (1993) The structure of random partitions of large integers. Trans. Amer. Math. Soc. 337 703–735.CrossRefGoogle Scholar
[22] Hardy, G. H. and Ramanujan, S. (1918) Asymptotic formulae in combinatory analysis. Proc. London Math. Soc. s2–17 (1) 75–115.CrossRefGoogle Scholar
[23] Johansson, F. (2012) Efficient implementation of the Hardy–Ramanujan–Rademacher formula. LMS J. Comput. Math. 15 341–359.CrossRefGoogle Scholar
[24] Knessl, C. and Keller, J. B. (1990) Partition asymptotics from recursion equations. SIAM J. Appl. Math. 50 323–338.CrossRefGoogle Scholar
[25] Knuth, D. E. and Yao, A. C. (1976) The complexity of nonuniform random number generation. In Algorithms and complexity: Proc. Sympos., Carnegie-Mellon University, Pittsburgh, PA, 1976, Academic Press, pp. 357–428.Google Scholar
[26] Lam, T., Lapointe, L., Morse, J. and Shimozono, M. (2010) Affine insertion and Pieri rules for the affine Grassmannian. Mem. Amer. Math. Soc. 208 (977).Google Scholar
[27] Lehmer, D. H. (1938) On the series for the partition function. Trans. Amer. Math. Soc. 43 271–295.CrossRefGoogle Scholar
[28] Lehmer, D. H. (1939) On the remainders and convergence of the series for the partition function. Trans. Amer. Math. Soc. 46 362–373.CrossRefGoogle Scholar
[29] Mathematica (2010) Mathematica Edition: Version 8.0, Wolfram Research, Inc. Google Scholar
[30] MATLAB (2011) Version 7.12.0.635 (R2011a), The MathWorks, Inc. Google Scholar
[31] McKay, B. D. and Wormald, N. C. (1990) Uniform generation of random regular graphs of moderate degree. J. Algorithms 11 52–67.CrossRefGoogle Scholar
[32] McLaughlin, J. and Parsell, S. (2012) A Hardy–Ramanujan–Rademacher-type formula for (r, s)-regular partitions. Ramanujan J. 28 253–271.CrossRefGoogle Scholar
[33] Nicolas, J.-L. (1978) Sur les entiers N pour lesquels il y a beaucoup de groupes abéliens d'ordre N . Ann. Inst. Fourier (Grenoble) 28 1–16.CrossRefGoogle Scholar
[34] Nijenhuis, A. and Wilf, H. S. (1975) A method and two algorithms on the theory of partitions. J. Combin. Theory Ser. A 18 219–222.CrossRefGoogle Scholar
[35] Nijenhuis, A. and Wilf, H. S. (1978) Combinatorial Algorithms: For Computers and Calculators, Academic Press.Google Scholar
[36] Pak, I. (2006) Partition bijections: A survey. Ramanujan J. 12 5–75.CrossRefGoogle Scholar
[37] Pittel, B. (1997) On a likely shape of the random Ferrers diagram. Adv. Appl. Math. 18 432–488.CrossRefGoogle Scholar
[38] Pittel, B. (1997) Random set partitions: asymptotics of subset counts. J. Combin. Theory Ser. A 79 326–359.CrossRefGoogle Scholar
[39] Rademacher, H. (1937) A convergent series for the partition function p(n). Proc. Nat. Acad. Sci. 23 78–84.CrossRefGoogle ScholarPubMed
[40] Remmel, J. B. (1982) Bijective proofs of some classical partition identities. J. Combin. Theory Ser. A 33 273–286.CrossRefGoogle Scholar
[41] Sills, A. V. (2010) Rademacher-type formulas for restricted partition and overpartition functions. Ramanujan J. 23 253–264.CrossRefGoogle Scholar
[42] von Neumann, J. (1951) Various techniques used in connection with random digits. Journal of Research of the National Bureau of Standards, Appl. Math. Series 3, 36–38.Google Scholar