Boys-and-girls Birthdays and Hadamard Products

• Autorzy: Bodini O. , Gardy D. , Roussel O.
• Języki publikacji: EN

Abstrakty

EN

Boltzmann models from statistical physics, combined with methods from analytic combinatorics, give rise to efficient and easy-to-write algorithms for the random generation of combinatorial objects. This paper proposes to extend Boltzmann generators to a new field of applications by uniformly sampling a Hadamard product. Under an abstract real-arithmetic computationmodel, our algorithm achieves approximate-size sampling in expected time O(n.n) or O(n σ) depending on the objects considered, with . the standard deviation of smallest order for the component object sizes. This makes it possible to generate random objects of large size on a standard computer. The analysis heavily relies on a variant of the so-called birthday paradox, which can be modelled as an occupancy urn problem.

Słowa kluczowe

EN

Boltzmann samplers; combinatorial structures; Hadamard product; birthday problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 117, nr 1-4
• Strony: 85--101
• Opis fizyczny: Bibliogr. 17 poz., rys., tab.

Twórcy

autor

Bodini O.

autor

Gardy D.

autor

Roussel O.

• LIPN, Paris-XIII and UMR 7030, France,

Bibliografia

• [1] Arnold, D., Sleep, M.: Random generation of balanced parenthesis strings, ACM TOPLAS, 2(2), January 1980, 122-128.
• [2] Bassino, F., Nicaud, C., Weil, P.: Random generation of finitely generated subgroups of a free group, International Journal of Algebra and Computation, 18(2), 2008, 375-405.
• [3] Bodini, O., Jacquot, A.: Boltzmann Samplers for Colored Combinatorial Objects, Proceedings of GASCOM 2008, 2008.
• [4] Duchon, P., Flajolet, P., Louchard, G., Schaeffer, G.: Boltzmann samplers for the random generation of combinatorial structures, Combinatorics, Probability and Computing, 13(4-5), 2004, 577-625.
• [5] Feller,W.: An introduction to probability theory and its applications, vol. 1, Wiley & Sons, New York, 1968.
• [6] Flajolet, P., Fusy, é., Pivoteau, C.: Boltzmann Sampling of Unlabelled Structures, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics (D. Appelgate, Ed.), SIAM Press, 2007, Proceedings of the New Orleans Conference.
• [7] Flajolet, P., Gardy, D., Thimonier, L.: Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-Organizing Search, Discrete Applied Mathematics, 39, 1992, 207-229.
• [8] Flajolet, P., Sedgewick, R.: Analytic combinatorics, Cambridge University Press, 2008.
• [9] Flajolet, P., Zimmerman, P., Van Cutsem, B.: A calculus for the random generation of labelled combinatorial structures, Theoretical Computer Science, 132(1-2), 1994, 1-35.
• [10] Galbraith, S. D., Holmes, M.: A non-uniform birthday problem with applications to discrete logarithms, IACR Cryptology ePrint Archive, 2010, 2010, 616.
• [11] Hadamard, J.: Théor`eme sur les séries enti`eres, Acta Mathematica, 22(1), 1899, 55-63.
• [12] Hayman,W.: A generalisation of Stirling's formula, Journal für die reine und angewandteMathematik, 196, 1956, 67-95.
• [13] Nijenhuis, A., Wilf, H.: Combinatorial algorithms, New York, 1978.
• [14] Nishimura, K., Sibuya, M.: Occupancy with two types of balls, Annals of the Institute for Statistical Mathematics, 40(1), 1988, 77-91.
• [15] Popova, T. Y.: Limit theorems in a model of distribution of particles of two types, SIAM Journal on Theory of Probability and its Applications, 6(13), 1968, 511-516.
• [16] Rémy, J.: Un procédé itératif de dénombrement d'arbres binaires et son application `a leur generation aléatoire, RAIRO Theoretical Informatics and Applications, 19(2), 1985, 179-195.
• [17] Selivanov, B.: On the waiting time in a scheme for the random allocation of colored particles, Diskretnaya Matematika, 7(1), 1995, 134-144.